Friday Facts #182 - Optimizations, always more optimizations

[Rseding91]

Single sided, double sided, a big train, a small one, loop-based or no loops makes no difference in the games performance. They're all the same.

I have no idea where people get these ideas from but they're all false.

Here for example:
https://youtu.be/E7st8UawPBI?t=8m32s
Should I tell Xterminator that he is totally wrong and need to do a correction video?

I will, and already have admitted I was wrong in that video about the trains. I had misunderstood some thing's some other people had discussed with me.
Loops are still bad, but not necessarily for lag or performance reasons. I do apologise for misleading anyone, it certainly wasn't my intention. The takeaway from the video I still stand behind though, to not use loops. Just not for the reason I said in the video.

Yes, it's not that "a loop is harder to path find for" but that a loop provides more paths for the A* path finding to check against because it connects more possible routes for the train to drive through. Creating the same paths through a non-looped system would give the same performance but there's no real advantage to doing that - it's just really easy to do with a loop.

[Asterix]

After a non-trivial amount of effort, I finally managed to upgrade the amazing potato to 64 bits: I am officially ready to run Factorio 0.15.

I really appreciate the effort going into optimizing performance, since I will apparently have to run it on a non-accelerated graphics card (as the accelerated driver did not make the transition)

Also the fact that most of the effort is currently apparently going into optimization and debugging, which presumably means all the cool new features are in and the first experimental release should be out soon (TM).

Keep up the good work, and do please let us know when we can take a peek at the first "this might reformat your cat" release

[bk5115545]

Short and interesting. Just the way I like it.

[posila]

After a non-trivial amount of effort, I finally managed to upgrade the amazing potato to 64 bits: I am officially ready to run Factorio 0.15.

I am happy to hear that

I will apparently have to run it on a non-accelerated graphics card (as the accelerated driver did not make the transition)

Oh no What FPS do you get in 0.14?

[StoneLegion]

I feel like losing the acceleration might be a lot worse since your not going get much out of 64 besides requirements Graphic wise if your FPS tanking now your game is going be crappy and not fun period.

[Pridesfall]

Can you please add a vote kick command to the server when there is no admin logged in. I'm in a game right now that had a monster factory in it and two guys, Hadi, and bernalfa, came in and set the whole factory to deconstruct and there was nothing we could do about it. Thanks.

[Engimage]

Single sided, double sided, a big train, a small one, loop-based or no loops makes no difference in the games performance. They're all the same.

I have no idea where people get these ideas from but they're all false.

If you have a loop at every intersection it should multiply available paths exponentially based on the number of intersections you will meet on the way.
I am not sure how the pathfinding in factorio works but generally in many-to-many lists the search tree works mostly the same. Loop-free design prevents the search tree from growing and should perform better.

Correct me if I am wrong.

But maybe the process of path finding is so fast anyways that it will not impact game performance at all as it actually runs pretty rarely.

[bulldog98]

Single sided, double sided, a big train, a small one, loop-based or no loops makes no difference in the games performance. They're all the same.

I have no idea where people get these ideas from but they're all false.

If you have a loop at every intersection it should multiply available paths exponentially based on the number of intersections you will meet on the way.
I am not sure how the pathfinding in factorio works but generally in many-to-many lists the search tree works mostly the same. Loop-free design prevents the search tree from growing and should perform better.

Correct me if I am wrong.

But maybe the process of path finding is so fast anyways that it will not impact game performance at all as it actually runs pretty rarely.

They use the A* algorithm which is normally algoritmically fast, but only gives approximate optimal results, since pathfinding is NP hard. And solving NP hard problems exact can take exponential time.

[Asterix]

I haven't tried actually *playing* 0.14/64 yet... Not on the upgraded amazing potato at least.

