Is there any significant difference between using a square or hexagonal grid for the area searched by a path finding algorithm. In other words, is square or hexagonal better, and if so why.
\$\begingroup\$
\$\endgroup\$
1
-
4\$\begingroup\$ Methinks you should use whatever suits your gameplay ;) \$\endgroup\$– Andrew RussellCommented Sep 6, 2010 at 14:53
Add a comment
|
4 Answers
\$\begingroup\$
\$\endgroup\$
6
The main consideration for deciding whether to use square vs hex grids shouldn't be ease of AI implementation -- breadth-first and depth-first search algorithms are pretty much the same no matter what kind of graph you have.
Rather, this is a gameplay issue that should be considered by the game designers. Square grids are more accessible to the mass market (hex boards tend to look "geeky"), and in a world of up/down/left/right controls it's a lot more intuitive to navigate around squares than hexes from a UI standpoint. Square grids also tend to restrict movement a bit more; assuming orthogonal movement (and not diagonal), it takes 4 moves to walk around a one-square obstacle, compared to 3 moves in a hex grid. From a programming standpoint, hexes are also a little bit easier to implement but it's not about search algorithms as much as that a square grid equals a two-dimensional array, but a hex grid doesn't really map to a standard data structure.
The down side of square grids is that the movement never feels right. Moving diagonally should take sqrt(2) movement points, but in practice it's either 1 movement (which makes it feel like walking on diagonals is fast and there's rarely a reason to walk orthogonally) or it's 2 movement (which makes diagonal movement feel too slow). With hex grids, movement distance is a lot more intuitive, as it's always the same distance from one hex to another no matter which path you take.
-
4\$\begingroup\$ +1. This is a design decision, not an AI decision. If you do want hexagonal grids, an offset-square grid like www-cs-students.stanford.edu/~amitp/game-programming/grids/… may be less intimidating to casual players, and it's mathematically equivalent to hexagons. Also, it's a convenient in-memory representation as well. \$\endgroup\$– user744Commented Sep 6, 2010 at 14:58
-
2\$\begingroup\$ +1 for the sentence "Square grids are more accessible to the mass market (hex boards tend to look "geeky")" :D \$\endgroup\$ Commented Sep 6, 2010 at 15:32
-
\$\begingroup\$ Edwin is not asking what is better on a grid based game. He is asking what is better for the AI to use square or hexagons. The world and gameplay itself does not have to be constrained to those, only what nodes the AI is searching on. \$\endgroup\$ Commented Sep 6, 2010 at 19:30
-
\$\begingroup\$ I've implemented turn-based strategy games with both hex and square grids, and there is absolutely no necessary difference in terms of pathfinding complexity. I even switched one game from a hex map to a square map, and (apart from the rendering) the only change I had to make was to a MapLocation::GetDistance() method which computed the distance between two sectors. I simply had to adjust the calculations to deal with every other row being offset slightly. In both cases, you can use the same in-memory representation. So, as the others have said, it's really a design issue. \$\endgroup\$ Commented Sep 27, 2010 at 20:34
-
4\$\begingroup\$ Just an aside, hexes can be mapped to a 2-dimensional array. Picture a square grid, then shift every even column half a step down. You've got an offset square grid now, which is isomorphic to a hex grid. \$\endgroup\$– AsmorCommented Nov 5, 2010 at 20:22
\$\begingroup\$
\$\endgroup\$
2
I'm not an AI expert by any means, but the difference should be negligible. Square grids are a bit faster (4 connections per node instead of 6), but that's really not the limiting factor in the algorithmic runtime. Depending on what algorithm you're planning to use, the code might be a bit more complex for a hex grid, since it's a bit more complicated to calculate coordinates, and it's harder to use the sort of quadtree/octree shortcuts that I believe are often used in pathfinding.
But for a simple world like a turn-based-strategy game level, the difference between the two layouts shouldn't matter much; a square grid will be slightly simpler and faster.
answered Sep 6, 2010 at 13:00
-
6\$\begingroup\$ "Square grids are a bit faster (4 connections per node instead of 6)" - unless you can travel along diagonals, in which case it's 8 connections vs 6. \$\endgroup\$ Commented Sep 6, 2010 at 14:40
-
\$\begingroup\$ Touche. You're totally right; of course diagonal connections would be likely. \$\endgroup\$ Commented Sep 6, 2010 at 15:29
\$\begingroup\$
\$\endgroup\$
There's one practical difference i can think off regarding path planning. Traversing from the center of an hex cell to on of its neighbors is always the same distance whereas, if you a allow diagonal travel, this is not true for squares.
\$\begingroup\$
\$\endgroup\$
This guide on hexagons is awesome. The part about pathfinding has an interactive example and some info on how to adapy square pathfinding.
If you’re using graph-based pathfinding such as A* or Dijkstra’s algorithm or Floyd-Warshall, pathfinding on hex grids isn’t different from pathfinding on square grids.
- Neighbors. The sample code I provide in the pathfinding tutorial calls graph.neighbors to get the neighbors of a location. Use the function in the neighbors section for this. Filter out the neighbors that are impassable.
- Heuristic. The sample code for A* uses a heuristic function that gives a distance between two locations. Use the distance formula, scaled to match the movement costs. For example if your movement cost is 5 per hex, then multiply the distance by 5.
