Node-Based pathfinding vs A* and others

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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".