Friday Facts #121 - Path Finder Optimisation II

Regular reports on Factorio development.
slpwnd
Factorio Staff
Factorio Staff
Posts: 1836
Joined: Sun Feb 03, 2013 2:51 pm
Contact:

Friday Facts #121 - Path Finder Optimisation II

Post by slpwnd » Fri Jan 15, 2016 4:52 pm

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

User avatar
Smarty
Global Moderator
Global Moderator
Posts: 816
Joined: Sat Oct 04, 2014 5:00 pm
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by Smarty » Fri Jan 15, 2016 5:08 pm

WHOOOO! Congratz klonan :D

ske
Filter Inserter
Filter Inserter
Posts: 389
Joined: Sat Oct 17, 2015 8:00 am
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by ske » Fri Jan 15, 2016 5:09 pm

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?

User avatar
SomeDuder
Inserter
Inserter
Posts: 37
Joined: Wed Feb 25, 2015 9:33 am
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by SomeDuder » Fri Jan 15, 2016 5:50 pm

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

fireant
Manual Inserter
Manual Inserter
Posts: 1
Joined: Fri Jan 15, 2016 5:44 pm
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by fireant » Fri Jan 15, 2016 5:51 pm

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.

User avatar
DasMonzta
Burner Inserter
Burner Inserter
Posts: 17
Joined: Wed Jun 04, 2014 10:43 am
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by DasMonzta » Fri Jan 15, 2016 5:54 pm

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
Global Moderator
Global Moderator
Posts: 5207
Joined: Fri May 30, 2014 8:54 am
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by Koub » Fri Jan 15, 2016 5:55 pm

SomeDuder wrote: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 ? :mrgreen:
Koub - Please consider English is not my native language.

Mion
Long Handed Inserter
Long Handed Inserter
Posts: 63
Joined: Thu Dec 04, 2014 7:38 am
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by Mion » Fri Jan 15, 2016 6:05 pm

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.
Last edited by Mion on Fri Jan 15, 2016 6:07 pm, edited 1 time in total.

_aD
Fast Inserter
Fast Inserter
Posts: 211
Joined: Sat Apr 12, 2014 12:03 am

Re: Friday Facts #121 - Path Finder Optimisation II

Post by _aD » Fri Jan 15, 2016 6:05 pm

SomeDuder wrote: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!

User avatar
Xterminator
Filter Inserter
Filter Inserter
Posts: 976
Joined: Sun Jun 15, 2014 4:49 pm
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by Xterminator » Fri Jan 15, 2016 6:06 pm

The pathfinding logic seems quite interesting. :D 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! :D
Image Image Image

Oxyd
Factorio Staff
Factorio Staff
Posts: 1297
Joined: Thu May 07, 2015 8:42 am
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by Oxyd » Fri Jan 15, 2016 6:20 pm

SomeDuder wrote: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
Fast Inserter
Fast Inserter
Posts: 175
Joined: Tue Jan 20, 2015 7:49 pm
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by Jonathan88 » Fri Jan 15, 2016 7:12 pm

DasMonzta wrote: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 :D )
FactoriOh No: when it's accidentally 2am, again

Koub
Global Moderator
Global Moderator
Posts: 5207
Joined: Fri May 30, 2014 8:54 am
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by Koub » Fri Jan 15, 2016 7:49 pm

Or the way ants tend to go where other ants from the hive have walked, following the pheromone path left behind.
Koub - Please consider English is not my native language.

YotaXP
Inserter
Inserter
Posts: 20
Joined: Sat Apr 05, 2014 7:17 pm
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by YotaXP » Fri Jan 15, 2016 8:23 pm

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
Fast Inserter
Fast Inserter
Posts: 104
Joined: Tue Apr 29, 2014 8:54 pm
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by Talguy » Fri Jan 15, 2016 10:49 pm

Just wanted to say congratulation to Klonan :)

Overread
Inserter
Inserter
Posts: 24
Joined: Fri Jan 02, 2015 3:05 pm
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by Overread » Fri Jan 15, 2016 11:14 pm

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

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

Re: Friday Facts #121 - Path Finder Optimisation II

Post by Drury » Sat Jan 16, 2016 12:38 am

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.

Image

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

Antaios
Long Handed Inserter
Long Handed Inserter
Posts: 60
Joined: Sun Jun 14, 2015 5:18 am
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by Antaios » Sat Jan 16, 2016 3:19 am

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
Burner Inserter
Burner Inserter
Posts: 13
Joined: Sat Dec 28, 2013 12:49 pm
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by lordjoda » Sat Jan 16, 2016 12:09 pm

Jonathan88 wrote:
DasMonzta wrote: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 :D )
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)
I'm a german Let's Player. If you like have a look at https://www.youtube.com/user/MightyPiratesLP

Marconos
Filter Inserter
Filter Inserter
Posts: 282
Joined: Mon Jun 02, 2014 10:46 pm
Contact:

Re: Friday Facts #121 - Path Finder Optimisation II

Post by Marconos » Sat Jan 16, 2016 4:10 pm

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.

Post Reply

Return to “News”

Who is online

Users browsing this forum: No registered users