Without trying to put anyone down, Wrathgame's algorithm is just Breadth-First Search (commonly abbreviated to BFS) and is one of the slowest of the pathfinding algorithms. Although it is guaranteed to find a path, if one exists, it doesn't make any use of extra information you provide about the map or the start/end points. This is why the A* algorithm is generally better, as it employs a heuristic (estimation function) to 'guess' which the best direction is. As a comparison using the example given, instead of generating a load of 1s, then searching them all to generate a load of 2s, then 3s and so on, it generates a load of 1s, then picks the best 1 to generate 2s, then picks the best 2 and generates 3s from it, etc. This tends to direct the search towards the target in a far more efficient manner, providing the heuristic is.

BFS is a good solution in a game where the number of nodes won't get too big. Examples are small maps (less than 20x20, I'd say) or maps that are generally tunnels rather than open spaces (Pacman as opposed to Command and Conquer). For other maps, something like A* is preferable, although slightly harder to code.

(PS: The choice of algorithm is actually irrelevant to Abaddon_db's problem. It will still generate 'broken' paths no matter whether you use BFS, DFS, A*, Dijkstra's, or any other pathfinding/node-based algorithm. The problem is that, for any given node, the list of candidate neighbouring nodes generated is wrong. This is because it's being treated like an offset grid, when in fact it needs to be treated more like a rotated grid, which is something Wrathgame did actually point out.)

Edited by - Kylotan on August 10, 2001 10:37:13 PM