Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Xolroc]

What, exactly, is the algorithm that DF uses for pathfinding?  I'm curious as to whether improvements are even possible while retaining universality.

[Sizik]

A*, I believe.

[ORCACommander]

A heavily modified A* algorithm.

interactive examples: http://qiao.github.io/PathFinding.js/visual/

[Xolroc]

I know it's based around A*, but in what ways is it modified?  (also, that is an amazing little applet, I'm gonna play with that a bit)

[ORCACommander]

for one there are weight values assigned to every tile. by default iirc the weight of any given tile is 25. if you start placing routes you get a whole wide range of values. and i  do not know if the A* algorithm takes into account a z axis to begin with.

[Xolroc]

If that's all, then I'd suggest Toady take a look at the Jump Point Search algorithm; it's an extension of A* that takes advantage of the fact that long straight paths are often possible, and only checks around obstacles.

[Urist Da Vinci]

Tile weights in an unedited game are:
HIGH 1
NORMAL 2
LOW 5
RESTRICTED 25

In a weight 1 area, A* will search out straight line paths first and not expand until it hits obstacles. HIGH traffic zones in hallways and staircases can really help out your FPS.

[Xolroc]

However, the advantage of JPS is that it treats long collections of free squares (hallways, rooms) as a single entity, and skips to the nearest place at which a turn would move closer to another feature/obstacle that it may need to path around.  This can provide large improvements in speed in very orderly systems, like the average player's fortress, and moderate improvements in randomized terrain.  The link earlier in this thread shows how A* works, but it also has other systems, including JPS, so you can see what I mean.

[Mr. Palau]

However, the advantage of JPS is that it treats long collections of free squares (hallways, rooms) as a single entity, and skips to the nearest place at which a turn would move closer to another feature/obstacle that it may need to path around.  This can provide large improvements in speed in very orderly systems, like the average player's fortress, and moderate improvements in randomized terrain.  The link earlier in this thread shows how A* works, but it also has other systems, including JPS, so you can see what I mean.

I hope the pathing program uses something like this already. Please good god Armok.

[Xolroc]

If it uses A*, then no it doesn't.  But remember, it's not as simple to compute as you think.  There are more computations in A*, but they're faster than the more complex but fewer ones that need to be done in JPS.  So the speed increase isn't as great as you'd expect.  Look at the timer in the bottom left of that applet.

[Di]

Well, we don't know much of the inner workings of the game. Toady probably has modified that A* beyond recognition so that simple version from applet does not represent it well.
There was a couple of threads on suggestion board about JPS, though it's unknown whether Toady has seen them.