In my previous post about the challenge of path finding on the XBOX with XNA, my A* algorithm benchmarks were abysmally slow.
Recall from my previous post that pathfinding was done in 3D, including diagonal movement, allowing 26 possible directions of movement at each cell in the grid. To reduce this, we move to 2D pathfinding, since the 3D grid was very thin anyway, and introduce weights at each grid cell to account for almost-3D objects on the grid.
Allowing diagonals permits 8 movement directions. It also allows actors to circumvent obstacles by moving through a corner, when adjacent cells touching at their corners should block it.
To increase speed and avoid having to check for adjacent obstacles before moving through corners, we can use only 4 directions of movement. The problem with this is that monsters following a path defined by this movement look robotic:
One solution I proposed to this was to use minimal acceleration hermite curves to generate smooth paths between grid cell centers.
To find any alternatives, I asked myself, what would Captain Kirk do?
Then I remembered this: http://kirkfails.ytmnd.com/
While I might still need to generate these curves, in the meantime I have decided to take a different approach:
Using a hexagonal coordinate system will naturally produce smoother paths.
In the first diagram, the end position is 10 units across and 10 units down relative to the start position. In the hexagonal version, the end position is still 10 units across, and is 9.5 units down.
Notice that we can’t create a perfect analog of the end position, or of the obstacle locations. In this particular example, the chosen path in the hexagonal version took 12 steps, as opposed to 17 in the square coordinate system.
This was no coincidence. A circle inscribed in a square occupies 79% of its area. A circle inscribed in a hexagon occupies 91% of its area. So on average we expect to represent an equivalent square grid with a hexagonal grid using 11% fewer cells.
However, since the hexagonal version requires checking 6 neighbor cells at each step, a minimum of 102 cells were examined in the hexagonal path, as opposed to a minimum of 72 cell examinations (at 4 examinations per cell) in the square version.
Game Programming Gems 7 chapter 1.5 “For Bees and Gamers: How to Handle Hexagonal Tiles” makes the claim that you gain performance by using hexagonal coordinates, because fewer cells are needed to represent the same data as rectangular cells. However, other constructs are rectangular, and need to be mapped to hexagonal coordinates. For example RAM is rectangular. The terrain quadtree subdivides into squares, and the world octree or GGR grid is square. Mapping between rectangular and hexagonal coordinate systems has an associated time cost, and having to check 6 directions instead of 4 in the path finding is going to cost a little bit more. Of course, it’s likely that hexagonal pathfinding is going to be faster than 8 directional rectangular pathfinding.
In the end I expect performance to be similar, though we gain the benefit of more natural looking paths, since hexagons have the same distance between the center and any adjacent cell (as opposed to squares, where you must travel 41% further to a diagonally placed cell).
One of the themes in this game is hexagonal tiling. I use them in the menu, and the skill tree (yet to be implemented). You’ll even find hexagonal tiling behind the main character of the game in the title banner of the website right now (look at the red background closely). That said, using hexagonal objects in the game world is something I’ve been considering for a while now. If used, hexagonal path finding would make a lot of sense.
Hexagons tend to represent organic shapes well (like islands and rocks), and squares tend to represent manmade shapes better (like city buildings or the rooms of a house).
Since most of the objects in this game will be organic in nature, hexagons will work out well. If you are building a post-apocalyptic zombie game that takes place in New York, then maybe not so much (streets and buildings are rectangular).
So in the next couple of days, I’ll be extending my hexagonal coordinate class (already used for the hexagonal menu system), and then modifying the path finding to use it.