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.

In a grid-based tactical game (think Fire Emblem), would A* or Dijkstra be more proper for finding a path to use for enemy AI to determine the best place to move?

A* has a better performance that Dijkstra, however Dijkstra may offer me better/smarter looking results for an AI.

If possible, I'd like to have the answer for both a hexagon based grid, and a rectangle based grid, if it'll make a difference.

share|improve this question
2  
Unless your map is huge, the performance gain of A* will be negligible. Unless your heuristic weights are way off, the accuracy of Dijkstra won't be notably better than the A* path. Whichever one you're more comfortable implementing is the more proper for a reasonably sized grid, square or hex. –  LLL79 Jul 9 '13 at 7:31
    
You might want to read this: stackoverflow.com/questions/1332466/… –  sm4 Jul 9 '13 at 7:49
    
For a smarter path finding solution ( not saying it's better, it sure did help me ) I added information to my units, an A-star aspect if you will, allowing me to dictate the cost and the density (walkable/solid) of each tile per unit ( or a collection of units ). This way I was also able to setup different behaviors/rules for my A.I. AND player. When my A-star algorithm looks for a path it check against the values i've set for the current unit. Thus creating shortcuts ( unitX CAN walk trough lava ) or long routes if a certain area is prone to enemy attack ( in combination w influence maps ). –  Sidar Jul 9 '13 at 16:08
1  
Oh btw, there is no difference between rectangular or hexagonal grids. The only thing that should be done different is retrieving the neighbours. –  Sidar Jul 9 '13 at 16:55
    
If you have a heuristic in your computation you can start with the basic weight function, but afterwords you can modify it to make your AI do fun things like swarm to the sides of the enemy rather than head on. A* wins all the way. –  Alex Shepard Jul 9 '13 at 18:04

3 Answers 3

up vote 10 down vote accepted

A* is just Dijkstra's with a heuristic to speed up pathfinding. Both find an optimal path; neither generates "more realistic" paths than the other. They can both be tuned to prefer straight lines or zig-zags, as you prefer.

If you have a decent heuristic (which you will for grid and hexagonal graphs), there's no reason not to choose A*. It will always perform as fast or faster-than Dijkstra's, and (despite your claim) their final results will be similar or the same.

share|improve this answer
    
Thank you for the clarification. –  Robert 'Jet' Rowe Jul 9 '13 at 18:02

If you can tolerate a little pre-processing, consider ALT with the 4 map corners as landmarks. Use Dijkstra from the 4 corners to generate landmark distances at every hex. When I implemented this on my 760 x 420 map Bidirectional ALT ran 80 * faster than Bidirectional A*.

Here is an Open Source implementation: Hexgrid Utilities for Board Games

share|improve this answer

Its subjective which feels better. You're the best judge of that; implement them both, and switch between them. And from then on only revisit the code with an eye to optimisation if its 'hot' in profiling!

If you are making a game with a large number of moving units then the speedup of Jump-Point-Search can be well worth it (empirical anecdotes from games like MegaGlest and 0ad).

Another key optimisation in my own hobby games has been to also have a 'reroute' function - when a unit hits an obstacle (e.g. a moving unit or a newly-placed building) it works out how to most efficiently rejoin its existing route rather than create a new route to the destination. There are nodes in the existing path just a cell or two away, typically.

share|improve this answer
3  
A* vs Dijkstra's is not as subjective as it sounds. The two algorithms are closely related, and there are lots of facts that we can use to form our answers. –  John McDonald Jul 9 '13 at 15:22
    
upvoting for JPS, looks like a very nice specialization of A* to grid maps. –  Jimmy Jul 9 '13 at 22:55
    
@JohnMcDonald well in my limited experience they do look and feel different as Dijkstra's shows any bias in your iteration order and priority queue e.g. will follow a wall and cross the room at the end where A* is going to be more of a Bresenham's line. And an A* that overestimates may not be optimal but sometimes that's useful and so on. So I read these implementation leaks into the author's question. –  Will Jul 12 '13 at 21:48

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.