Path finding on hex maps

Right from the get go, I’m going to point you at red blob games, specifically this article but have a look at the whole site as there are some great path finding articles too… In particular the various algorithms dealing with hex grids are comprehensive and easy to understand, Amit I salute you!

If you’ve seen any of my recent posts, you won’t be surprised to see that we’re relying on the raylib library to deal with much of the boring minutia so we can get down to coding the fun stuff…

While using basically what amounts to A* path finding, which is commonly done on a square grid, I’ve found it useful to treat the hex map as a graph of nodes. When setting up the graph, each node (or hex) in the map has six possible exits (or vertices in a graph) as we build the graph, taking each of the six possible exits from a hex, we point them in turn to the appropriate neighboring hex, however if a hex is impassable (or outside the map) we set the exit leading to it as NULL, this way it is impossible for any path finding algorithm to reach impassable hexes.

This has the advantage that the path finding algorithm need not know anything about your game rules. For example in the code for this article, there are just two passable hex types, grass and bridge, the bridge however can only be entered and exited by traveling directly east or west.

The path finding code knows nothing about this, all it has to do is follow the links from hex to hex, if when we build the map graph we have included rules about bridges then that is automagically respected by the path finder. This makes the path finding code less complex and more general purpose, something you should always strive for when writing your functions, my path finding function actually originally came from a different project of mine, with minor massaging is slotted right into place…

One small draw back to this approach is that should you need to change the type of a particular hex, you will need to regenerate the graph for that node and its neighbors. Its rare you’ll need to change a map on the fly and in practice regenerating the whole graph for the map can be done quickly enough, so because I’m lazy that’s exactly what I do whenever a hex changes type.

The basic idea behind A* is to maintain an open and closed lists of hexes, you start off with your start point on the open list, you score an item on the open list by how much it actually costs to reach it from the start point and the estimate of how much it will cost to reach the goal (basically the straight line distance, called the heuristic), once you have added all this hexes neighboring hexes onto the open list you then move it onto the closed list. After the open list has been reordered by the heuristic score, you keep repeating this process until you reach the goal, considering the best scored hex on the open list each time.

Currently it only cost two points to move from one hex to another, for more complex maps you might want to make it cost more to travel over say rough ground (something like 2.2). However you will have to test how this behaves, and possibly multiply the heuristic by a factor to make it behave in a reasonable manner – its a case of experimenting and ensuring that given different start and end points work with changing terrain and that the resulting path looks sane.

One little bit of finessing I’ve added to the path finder is to compare the top two heuristic scores on the open list, if they are the same then there is a 50/50 chance that the second item is used instead of the first. The reason for doing this is that there are often multiple routes the same length between two points, this simple randomizing of the path, ensures that the path finder doesn’t end up having some odd biases, and having a bit of randomness in the behavior of your “AI” is no bad thing!

The example code with the post, shows a hex grid containing various terrain types. Moving the mouse around you will see that the hex under the mouse is highlighted, pressing S defines the start hex of the path (it will be highlighted in a different colour) Similarly the E key defines the end of the path. Once a start and end point have been defined, you will see a path highlighted between the two points. Pressing T will increment the tiles terrain value, remember that only grass and bridges are passable. Because the path is recalculated every time a tile is changed you can change a tile away from the path to see different routes chosen that are all the same length…

You can get the code here.

Leave a Reply

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