Friday Facts #121 - Path Finder Optimisation II

[slpwnd]

Today Oxyd gives more details on our path finder improvements efforst: http://factorio.com/blog/post/fff-121

[Smarty]

WHOOOO! Congratz klonan

[ske]

Does that patch caching mean that all enemies coming from one area going to another area take the same path for the most part?

Or is the cached path(part) used as starting point for a path optimization?

[SomeDuder]

Damnit, finish the story! Does the lonely biter eventually find his friends or does he die of old age, friendless and bitter?

[fireant]

Regarding pathfinding optimization:
I suppose you have seen this already, but I will post it just in case: Jump Point Search https://harablog.wordpress.com/2011/09/ ... nt-search/ is a great optimization for pathfinding on uniform grids (what Factorio is afaik).
Tynan Sylvester did a great video on optimizing pathfinding in his game Rimworld: https://www.youtube.com/watch?v=RMBQn_sg7DA, while probably not aplicable to Factorio as both are trying to achieve bit different things it still can be quite an interresting watch.

[DasMonzta]

I would love to see the bitters actually try to find paths like ants do
I think that would be really realistic, since it seems not logical that every bitter knows his paths already.
And it is computationally not that kind of a bad idea and your approach is not that far away from those strategies
I mean swarm intelligence just sounds like bitters stuff :p
https://en.wikipedia.org/wiki/Ant_colon ... algorithms

[Koub]

Damnit, finish the story! Does the lonely biter eventually find his friends or does he die of old age, friendless and bitter?

Damn a bitter biter ?

[Mion]

About Negative Cache:
If item that blocks a path will be destroyed (for example, biter spawner), will information in cache be updated? Because if not, hypothetically effective paths will no be used after changes on the map.

UPD: information in negative cache.

[_aD]

Damnit, finish the story! Does the lonely biter eventually find his friends or does he die of old age, friendless and bitter?

This is your doing!

[Xterminator]

The pathfinding logic seems quite interesting. It definitely makes sense to have to it use paths that are already in place instead of making an entirely new one each time. I can see for sure how this would reduce the number of things going on in the background while playing. Awesome work as always!

Also, huge congrats to Klonan!

[Oxyd]

Damnit, finish the story! Does the lonely biter eventually find his friends or does he die of old age, friendless and bitter?

He dies a quiet and lonely death. No one comes to mourn him or bury him, because he's unreachable.

[Jonathan88]

I would love to see the bitters actually try to find paths like ants do

What might be an idea is to create 'paths' on the sections where biters walk the most (a bit like animal runs https://littlesundog.files.wordpress.co ... l-path.jpg)
This would make it more realistic and it could be useful in determining where the biters attack the most )

[Koub]

Or the way ants tend to go where other ants from the hive have walked, following the pheromone path left behind.

[YotaXP]

We haven't yet figured if all the experimental updates will go to Steam, or what exactly will be the model, but we are working on that.

Pretty sure you can upload multiple branches to Steam. Players can choose which branch they want to play from the "Betas" tab of the game's property page.

[Talguy]

Just wanted to say congratulation to Klonan

[Overread]

About Negative Cache:
If item that blocks a path will be destroyed (for example, biter spawner), will information in cache be updated? Because if not, hypothetically effective paths will no be used after changes on the map.

UPD: information in negative cache.

This is what I'm wondering as well; especially with regard to how Biters regard player built features as accessible or inaccessible. Otherwise, in theory, the player could build key structures behind a barrier of sufficient size to make biters avoid it as a pathway and then demolish the structures and the biters would still think it impossible to reach.

[Drury]

Well like I said before, Steam allows developers to upload various releases as separate "betas" and the users to pick which beta to opt into, and a special "latest" beta selected by default which you as a dev just update with the latest patch and have everyone automatically update to. You can have a beta for each version of Factorio, effectively allowing Steam users to downgrade at their leisure at any time and instantly. Euro Truck Simulator does this and it's awesome.



The Steam version can just have the autoupdater disabled by default (which I think is the actual default behavior anyway?) and just download the updates from Steam. I believe for most users this is the most convenient solution, since they can update without launching the game and using Steam's bandwidth limiter in case they need it.

Of course I take it you want to keep the game DRM-free, so you can keep the autoupdater in the game for non-Steam users or Steam users who change their mind on Steam, no problem. There's no reason to have a special dedicated Steam version with this model as far as I know.

[Antaios]

I remember I've used an area code system before to solve the problem of invalid path finds.

Essentially every tile is assigned an area number, areas that aren't connected are assigned different (unique) numbers. Then if a path-find has start and end points with different area numbers, the path is invalid.

Whenever placing or removing objects that can obscure paths, the boundary of the object is checked for obstacles. If all boundary blocks meet up, nothing needs updating. If they don't then the boundary check continues along the obstacle edges until either they meet or distinct region/s are found.
The number of areas directly surrounding the object earlier can be used to determine when all boundary regions have been found (# of areas - 1). So if there's a placed object with three obstacles spaced out around it, there would be three areas directly adjacent, and two distinct regions need to be found.
once the regions are found the tiles inside can be updated with unique area numbers. A few methods would need testing to try and only change the area number of the smaller areas, rather than accidentally updating the entire map.

It's quick for determining that a path is invalid, but updating the list can become slow when enclosing large areas. unfortunately this might start happening frequently in a large enclosed base where biters destroy walls and they're replaced by bots often.


Just a thought.

[lordjoda]

I would love to see the bitters actually try to find paths like ants do

What might be an idea is to create 'paths' on the sections where biters walk the most (a bit like animal runs https://littlesundog.files.wordpress.co ... l-path.jpg)
This would make it more realistic and it could be useful in determining where the biters attack the most )

I wanted to suggest exactly the same thing! Possibly the "path" would also increase the movement speed a bit making it even more likely that a npc will use this path and therefore maybe save even more calculation time? (I think Settlers 3 is a good example, though I'm not sure if it did increase movements speed)

[Marconos]

I'm really looking forward to this optimization. In my current game (max biter settings) my ups/fps drops to low 20's from upper 40's when I engage most hives. Really curious to see how that can affect this as the game play seems really weird when you have solo motion for all combat.