Sectorizing a pathfinding map for hierarchical pathfinding

When you implement pathfinding on a 3D map you quickly realize that sending a request for a destination on the other side of even a relatively small 64*64*8 (32,768 tiles) map, like the one presented, can take too much time, and the size of the pathfinding map in MBs prevents scattering it to multiple processors for multiprocessing. That makes hierarchical pathfinding a necessity.

In hierarchical pathfinding the tiles are distributed in sectors of a set size (in this case, 16x16x8). An algorithm finds the regions of contiguous accessible land for every movement capability, and another calculates each region center from the center of mass of its region. When hierarchical pathfinding is implemented, a first pathfinding query figures out if movement from a region to another possibly very far away is even possible at all, but does so by querying a much, much smaller number of coordinates (mostly the region centers). If the path is possible, a list of coordinates is calculated from the closest region center from the origin to the closest region center from the destination. Regarding the low level pathfinding map that holds the information about neighboring tiles for 32,768 ones, a pathfinding query is only calculated from a region center to the next one, limiting the neighbor queries to an average of about 16 each time.