Dijkstra Bug: Deadends and Really Bad Algorithms

Posted by santosj on April 23, 2007

I should point out that it isn’t the algorithm for Dijkstra that is wrong, because tests show that the algorithm does what is expected. It is the internals of the Abstract (Ai_Pathfinding_Abstract) which completes both the Dijkstra and, when finished, the A* algorithms. The only reason the first (and only) test was successful was because there were no “deadends” internally.

(Some days I wish I was more intelligent, such solutions would come easier than and such problems would never had existed.)

A deadend is where the algorithm comes across neighbor nodes that had already been checked or have higher fitness than the current node. What is happening is that a deadend is being found after each iteration, which isn’t supposed to happen. The “Solution”, which is wrong by the way, is to rewind back to any available node and start over from there. It explains why the algorithm will “jump” from one point to another, instead of the correct moving along to the next neighbor.

The correct solution has always been to save each node path and then then move back when a dead end was reached until the end was reached and save that and every path that completes. The solution involves a tree data type. The solution before was more a queue which was incorrect.

I’ll have to spend some time testing and developing a tree based solution. Should be fun. Also the internals will also have to be changed, the API won’t change. I’m thinking of breaking the algorithm into three methods, one for the algorithm specific code, one to build the tree, and the last one to traverse the tree and pick the correct path. I’m thinking of keeping all of the completed paths and allowing them to be accessed by the user. What this would allow is choosing the best path instead of the shortest.

Metrics

I need to think about adding metrics to the algorithm, which would help make it more complete. Right now the only metric is the distance between the node and the end node. There needs to also be metrics for depths (3D terrain heuristics), choosing “jumps” (wormholes, portals, etc), and different types of terrain (such as moving through water would be slower or faster for certain types).

My main focus was to first get the algorithms working and then go back and allow “advanced” features to be implemented. Not that I’ll be doing all of the work, or maybe I might, but really to allow others to go in and add their own metrics.

I think if I can get the tree done, I can do a better job of allowing metrics. The API would have to change when I do.

Possibly Related Posts:


Projects

Comments are closed.