Friday Facts #117 - Path Finder Optimisation I

[slpwnd]

This week you can read about our efforts to improve the path finder: https://www.factorio.com/blog/post/fff-117

[psihius]

So, the mod portal development died on you. With the amount of mods out there, that's sad news actually.

Are you thinking of actually contracting that work to people or a company who do WEB development, maybe?
If so, drop me a message, I will get in touch through official channels

[Peter34]

One potential issue with "caching" of found paths: Some mods allow the player to change the map, which would seem to possibly make old cached pats invalid.

The Landfill mod has a reputation for being able to create moats and thus being a cheaty mod. If true then that would certainly invalidate cached paths, if the player creates a moat to block a cached path. But the versions if Landfill that I've used specifically did not facilitate the creation of coherent surfaces of water, and so unless the mod has been changed recently (which I consider unlikely) cached paths can never be invalidated.

The reverse could well happen, however, with one alien finding a path around a medium-sized lake, and then caching that path (leaving a pheromone trail for its hippie comrades to follow), and then right after that the player auto-fills the entire lake using the option for that in the Landfill mod, which creates the silliness of a bunch of aliens cirling around a lake that no longer exists, instead of making a beeline across the now dry and eminently walkable lake bed.

How much damage to suspension of disbelief this does will depend on for how long paths are cached before the game attempts to re-path to see if a shorter way has arisen. 10 seconds? Good? 120 seconds? Potentially damaging. 600 seconds? Not good!

[matheod]

Hi,

I don't understand how the solution for very short length (<5) work. Instead of making the biter who bumped into the other search for a new very short path, you make the biter who have been bumped into move away, so also searching a new very short path. So why is this more efficient ?

Thanks !

[Rseding91]

One potential issue with "caching" of found paths: Some mods allow the player to change the map, which would seem to possibly make old cached pats invalid.

The Landfill mod has a reputation for being able to create moats and thus being a cheaty mod. If true then that would certainly invalidate cached paths, if the player creates a moat to block a cached path. But the versions if Landfill that I've used specifically did not facilitate the creation of coherent surfaces of water, and so unless the mod has been changed recently (which I consider unlikely) cached paths can never be invalidated.

The reverse could well happen, however, with one alien finding a path around a medium-sized lake, and then caching that path (leaving a pheromone trail for its hippie comrades to follow), and then right after that the player auto-fills the entire lake using the option for that in the Landfill mod, which creates the silliness of a bunch of aliens cirling around a lake that no longer exists, instead of making a beeline across the now dry and eminently walkable lake bed.

How much damage to suspension of disbelief this does will depend on for how long paths are cached before the game attempts to re-path to see if a shorter way has arisen. 10 seconds? Good? 120 seconds? Potentially damaging. 600 seconds? Not good!

All mods use the API so we know when tiles are modified and can update the cache as needed to account for any tile changes Also you're correct: I specifically coded the Landfill mod to not be able to create moats because at that point just turn off biters if you don't want to fight them

[Rseding91]

Hi,

I don't understand how the solution for very short length (<5) work. Instead of making the biter who bumped into the other search for a new very short path, you make the biter who have been bumped into move away, so also searching a new very short path. So why is this more efficient ?

Thanks !

Biter A who's following the path wants to go to a specific point. Biter A collides with biter B and asks B to move. B doesn't really care where it sits so it just walks "away" in any direction a few tiles to let the other biter past. It doesn't need to do any path finding it just needs to "go away" in any available direction

[devaking]

Nice.

i was reading the previous post about landfill mod and it got me thinking.

in the process of finding a way around a lake, if said value his higher then X, bitters go in a straight line into the water and drown, leaving a trail of body and slowly building a bridge toward source of pollution.

[Peter34]

All mods use the API so we know when tiles are modified and can update the cache as needed to account for any tile changes Also you're correct: I specifically coded the Landfill mod to not be able to create moats because at that point just turn off biters if you don't want to fight them

Cool.

In a recent YouTube Let's Play, someone (Steejo, IIRC) claimed that your mod could be used to make moats, but I corrected him.

[_aD]

Another interesting peek under the bonnet. Does this spell the end of the dancing spitter? I always found them entertaining :-P

[ridcully]

in the process of finding a way around a lake, if said value his higher then X, bitters go in a straight line into the water and drown, leaving a trail of body and slowly building a bridge toward source of pollution.

Factorio^WLeiningen versus the ants

[maxik]

Considering the path finding optimization.

How about making a gradient map that would guide the biters. When they attack, they always go to the same target, the player base, and that does not move. You could grow a gradient from players structures outwards, for a precise solution. Or simply from the centers of the sectors (map chunks) that contain player structures and continue with normal path find below certain distance.

This cost memory but saves cpu cycles. You don't even need to update the gradient immediately when player builds something, let the update run in background and bitters get close enough using the old data then again switch to normal path find.

[VanVeenGames]

A gradient map is interesting, but keep in mind that that's just basically pathfinding from the base and caching it all.

How about tracing? If you find water, it's probably a body of water. At this point you can trace the lake (keep water to the right/left). Of course tiny dents in the lake border will make it seem somewhat idiotic, but you could opt to do a jump check, where you get the fastest route from one traced point to a fairly close following tile. So you check once every ten tiles or so if the path to 10 tiles ahead is optimal. This is fairly light and can all be done in one pathfinding pass, reducing the overhead bottleneck part.

I recommend minimising caching all the way, and focusing on approximating paths instead. Remember: good intelligence is not always desired. I think it would even be fine to have almost no pathfinding whatsoever, just let them follow you and if the bump into trouble, take an eat it or leave it approach.

