2
\$\begingroup\$

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.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – LLL79
    Jul 9, 2013 at 7:31
  • \$\begingroup\$ You might want to read this: stackoverflow.com/questions/1332466/… \$\endgroup\$ Jul 9, 2013 at 7:49
  • \$\begingroup\$ 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 ). \$\endgroup\$
    – Sidar
    Jul 9, 2013 at 16:08
  • 1
    \$\begingroup\$ Oh btw, there is no difference between rectangular or hexagonal grids. The only thing that should be done different is retrieving the neighbours. \$\endgroup\$
    – Sidar
    Jul 9, 2013 at 16:55
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 9, 2013 at 18:04

3 Answers 3

13
\$\begingroup\$

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 should perform faster on average than Dijkstra's, and (despite your claim) their final results will be similar or the same.

\$\endgroup\$
0
1
\$\begingroup\$

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

\$\endgroup\$
-1
\$\begingroup\$

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.

\$\endgroup\$
4
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ Jul 9, 2013 at 15:22
  • \$\begingroup\$ upvoting for JPS, looks like a very nice specialization of A* to grid maps. \$\endgroup\$
    – Jimmy
    Jul 9, 2013 at 22:55
  • \$\begingroup\$ @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. \$\endgroup\$
    – Will
    Jul 12, 2013 at 21:48
  • \$\begingroup\$ It doesn't really matter which "feels" better in this case, Dijkstra is just not the best choice for point to point searches because of the massive performance implications on large grid-maps, which OP wants to use. And if you need a 99.9% Dijkstra-like behavior you can set the A* heuristic-weight to 0 any time. The remaining differences will be small and implementation-dependent and definitely not algorithm-dependent: A* - Wikipedia \$\endgroup\$
    – VaTTeRGeR
    Feb 20, 2019 at 10:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .