Path finding: What would Kirk do?

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.

With diagonals, if we aren't careful, objects can pass through two objects that meet at their corners.

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:

2D path finding without diagonals. A monster following this path in the naive way would turn down, right, down, right,... making it seem 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:

Path finding in a hexagonal coordinate system.

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.

This entry was posted in Coding, DBP2011, XNA and tagged , , , . Bookmark the permalink.

3 Responses to Path finding: What would Kirk do?

  1. Timmy says:

    I would like to say thank you a lot for the job you have made in writing this article. I am hoping the same top job by you in the future as well.

  2. Caleb says:

    You could stick to the square grid and calculate your path without using diagonals, then when the path is done, you could smooth it out by replacing the ‘blocky’ movement with diagonal movement. I.E. the right-and-then-down would be replaced with a diagonal-down-right (checking that there isn’t a block occupating the square directly underneath it, unless you want your paths to be able to sneak around corners without going on the tile at the corner of the obstacle)

  3. olhovsky says:

    Actually that’s a pretty good idea Caleb.

    I haven’t touched the pathfinding in a while, and I wound up using a hexagonal map for coarse first pass pathfinding, and then a rectangular map for second pass detail pathfinding, using cubic splines to smooth paths.

    I’ll try implementing your idea, and see how it turns out.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>