But other than that, you can also try a nav-mesh like approach, where you first look at a supergrid, like a supersampled mini-world with "factory", "land", "water", "mostly water" tiles with 5x5 tiles combined into one. Once you have this approximate path, you can connect all the 5x5 tiles with pathfinding within those small tiles. Probably works fine if balanced right (5x5 is just a guess, 10x10 may work as well).

And finally, ACO. Would be awesome. Not optimal, but who cares, it's awesome.

[jorgenRe]

Psst, I love working with databases, and seeing as it's Christmastime now. I can actually come and help some with the php, html and Javascript code and setup the database if the project is fairly straightforward !
PS I can make the skeleton, but making it look nice is not my thing :p

[ssilk]

Considering the path finding optimization.

How about making a gradient map that would guide the biters. When they attack, they always go to the same target, the player base, and that does not move. You could grow a gradient from players structures outwards, for a precise solution. Or simply from the centers of the sectors (map chunks) that contain player structures and continue with normal path find below certain distance.

This cost memory but saves cpu cycles. You don't even need to update the gradient immediately when player builds something, let the update run in background and bitters get close enough using the old data then again switch to normal path find.

I think this idea is worth following a bit more, cause all the paths need also memory.

And if you think this to the end a gradient map can also be seen as a "smell" or a cloud of pheromones. See https://forums.factorio.com/forum/vie ... f=6&t=3440

The natives can learn to avoid or focus on things, just by changing the gradient.

[Brambor]

I'm actually about to try solving some patchfinding performance in my python program
If you are interested it's D&S at github but it's not any actual program or well documented one

[ratchetfreak]

You could create a "super grid" based on chunks where you dedicate a point or 2 where the node is. and you cache connectivity

you use those paths to get the general path and then refine as that path won't be ideal.

[vaderciya]

What if, in addition to the path finding improvements already made, consider the following: Group biters into "squads" of 5, (or any number, really) so instead of having to path find for every biter from across a lake to the other side, where you get easy to kill 'conga lines' of biters, the game path finds for groups, so the amount of path finding to be done is decreased approximately 5 fold. Reducing the amount of overall work for the game in a long run, and adding a new formation of enemies to deal with. The post mentioned that pathing across a lake is very expensive for the path finding engine, so in theory I think this would help. Perhaps also some hierarchy in grouping. (Small biters together, medium biters together, large together, behemoth together)

This all makes sense in my head, but I'm not a programmer, so I don't fully understand the complexity of implementing it. But I want to help

[Brambor]

What if, in addition to the path finding improvements already made, consider the following: Group biters into "squads" of 5, (or any number, really) so instead of having to path find for every biter from across a lake to the other side, where you get easy to kill 'conga lines' of biters, the game path finds for groups, so the amount of path finding to be done is decreased approximately 5 fold. Reducing the amount of overall work for the game in a long run, and adding a new formation of enemies to deal with. The post mentioned that pathing across a lake is very expensive for the path finding engine, so in theory I think this would help. Perhaps also some hierarchy in grouping. (Small biters together, medium biters together, large together, behemoth together)

This all makes sense in my head, but I'm not a programmer, so I don't fully understand the complexity of implementing it. But I want to help

I believe that this is in the game already. When pollution reaches, bitters make groups, and then run 'as one man' towards the pollution source.
And yes that is exactly how the programator should think

[vaderciya]

What if, in addition to the path finding improvements already made, consider the following: Group biters into "squads" of 5, (or any number, really) so instead of having to path find for every biter from across a lake to the other side, where you get easy to kill 'conga lines' of biters, the game path finds for groups, so the amount of path finding to be done is decreased approximately 5 fold. Reducing the amount of overall work for the game in a long run, and adding a new formation of enemies to deal with. The post mentioned that pathing across a lake is very expensive for the path finding engine, so in theory I think this would help. Perhaps also some hierarchy in grouping. (Small biters together, medium biters together, large together, behemoth together)

This all makes sense in my head, but I'm not a programmer, so I don't fully understand the complexity of implementing it. But I want to help

I believe that this is in the game already. When pollution reaches, bitters make groups, and then run 'as one man' towards the pollution source.
And yes that is exactly how the programator should think

Can we confirm that the game groups enemies together and simulates their path finding as a single entity? I don't mean to question you, just want to be sure but if the game already did that, then I don't believe it would be very difficult to path find for a couple of groups even across large distances and or lakes. The reason for my disbelief is that I've obviously played a lot of factorio, and I've noticed that even in huge groups the biters all seem to have individual path finding even when adjacent to many many other biters, sometimes biters on the sides of a group will sometimes branch off from charging a direction to go somewhere else or attack something else. I'd really like to understand how they work, so don't be afraid to post an essay about it, this stuff really interests me and I love learning

[Cos]

Regards Biters blocking each other and short paths.

A few years ago I read the book 'The man who loved only numbers' by Paul Hoffman. It's an biography of the Hungarian mathematician Paul Erdős.
In it one of his collaborators, Ronald Graham, talks about a problem he faces while working at a telecoms company.

In trying to route phone calls the company ran into a problem when sometimes calls would run into each other - trying to use the same piece of the network (or the same 'tile' in Factorio).
They tried many complex systems to try to optimise this but in the end they found the easiest, fastest and and least expensive in terms of overhead way was:

Pick another immediate option at Random with no actual 'pathing' taking place at all!
This occasionally led to a very brief 'dance' like you get on the street when two people walk towards each other but that doesn't last long - by picking a side at random you'll likely only need 2 or 3 attempts (each of which cost very little overhead) before the impasse is cleared.

Incidently - even if you are even remotely interested in mathematics I would recommend the book - it's very readable and accessable and gives some facinating insights into mathematics and mathematicians.

Keep up the good work team!