So at this point I had height factored into the system, awesome! The AI can find a path up a mountain without flying up the side, and can get back down without taking leap of faith. But here’s where things get messy. What happens if I cut into the mountain along the path ? Well with the system as it was it wouldn’t actually affect getting to the top of the mountain, which is great, who cares if there’s a crevice in the mountain if it’s not interfering with the path ?
Well what if it’s not a crevice, what if it’s a small cave ? What happens if the AI chases the player up a mountain and the player goes in the cave ? With the system as it was this would be a problem, logically we’d want to follow the player into the cave but as soon as they step into that cave the system would generate a path taking the AI to the top of the mountain, the x and z coordinates of the destination would match the player, but the node would exist on top of the mountain, not inside the cave.
In order to take these caves into consideration I needed to be able to generate stacks of nodes rather than one for each grid point, but adding a y dimension to the graph would break the system, I would no longer be working with anything close to A* and would effectively be inventing a brand new pathfinding algorithm, and I really couldn’t afford to do this.
So I thought about it another way, in most of the cases we had for Hex World, a stack was composed of solid tiles all the way through, air pockets were actually in the minority of cases here. So what’s the point in adding a whole dimension when it’s going to be used in maybe 10% of the stacks. Furthermore, just because a stack has an air pocket doesn’t mean that anything can fit in the pocket, meaning that air pockets don’t always need a node.
With these in mind I thought about what that meant, in most cases I would want one node to each grid position, in the event that an air pocket exists I might want an more than one node to that grid position and if a lot of air pockets exist I might want even more nodes to that grid position. So I thought maybe if each grid position stored a list of nodes that could fix the problem, I could iterate through the list as part of the algorithm until I reach the end and pick the appropriate node. So that’s what I did, changing the system to consider each grid position as a stack of nodes that need to be iterated through. When generating the stack a node is adding to the list, starting from the lowest air pocket we generate a node if the collider fits and add that node to the list, and progress up to the next air pocket until we reach the top of the tile stack where the last node will be added.
However this brought on a new problem, how does the neighbour array for each node work ? Well it could work the same way, since we already store the array and populate it at generation why not simply add the first node that can be reach from the current node.
So 3D A* came down to storing the correct node neighbours and storing traversal types to said neighbours. With some additional physics checks added to edge traversal tests (we need to know if something blocks us from jumping etc.) the system worked and pathing through tunnels worked!
This next video shows the agent pathing through a more complex map, the agent is no longer a cube, instead being an invisible object (can be made visible for debug purposes).