Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 13 down vote favorite
2

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.

share|improve this question
3  
Methinks you should use whatever suits your gameplay ;) – Andrew Russell Sep 6 '10 at 14:53

3 Answers

up vote 16 down vote

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.

share|improve this answer
3  
+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. – Joe Wreschnig Sep 6 '10 at 14:58
1  
+1 for the sentence "Square grids are more accessible to the mass market (hex boards tend to look "geeky")" :D – Kornel Kisielewicz Sep 6 '10 at 15:32
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. – AttackingHobo Sep 6 '10 at 19:30
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. – Mike Strobel Sep 27 '10 at 20:34
3  
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. – Asmor Nov 5 '10 at 20:22
up vote 3 down vote

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.

share|improve this answer
up vote 2 down vote

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.

share|improve this answer
5  
"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. – Ian Schreiber Sep 6 '10 at 14:40
Touche. You're totally right; of course diagonal connections would be likely. – Gregory Avery-Weir Sep 6 '10 at 15:29

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.