I started up an 0.13/64 I had around (which I had downloaded to confirm that Linux, unlike BSD, doesn't support running 64-bits applications on a 32-bits kernel). The game loads and renders, so I confirmed that the system meets the software prerequisites.

As for the hardware ones...

The amazing potato has a dual core APU from 2014, with 4GB of RAM.

Factorio 0.14/32 ran just fine (as long as I kept my factory relatively self-contained, obviously).

I think that's a testament to the level of optimization that was put into the game, but optimization can only take you so far.


Things I learned this week:

- You can, in fact, upgrade a live Ubuntu from 32 to 64 without reinstalling.
- The words *can* and *should* look nothing alike. So do a live upgrade and a fresh install.
- The Xenial kernel still has a ways to go to catch up with the Trusty one.

Oy vey.

[vanatteveldt]

They use the A* algorithm which is normally algoritmically fast, but only gives approximate optimal results, since pathfinding is NP hard. And solving NP hard problems exact can take exponential time.

It's a while since I did AI, but afaik A* is provably correct if the estimation heuristic is always optimistic. For pathfinding the euclidian distance is an easy heuristic, which is always optimistic since a straight line is guaranteed to be the shortest route.
Thus, pure A* with euclidian distance as heuristic is not an approximation but will always find the actual shortest path.

Of course, they probably use a lot of other optimizations, pruning, and heuristics, which might well make it approximate.

[StoneLegion]

Can you please add a vote kick command to the server when there is no admin logged in. I'm in a game right now that had a monster factory in it and two guys, Hadi, and bernalfa, came in and set the whole factory to deconstruct and there was nothing we could do about it. Thanks.

This kind of thing would be a mod not base game. Sure they can add ban/kick if it's already not built in but I highly and I mean HIGHLY doubt they will build in a automated ban/kick system via votes. This is just something not suitable for 99% of games due to its abusive nature.

[kulib]

So, one little question for me. Is A* algorithm something simular to Bellman-Ford algo?
I don't have enough knowledge in this section of knowledge, so, the question is:
Does Bellman algo have worse performance than A*?
https://en.m.wikipedia.org/wiki/Bellman–Ford_algorithm

[Nidan]

They use the A* algorithm which is normally algoritmically fast, but only gives approximate optimal results, since pathfinding is NP hard. And solving NP hard problems exact can take exponential time.

Well, while A* being in NP is technically correct, A* is actually in P. The worst case, exploring the whole graph (aka train network), can be done in O(n + m) <= O(n^2) time. (with n being the number of vertices (signals) and m being the number of edges (connections from one signal to the next). Also A* is an exact algorithm as was already said:

It's a while since I did AI, but afaik A* is provably correct if the estimation heuristic is always optimistic. For pathfinding the euclidian distance is an easy heuristic, which is always optimistic since a straight line is guaranteed to be the shortest route.
Thus, pure A* with euclidian distance as heuristic is not an approximation but will always find the actual shortest path.

So, one little question for me. Is A* algorithm something simular to Bellman-Ford algo?
I don't have enough knowledge in this section of knowledge, so, the question is:
Does Bellman algo have worse performance than A*?
https://en.m.wikipedia.org/wiki/Bellman–Ford_algorithm

Bellman-Ford needs more time but can cope with negative edge weights (i.e. arriving somewhere before you leave) and negative cycles. Depending on the implementation Dijkstra (or A*) can handle negative edges while loosing the runtime guarantee. Negative cycles will always lead to either an infinite loop or wrong results Dijkstra/A*. (The shortest path is no longer well-defined).
Since trains don't time travel Bellman-Ford is a bad choice.

[ratchetfreak]

For train overview rendering the first thing that you can do is cull the minimaps that aren't visible in the menu...

Then you could divide the map into tiles and render a 3x3 area around every tile with a train in it (possible joining some renders into a 4x3 or a 4x4 depending on factors) . Then use those textures to sample from when drawing the train menu. This will make rendering all the train maps linear (each train is rendered at most 9 times) instead of quadratic at the cost of extra memory used (up to a max of the total minimaps visible).

Or it could be a separate path from the current render path that only triggers when another train is in the area.

A more advanced option is to do advanced clustering of the trains to group them for rendering.

[Asterix]

Rseding91: Yep, you were right: I get 7 +/- 2 fps on the non-accelerated driver.

I could live with, say, 20 +/- 5, but 5 is a bit on the low side

On the accelerated driver, however, which I eventually managed to reinstall by downgrading the kernel, I get a perfectly playable 40-50.

I really hope the Xenial devs will fix this at some point...

[posila]

I eventually managed to reinstall by downgrading the kernel, I get a perfectly playable 40-50.

I am amazed someone with ability to do this doesn't have budget to buy a not-potato computer.

[Asterix]

It's not always a matter of budget The amazing potato is essentially a netbook, and a relatively recent one at that (2015).

I have bigger and better hardware, but it doesn't follow me around like the potato

Incidentally, crossgrading from 32 to 64 bits was... Less than straightforward. By comparison, downgrading the kernel was a walk in the park.

Apparently, aptitude doesn't like it when you need both the 32 and the 64 bits version of PERL installed at the same time: the unresolved dependencies count kept growing and growing for several minutes, eventually surpassing the number of installed packages, until I eventually decided to just put it out of my misery and manually fix the 600-odd broken packages

I mean, there's a reason I'd been putting off upgrading

Several reasons, actually...

[Drury]

I eventually managed to reinstall by downgrading the kernel, I get a perfectly playable 40-50.

I am amazed someone with ability to do this doesn't have budget to buy a not-potato computer.

They spend too much of their time doing things like this

Apparently, aptitude doesn't like it when you need both the 32 and the 64 bits version of PERL installed at the same time: the unresolved dependencies count kept growing and growing for several minutes, eventually surpassing the number of installed packages, until I eventually decided to just put it out of my misery and manually fix the 600-odd broken packages

to be productive.

[mrvn]

They should've made minecraft. You'd have nearly infinite worlds with high UPS even with demanding mods.

and none of the millions of glitches

[StoneLegion]

You telling me you rather have Minecraft then Factorio...? There would not be both it would been one or the other.