At this point I had a bog standard A* algorithm working in Hex World, not really that big of deal really but this is where I realised what the system was going to struggle with, a 3D environment.

Hex World isn’t just a flat series of tiles, the tiles vary in height, tile stacks can also feature gaps of air. How can a standard A* algorithm possibly path around these things ?

Well simple answer is that it can’t, but I didn’t want to just leave it or build a new more complicated solution from scratch, so I thought through how the algorithm could be adapted to take these problems into account.

At this point the system generated the node graph at run time using physics tests at each node to see if a collider would fit in the node, this information would come in handy later. The system also stored some vital information for each node, including what that nodes neighbours are. With this in mind I decided I could store the height value of each node and then incorporate height comparisons into the A* algorithm in order to discourage the system from creating paths that have drastic height changes from node to node. I thought that if I simply made the cost of a move become exponentially more expensive as the height difference increases that that would be enough.

It wasn’t, no matter how expensive a single move was it always beat out the cost of the path around the obstacle, so I had to rethink the problem. I looked at the problem in terms of what kinds of moves a character could make from node to node, they could either walk along a flat edge, step up or down a small height change, jump up a large positive height change, drop down a large negative height change and finally too much height difference means they cannot cross that edge.

Now with this in mind at each point of the algorithm in which I was checking the neighbours of a node the height difference would tell me what kind of move I could make, but I didn’t like the idea of doing this computation multiple continuously and multiple times for the same node, so I decided to compute it at generation and have each node store an array of traversal types. The index of this array corresponded to the index of the neighbour, in the neighbour array, that the traversal type referred to.

So with what ultimately became a simple addition to the algorithm I was able to use A* to path with height consideration with little performance impact!