I’ve been learning about using sparse voxel octree for 3d pathfinding based on Daniel Brewer’s chapter in Game AI and his talk at GDC 2015.

One aspect that I’m really confused about is exactly what is considered to be a neightbor of a cell in the tree, and whether using Manhattan distance is alright or not. Let’s assume that all the cells are of the same size and consider some cell C. How many neightbors will it have – 6, one for each side of the cube, or 27-1=26, all the cubes “touching” our chosen cell at least in one vertex?

It seems the former 6, but I don’t see how that doesn’t cause problems if we calculate distances between centers of the cells – it induces a manhattan norm, and there’s lots of situations where that fails. I have some intuition why it might not be an issue if you do some type of “post processing” on the found path, but it could simply fail quite badly in finding a good path.

Brewer has mentioned using Manhattan distance throughout the talk as well to allow for easier computations, but: 1, it seems like a very problematic thing to me and 2, it seems to me like Manhattan distance is already being used when moving across neightboring cells of same size, which I would assume where the bulk of the expensive computation happens.