Whats the difference between node-based pathfinding algorithm and the A* among others?
A friend just told me about node-based, but I cannot find much tutorial or information on it.
\$\begingroup\$
\$\endgroup\$
13
-
\$\begingroup\$ Would your friend be talking about Dijkstra's algorithm? It's such a good node-based pathfinding algorithm that internet routing runs on it. \$\endgroup\$– doppelgreenerDec 23, 2010 at 5:42
-
3\$\begingroup\$ @Axidos: Dijkstra's is uninformed A*; if you can come up with any heuristic, A* is better. \$\endgroup\$– user744Dec 23, 2010 at 10:53
-
\$\begingroup\$ @Joe Wreschnig: So it is! I didn't realise that - thanks for giving me a reason to investigate! \$\endgroup\$– doppelgreenerDec 23, 2010 at 12:13
-
1\$\begingroup\$ Dijkstra is basically A* without heuristic. Using Dijkstra is really useful if you want to find the nearest item of type X. Eg. your Bot is looking for the nearest ammo-crate, then Dijkstra's will find you the nearest one. \$\endgroup\$– bummzackDec 23, 2010 at 14:24
-
1\$\begingroup\$ bummzack: I'm proposing h(x) = min(map(x.dist, ammo_crates)). I'm not changing the goal at any point during running the algorithm - I'm defining the goal to be the nearest ammo crate, rather than specifically the Euclidean-nearest crate. The whole point of A* is that once g(x) > g(y) + h(y), it's going to start exploring down y no matter how small h(x) is. \$\endgroup\$– user744Dec 25, 2010 at 23:57
|
Show 8 more comments
3 Answers
\$\begingroup\$
\$\endgroup\$
0
My AI is rusty, but it sounds like your friend is describing a common approach to defining the environment for the pathfinding: explicitly or algorithmically define a set of discrete nodes that agents can travel between in a network. Once you've got that node graph, you can run any algorithm you want on it, including A*.
A* can be run on a grid (which is really just a very regularly-spaced set of nodes) or a terrain mesh, too. Making a node graph is just a way to simplify a complex pathfinding situation by defining possible paths through an area.
Of course, there may be a definition of "node-based pathfinding" with which I am unfamiliar.
answered Dec 23, 2010 at 3:47
\$\begingroup\$
\$\endgroup\$
0
A* is node-based. In fact, the only difference between A* and depth-first, breadth-first, uniform cost and every other graph search algorithm is how they determine the next node to visit. Using a stack, queue, priority queue based on cost from start, and a priority queue based on cost from start plus estimated cost to goal yields DFS, BFS, uniform cost and A* respectively.
Graph search algorithms, especially A*, sound all mysterious until you grok what I said above - then they all become obvious. I plan to write a set of articles for my blog exploring this topic in depth.
\$\begingroup\$
\$\endgroup\$
1
Dijkstra's algorithm gives the correct answer on any grid of nodes, and exaustively finds the best route. If you have a small number of pre-populated nodes on your map (e.g. you placed them in your editor) then there are probably sufficiently few that it works fine.
On the other hand A* uses a "distance function" (typically manhattan distance or something) to optimise Dijkstra's algorithm for the special case where you have a very large number of evenly spaced nodes, e.g. a grid - which is the normal case.
The A* algorithm can find the best route in a grid with some caveats regarding weights. For example, if you place a few teleporters on an otherwise grid-like map, A* can no longer work, as its "Distance funcion" doesn't give the right result, taking into account the teleporters.
But Dijkstra isn't efficient** on a big open grid either, because the number of nodes you have to consider gets big quickly. Dijkstra's algorithm is like a flood-fill - it always touches all reachable nodes. A* does not.
I'm not sure if this answers your question but I hope it helps.
** For a given defintions of "efficient" and "big".
-
\$\begingroup\$ That you choose a bad heuristic for your data doesn't make A* "not work" - it still does what it mathematically claims to. You just need to pick an admissible heuristic - like the minimum of the distance to the goal or the nearest teleporter - and it'll find the optimal path at least as fast as Dijkstra's. \$\endgroup\$– user744Dec 23, 2010 at 22:58