I have finished integrating a scene partitioning scheme into my level editing workflow. On a separate layer of the map, you simply draw rectangles. The rectangles are loaded into the map as separate sections, and path edges are created between any rectangles that are touching. I don't have hierarchical pathfinding set up yet, but to test that this is working, I have configured the agents to, on maps that HAVE partitions, pathfind ONLY using the partitions, ignoring the tile layer. The algorithm is, for every section on the path between the start and end sections, walk to the center point of the section. For the last section, just walk to the destination point (which should be in there somewhere and accessible from the previous section). It should work pretty well, except I'm finding my agents are getting stuck in weird places - the generated path is fine, but following it is messed up. I'm pretty sure this is an unrelated bug - perhaps the walking doesn't work well if the destination point is too far away.

I've thought a bit about how to do it, and realized adding hierarchial should not be too difficult - I already have hierarchial logic in the behavior tree. I just would add a node above the point to point which goes through each section in a section path. Current logic looks like this:

*generate path
 *for point in path
  *go to next point

New logic will look something like this:

*generate section path
 *for section
  *generate path to next section
   *for point
    *go to next point

The tricky bit is encoding which tiles are actually in the section to constrict the search, and which tiles to aim for when heading to the next section. Going from center to center is fine for my experiment, but in the real thing that's insufficient. Sections should be able to contain walls, and they will need to pathfind around those walls when they reach the section. I need to pick the tile on the EDGE of the section that is closest to us. Sigh math.

To speed up pathfinding, I'm looking into hierarchial pathfinding. Since some of my scenes are quite large grids, and I'm eventually going to need to pathfind between maps as well, I'd like something that at a general level lets me layer sections into pathfinding to be more efficient. Tiles will be in sections, sections will be in maps. Basic algorithm is as follows:

# start - (tile position, section, map)
# end - (tile position, section, map)
if start.section == end.section:
    return astar(section.grid,start.position,end.position)
if start.map == end.map:
    return astar(map.sections,start.section,end.section)
return astar(map_grid.maps,start.map,end.map)

Sections will be created inside of each map, probably by hand to start with as something I can paint in tiled, including places where sections connect. When astar is run on sections, it will need to both find a path from the start to the end section, but also return paths within each section in order to generate the path through the individual tiles. For optimization, I could preprocess these paths and save them. Another approach would be for the ai to constantly be shifting which level it is searching based on where it is in following the path. So once he reaches the boundary between sections, he does another small astar search on the tiles to get across that section.

The biggest benefit to this, is a huge optimization for when I close off parts of the environment. When you move a rock in front of the path blocking an ai in a room for instance, that ai will know that he can't get out of the room, and not try to pathfind like crazy to find an exit. A smaller benefit is much quicker pathfinding if there are many units trying to travel long distances across the map.

Also map transitions is something that I handle very hackily right now. I still need to fix the path following algorithm, lol.

Currently the pathfinding in my game understands which areas are walkable and which ones are blocked based on collision tiles which are drawn on the map in the tile editor (for which I currently use the excellent Tiled). This is great, but it doesn't well handle dynamically placed objects. I took a stab at writing an efficition class to lookup which tiles are blocked taking into account dynamically moving objects. I plan to eventually evolve it into some sort of quadtree-like structure, and dump the tiles in there as well.

I tried to actually hook the space class up to the pathfinder, but didn't have time to actually make it functional yet. Very close!