Friday Facts #182 - Optimizations, always more optimizations

Regular reports on Factorio development.
Rseding91
Factorio Staff
Factorio Staff
Posts: 13175
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by Rseding91 »

Xterminator wrote:
ili wrote:
Rseding91 wrote: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.
If you want to get ahold of me I'm almost always on Discord.

Asterix
Inserter
Inserter
Posts: 29
Joined: Wed Oct 12, 2016 5:51 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by 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) :P

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
Fast Inserter
Fast Inserter
Posts: 123
Joined: Sun Apr 03, 2016 7:00 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by bk5115545 »

Short and interesting. Just the way I like it.

posila
Factorio Staff
Factorio Staff
Posts: 5201
Joined: Thu Jun 11, 2015 1:35 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by posila »

Asterix wrote: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 :)
Asterix wrote:I will apparently have to run it on a non-accelerated graphics card (as the accelerated driver did not make the transition) :P
Oh no :( What FPS do you get in 0.14?

Kane
Filter Inserter
Filter Inserter
Posts: 666
Joined: Fri Sep 05, 2014 7:34 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by Kane »

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

User avatar
Pridesfall
Fast Inserter
Fast Inserter
Posts: 133
Joined: Thu Dec 18, 2014 7:18 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by 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
Smart Inserter
Smart Inserter
Posts: 1067
Joined: Wed Jun 29, 2016 10:02 am
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by Engimage »

Rseding91 wrote: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
Long Handed Inserter
Long Handed Inserter
Posts: 74
Joined: Tue Apr 08, 2014 6:40 am
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by bulldog98 »

PacifyerGrey wrote:
Rseding91 wrote: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
Inserter
Inserter
Posts: 29
Joined: Wed Oct 12, 2016 5:51 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by 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
Filter Inserter
Filter Inserter
Posts: 945
Joined: Wed Nov 25, 2015 11:44 am
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by vanatteveldt »

bulldog98 wrote: 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.

Kane
Filter Inserter
Filter Inserter
Posts: 666
Joined: Fri Sep 05, 2014 7:34 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by Kane »

Pridesfall wrote: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
Burner Inserter
Burner Inserter
Posts: 7
Joined: Tue Jun 16, 2015 5:13 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by 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
Fast Inserter
Fast Inserter
Posts: 225
Joined: Sat Nov 21, 2015 1:40 am
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by Nidan »

bulldog98 wrote: 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:
vanatteveldt wrote: 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.
kulib wrote: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
Filter Inserter
Filter Inserter
Posts: 950
Joined: Sat May 23, 2015 12:10 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by 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
Inserter
Inserter
Posts: 29
Joined: Wed Oct 12, 2016 5:51 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by 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 :P

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
Factorio Staff
Factorio Staff
Posts: 5201
Joined: Thu Jun 11, 2015 1:35 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by posila »

Asterix wrote: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
Inserter
Inserter
Posts: 29
Joined: Wed Oct 12, 2016 5:51 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by 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 :P

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

Several reasons, actually...

User avatar
Drury
Filter Inserter
Filter Inserter
Posts: 782
Joined: Tue Mar 25, 2014 8:01 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by Drury »

posila wrote:
Asterix wrote: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
Asterix wrote: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 :P
to be productive.

mrvn
Smart Inserter
Smart Inserter
Posts: 5682
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by mrvn »

cpy wrote: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

Kane
Filter Inserter
Filter Inserter
Posts: 666
Joined: Fri Sep 05, 2014 7:34 pm
Contact:

Re: Friday Facts #182 - Optimizations, always more optimizations

Post by Kane »

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

Post Reply

Return to “News”