Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
Would your friend be talking about Dijkstra's algorithm? It's such a good node-based pathfinding algorithm that internet routing runs on it. –  Jonathan Hobbs Dec 23 '10 at 5:42
3  
@Axidos: Dijkstra's is uninformed A*; if you can come up with any heuristic, A* is better. –  user744 Dec 23 '10 at 10:53
    
@Joe Wreschnig: So it is! I didn't realise that - thanks for giving me a reason to investigate! –  Jonathan Hobbs Dec 23 '10 at 12:13
1  
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. –  bummzack Dec 23 '10 at 14:24
1  
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. –  user744 Dec 25 '10 at 23:57

3 Answers 3

up vote 9 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
+1 This is the correct answer. –  Nick Wiggill Sep 10 '11 at 10:35

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

share|improve this answer
    
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. –  user744 Dec 23 '10 at 22:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.