Print

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

[Ampersand]

http://www.helsinki.fi/~lappinen/tira/pathfinder.html

What we have here is a java application which graphically represents A* and Dijkstra path finding.

Why would one prefer A* over Dijkstra? In wide open expanses, it has obvious benefits, and quickly finds the path of least resistance. However, something peculiar happens when we add in winding tunnels and more complex walls to navigate through. Suddenly, A* takes far longer to find a short path than does Dijkstra.

Yeah... ...Well I thought it was interesting!

[Veroule]

I will have to play with this later.  I will be developing a complete design for improving the pathfinding, and knowing weaknesses to specific alogarithms will be part of it.

Thanks for the link and info.

[Sowelu]

Personally, I think the most poignant lesson from this app is that in mazey corridors, they BOTH suck.  I would love to see an applet that actually demonstrates some of the cluster-based solutions (where you divide the map into 4x4 or 8x8 clusters that know what paths lead through them)

[Fossaman]

Has anybody ever tried doing pathfinding where it searches from both the start and end points at the same time? It seems like the A* method with searches from both the origin and the destination would be considerably faster. But I don't know much about pathfinding, so feel free to ignore me.

[Ampersand]

That might actually make multiple core use make sense.

[Sowelu]

Bidirectional pathing works with Dijkstra, but is a very bad idea with A*.  Saw a paper on that a while back.  Basically, with Dijkstra and given path costs that are the same in both directions, the first intersection point is guaranteed to fall on an optimal path, constructed by joining the two half-paths (IE it gives you what you want).  With A*, the two paths frequently miss each other...one of them goes one way around a boulder, the other goes the other way.  I think you can prove that the first intersection is still an optimal path with bidirectional A*, but in wide open areas (where A* excels) you'll frequently almost double your computation cost.

A common worst-case scenario is:  Imagine two points on a flat plain that are seperated by 1000 units X and 1 unit Y.  The origin goes right 1000 units then up one; the destination goes left 1000 units then down one.

[Ampersand]

A common worst-case scenario is:  Imagine two points on a flat plain that are seperated by 1000 units X and 1 unit Y.  The origin goes right 1000 units then up one; the destination goes left 1000 units then down one.

I think the one problem that could come from this is, if bidirectional pathing is used, the point where the two overlap will not be the midpoint between them, if as I suggested, both cores of a given processor were used in concert, as one would be more heavily burdened by Dwarf Fortress's other calculations. That may or may not cause problems, probably not for an individual dwarf. The problem, I'd guess, is keeping a given job pair concurrent with it's proper partner.

[worldspawn]

I'd still like to know how Toady makes all this work on multiple Z levels. I've created simple apps using A* before but it was all on a 2D plane.

[Ampersand]

I think it's relatively easy when you abandon the idea of Dwarf Fortress being 'really' 3D, and being more of a 3D hologram of a 2D world. The Z layers are completely independent of each other on a single 2D plane, where staircases act as teleportation points between these planes.

This is still an oversimplification, I think, as dwarfs seem to calculate distance between objects and themselves with a sphere that disregards all boundaries.

[Hawklaser]

I wonder how hard it would be to make a new constantly changing variable pathing cost system? As I noticed a trend with the A* and DijkstraI, even if a tile was farther away on the map, it would still check them in an order based off of path cost. And for a game that uses winding tunnels all the time, it would pay to give the correct shorter paths a lower value to speed up future pathing. I think a variable pathing cost formula would have to work something like this at the simplest.

Tile cost= (Iinitial cost - times pathed over, set up in a way so it does not go negative) + (X + 1)

And X would be so players could set up high and low traffic areas.

Now what would be interesting about this is, it would also kind of give the game a kind of habit memory. Would be interesting to see dwarfs forget to use your newly built tunnel due to old habits, or take odd routes if the common route gets closed. If could also add in variable adjustors due to other moving objects in the way, it would make having alternate paths useful, and would not make those new tunnels get forgotton for ever.

Another way to keep the game from locking in on just one path would be to have the Current cost get reset every so often but reset the more used tiles to a slightly lower cost so the game would still go through the quicker known paths first.

[Jifodus]

I'd still like to know how Toady makes all this work on multiple Z levels. I've created simple apps using A* before but it was all on a 2D plane.

Just remember that A* can work with arbitrary graphs. All a node needs is a cost and a way to estimate the cost from the node to the goal.

[corvvs]

A common worst-case scenario is:  Imagine two points on a flat plain that are seperated by 1000 units X and 1 unit Y.  The origin goes right 1000 units then up one; the destination goes left 1000 units then down one.

I think the one problem that could come from this is, if bidirectional pathing is used, the point where the two overlap will not be the midpoint between them, if as I suggested, both cores of a given processor were used in concert, as one would be more heavily burdened by Dwarf Fortress's other calculations. That may or may not cause problems, probably not for an individual dwarf. The problem, I'd guess, is keeping a given job pair concurrent with it's proper partner.

A good optimization may be to stop computation when the result is "good enough." I.e. calculate the absolute Cartesian distance between the beginning and end points and if the first path found is less than (distance * 1.75 or so) use it. Otherwise, continue to search.

Winding tunnels will often still have to calculate the entire A* set, but most common cases will stop faster, freeing up more CPU cycles per frame to do the complicated bits.

[eerr]

we keep looking for more and more efficient pathfinding.

but what we should be looking for is what dwarves would walk on a day to day basis, ie: what path will they usually follow, not what is always most efficient!.

now, in times of danger speed is the utmost importance.

but for day to day things, even real people rarely recalculate the entire path from a to b.

[bhelyer]

we keep looking for more and more efficient pathfinding.

but what we should be looking for is what dwarves would walk on a day to day basis, ie: what path will they usually follow, not what is always most efficient!.

now, in times of danger speed is the utmost importance.

but for day to day things, even real people rarely recalculate the entire path from a to b.

That is path caching, and part of making path finding more efficient.

[Impaler[WrG]]

For thouse interested in path finding, the A* implementation in that Java applet is just Terrible, on open ground A* should go strait towards its target and check hardly any nodes at all, this implementation is queuing hundreds of unnecessary nodes and checking almost as many nodes as Dijkstra.  It's only someone school project so its not surprising the implementation is poor but don't let this confuse you as to how efficient a real A* implementation is, it is in fact orders of magnitude better then Dijikstra and should be used in any instance UNLESS site-to-site teleports are on the map, only Dijikstra can deal with teleporting.