Friday Facts #121 - Path Finder Optimisation II

[transportman]

If the cache has no more room for another path, we use the difficulty-to-compute information to decide which path to remove from the cache in order to make more room.

Do you also consider how often a path is used and when a path has last been used? Just to remove unused paths from the cache, instead of keeping them because they are difficult to compute. I assume you also considered this, but it is not mentioned.

[ketil]

I wonder if you could talk a bit about ideas for optimalizations you have rejected and why? I have a couple of ideas, but because I don't have in depth knowledge of your code, and you probably have thought of them already they might not be very useful, but I write them just in case.

You said in FF117 that it is expensive to initialize the pathfinder, have you considered making two different pathfinders and use a relatively cheap test to find out which to use? Then you could use a lighter, less intelligent, brute force pathfinder for short paths and only care about direction for long paths. If the short path-finder fail to find anything sensible within a reasonable amount of tries, then maybe it could start the long-path-finder. The most expensive paths would then be if the cheap test guessed it was finding a short part while it in reality was a long path. On the other hand the path finders could be less generic, and more optimized for the average case it is used given the result of the cheap test.

The absolute distance between A and B(without caring about obstacles) is sqrt((B.x- A.x)^2 + (B.y - A.y)^2)). Not sure how expensive sqrt is, but you can do the test against a constant that is already squared. So say you want the pathfinder to use the short simple one for paths with less than 50 absolute distance, then you could say if ((B.x- A.x)^2 + (B.y - A.y)^2) > 50*50) {longpath(param);} else {shortpath(param);}. Remember, a path with long absolute distance is always long, but a path with short absolute distance is probably, but not always short.

As for the frequency, if you calculate A->B->C->D first and then find that you can use B->C afterwards then you may end up removing the full path, but keeping the subpath. Especially if B->C is long and frequent, but A->B and/or C->D is not.

There may or may not also be a good idea to special case the area around biter bases in order to calculate the paths there either in a cheaper way, or using cache more. Maybe it's a good idea to do a debug test to record the amount of obstacles you encounter, and the type of them in order to find out which cases it makes most sense to special case, or not.

[Antaios]

You said in FF117 that it is expensive to initialize the pathfinder, have you considered making two different pathfinders and use a relatively cheap test to find out which to use? Then you could use a lighter, less intelligent, brute force pathfinder for short paths and only care about direction for long paths. If the short path-finder fail to find anything sensible within a reasonable amount of tries, then maybe it could start the long-path-finder. The most expensive paths would then be if the cheap test guessed it was finding a short part while it in reality was a long path. On the other hand the path finders could be less generic, and more optimized for the average case it is used given the result of the cheap test.

The absolute distance between A and B(without caring about obstacles) is sqrt((B.x- A.x)^2 + (B.y - A.y)^2)). Not sure how expensive sqrt is, but you can do the test against a constant that is already squared. So say you want the pathfinder to use the short simple one for paths with less than 50 absolute distance, then you could say if ((B.x- A.x)^2 + (B.y - A.y)^2) > 50*50) {longpath(param);} else {shortpath(param);}. Remember, a path with long absolute distance is always long, but a path with short absolute distance is probably, but not always short.

That's basically what they said they were doing with FF117, using simple, cheap avoidance logic for paths shorter than 50 tiles.

[ketil]

That's basically what they said they were doing with FF117, using simple, cheap avoidance logic for paths shorter than 50 tiles.

A proper specialised pathfinder for short paths can do things that simple avoidance can't do, depending how it's implemented, e.g. add small impossible paths to negative cache: e.g. the example with the biter on the peninsula. A pathfinder with short working range need less initialisation,or maybe even be a stateless function without initialization, possibly at slight increased cost during the pathfinding itself. It is common to solve small problems with stupid, but simple algorithms, because the cost of being smart can be unreasonably high for small datasets. This cost doesn't matter much if you only do a few of them, but it is quickly adding up if it's many, and you need to reinitialize them. Doing a lot of small problems is different from doing a few large ones. Maybe the current pathfinder, could save time if it didn't have to handle short paths in the exception cases. And a proper pathfinder doesn't have to call the backup pathfinder if it is sure that no path exist, which decrease the requirement for negative path cache.

[Antaios]

A proper specialised pathfinder for short paths can do things that simple avoidance can't do, depending how it's implemented, e.g. add small impossible paths to negative cache: e.g.

Avoidance is cheap, and if the avoidance fails the biter would fall back on the pathfinder anyway, the pathfinder would then add the negative path to the cache.

the example with the biter on the peninsula. A pathfinder with short working range need less initialisation,or maybe even be a stateless function without initialization, possibly at slight increased cost during the pathfinding itself.

I'm not sure how a pathfinder with a short working range would somehow be faster to initialise and run. The only thing that changes is the size of the grid, which shouldn't need initialising since it's already there. Unless the working area is copied into another series of arrays for the pathfinder to work on, it shouldn't make a difference, and if it did, probably not a huge difference.

If it does make a difference then the pathfinder itself could use the distance between the start and end points to guess the working area anyway, and if while working, the pathfinder hits the boundary it would then expand the area dynamically. That would add a 'small pathfinder' type optimisation to all pathfinds, rather than just short ones.

