Friday Facts #182 - Optimizations, always more optimizations

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

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

Post by Rseding91 » Sat Mar 18, 2017 9:51 pm

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

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

Post by Asterix » Sat Mar 18, 2017 10:16 pm

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 » Sat Mar 18, 2017 11:02 pm

Short and interesting. Just the way I like it.

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

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

Post by posila » Sat Mar 18, 2017 11:24 pm

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: 654
Joined: Fri Sep 05, 2014 7:34 pm
Contact:

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

Post by Kane » Sun Mar 19, 2017 12:07 am

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.

Pridesfall
Burner Inserter
Burner Inserter
Posts: 16
Joined: Thu Dec 18, 2014 7:18 pm
Contact:

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

Post by Pridesfall » Sun Mar 19, 2017 7:29 am

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.

PacifyerGrey
Smart Inserter
Smart Inserter
Posts: 1014
Joined: Wed Jun 29, 2016 10:02 am
Contact:

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

Post by PacifyerGrey » Sun Mar 19, 2017 8:05 am

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 » Sun Mar 19, 2017 8:43 am

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

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

Post by Asterix » Sun Mar 19, 2017 9:31 am

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: 913
Joined: Wed Nov 25, 2015 11:44 am
Contact:

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

Post by vanatteveldt » Sun Mar 19, 2017 3:08 pm

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: 654
Joined: Fri Sep 05, 2014 7:34 pm
Contact:

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

Post by Kane » Sun Mar 19, 2017 3:30 pm

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

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

Post by kulib » Sun Mar 19, 2017 3:59 pm

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

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

Post by Nidan » Sun Mar 19, 2017 5:40 pm

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: 934
Joined: Sat May 23, 2015 12:10 pm
Contact:

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

Post by ratchetfreak » Mon Mar 20, 2017 9:44 am

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

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

Post by Asterix » Mon Mar 20, 2017 10:43 am

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: 3484
Joined: Thu Jun 11, 2015 1:35 pm
Contact:

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

Post by posila » Mon Mar 20, 2017 10:49 am

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

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

Post by Asterix » Mon Mar 20, 2017 12:06 pm

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: 679
Joined: Tue Mar 25, 2014 8:01 pm
Contact:

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

Post by Drury » Tue Mar 21, 2017 11:41 am

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.
Image

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

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

Post by mrvn » Tue Mar 21, 2017 1:48 pm

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: 654
Joined: Fri Sep 05, 2014 7:34 pm
Contact:

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

Post by Kane » Tue Mar 21, 2017 1:57 pm

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”

Who is online

Users browsing this forum: bobucles