Walkable Surface Detection and 3d Optimized Dijkstra Pathfinding

This project is my version of baking a navmesh. This was created using physics casts and quadtree collision detection. The project starts with one large cubic physics cast. If it collides with something, it is divided into 8 equal parts (halving every side). This happens until an arbitrarily small size. This method is very inefficient, but I used it since it was simple to implement and it wasn’t the main part of the project.

The top surfaces were then selected by finding cubes that did not collide with an object, but that the cube underneath it did. All surface cubes then have a link created to all of the cubes next to them, in all directions.

The result of each surface cube being next to a collided cube is that almost all of them are of the smallest size. This means that if Dijkstra’s pathfinding was implemented using these cubes, then it would be incredibly inefficient. This solution to this is to combine cubes that are touching each other into larger cubes. The reason why the cube shape is preserved in this procedure is to guarantee proper pathfinding results when moving between cubes. This could be accomplished using a Voronoi diagram as well, but this implementation was meant to be more simple.

Baking the navmesh of the scene below takes around half of a second. This is due to the inefficient nature of physics casts.

The video below shows traversing the scene without any of the grid visible and then with it visible. The colors of the cubes represent the size of the grid that they are a part of. The order from largest to smallest is grey, dark blue, light blue, green, red, and white. The verticle lines sticking up from the adjacent grids are the center of those grids. These represent the options that the Dijkstra’s algorithm chooses from when deciding the best path. The adjacent grids have related weights referring to their distance from the grid the algorithm is currently processing and their distance to the destination. The actual implementation of Dijstra’s algorithm was never completed as interest in the project faded. This is due to Dijstra’s pathfinding algorithm being extremely simple to implement and is thus not a very interesting project to pursue.