It is common to solve small problems with stupid, but simple algorithms, because the cost of being smart can be unreasonably high for small datasets. This cost doesn't matter much if you only do a few of them, but it is quickly adding up if it's many, and you need to reinitialize them. Doing a lot of small problems is different from doing a few large ones. Maybe the current pathfinder, could save time if it didn't have to handle short paths in the exception cases. And a proper pathfinder doesn't have to call the backup pathfinder if it is sure that no path exist, which decrease the requirement for negative path cache.

But the pathfinder doesn't handle short paths, the avoidance logic does.?
And the main pathfinder doesn't start up if it's sure that no path exists, it should check the negative path cache first, which lists the most common non-existing paths and tells it there's no path there.
The negative path cache is almost certainly faster than using a smaller path finder (I still don't know how thats somehow faster)

Given that, I have my doubts about this negative path cache, It seems to rely too heavily on things wanting to go to the same place. What if 20 biters are all trapped on a peninsula, and all of them want to go in different directions? 20 negative paths. Plus there's the issues other people have posted about how it's going to update when the path is no longer blocked. I think this needs a better solution, which is why I suggested one earlier, although that possibly has it's own problems.

[RaviorMetal]

You know what you guys should do?
Create a book with all the technical stuff from your friday facts and sell it.
Indie Game developers love stuff like this and would instant buy it.
You could also create wiki articles for a game dev wiki about optimizations from it I guess.

[ssilk]

This would be indeed a good idea.

[Kewlhotrod]

You know what you guys should do?
Create a book with all the technical stuff from your friday facts and sell it.
Indie Game developers love stuff like this and would instant buy it.
You could also create wiki articles for a game dev wiki about optimizations from it I guess.

or just release it for free, putting a price on information is toxic, should be free and open source for any of those who wish to contribute to it.

[ssilk]

It's already everything here. Free, without price. You "just" need to read everything.
Why should someone not be payed for reading things and put the essence in another book?

[-root]

Congrats to Klonan. He should be a good fit to the team and he already knows the community and the community already knows him so there's no way he can fail



No but seriously, Klonan, good luck! If Factorio goes big, you're gonna need it!!!

[jockeril]

Hello everyone ! been away for sometime, concentrating on other things, but I never really left Factorio - keeping up with the FFF's.

I was sad to hear about betka leaving and I'm glad to hear that the position has been filled and with a community member, no less ! Congratulations Klonan - leave long and prosper

and for you the factorio team - Thank you for your continued improvement of the game - the ideas you talk of sound great and a good reason to continue playing (just as soon as I finish Fallout 3 )

keep up the good work,
jocker

[dimmy]

Moved from Ideas and Suggestions to this thread
-- daniel34

Hi devs, i've read a lot about your path-finder-solveing problem and...
Did you think that this is a problem from programmers algorithm competitions (yes, i was competitor, now the coach, russia).
So, A* is not one of the best desicions for you.
There are solutions but not in english language sometimes)

You might check following:

1) Jump Point Search
http://users.cecs.anu.edu.au/~dharabor/pathfinding.html
Russian article: http://habrahabr.ru/post/162915/

2) The best resource
http://neerc.ifmo.ru/wiki/index.php?tit ... 0%B5%D0%B9

3) So, one of the solutions in games, that i saw was next:
you do standart A*, but you do it not in real small tiles (1x1 size), you do it on bigger tiles with sizes 10x10 and find path with them, if the path exists, then you should take that found-tiles and devide them into 3x3 x9 tiles ( 3x3 tiles * 9 times = 10x10 tile).

With method from 3 you can speed up your path finding without need of cache and etc. (do you remember that ant tree-cuting should result in cache recalculate?).

Also, if you want it can be the contest from factorio-gamers, that write they own algorithm for thim, and you take the best (like http://www.topcopder.com do) and even can take this guy for a work.

[starholme]

You know what you guys should do?
Create a book with all the technical stuff from your friday facts and sell it.
Indie Game developers love stuff like this and would instant buy it.
You could also create wiki articles for a game dev wiki about optimizations from it I guess.

Just another vote for this idea. I love the technical updates, and would buy this book. I just upgraded to the highest purchase tier, because I've played this game way too much since purchasing it with the lowest tier.

[kel]

Moved from Ideas and Suggestions to this thread
-- daniel34

Hi devs, i've read a lot about your path-finder-solveing problem and...
Did you think that this is a problem from programmers algorithm competitions (yes, i was competitor, now the coach, russia).
So, A* is not one of the best desicions for you.
There are solutions but not in english language sometimes)

You might check following:

1) Jump Point Search
http://users.cecs.anu.edu.au/~dharabor/pathfinding.html
Russian article: http://habrahabr.ru/post/162915/

2) The best resource
http://neerc.ifmo.ru/wiki/index.php?tit ... 0%B5%D0%B9

3) So, one of the solutions in games, that i saw was next:
you do standart A*, but you do it not in real small tiles (1x1 size), you do it on bigger tiles with sizes 10x10 and find path with them, if the path exists, then you should take that found-tiles and devide them into 3x3 x9 tiles ( 3x3 tiles * 9 times = 10x10 tile).

With method from 3 you can speed up your path finding without need of cache and etc. (do you remember that ant tree-cuting should result in cache recalculate?).

Also, if you want it can be the contest from factorio-gamers, that write they own algorithm for thim, and you take the best (like http://www.topcopder.com do) and even can take this guy for a work.

Here is a working link (topcoder not topcopder) http://www.topcoder.com