Nitty Gritty on the QuadPathFinder

I've been side-tracked for around a month (!) getting pathfinding working. Today I integrated what I hope to be the final version of the path finder for the Appalachia (tentative title for the scene with "Jed") project. It uses a standard grid-style A* algorithm with a special method for finding adjacent nodes.
When I completed the first version of the path finder, I had a plain A* algorithm that used a grid of 2d integer coordinates, and it worked great as long as the search space involved was small. However, when I made the grid of nodes match the map in pixels, it stopped being feasible, because the number of nodes requiring traversal in a map without obstacles alone scaled linearly with the distance in nodes from start node to goal node. I hadn't planned on it costing so much when I implemented it, but I'd overlooked the cost at each node of finding out if each adjacent node was already in the closed or open node lists (see A* on Wikipedia for an explanation.) Even using a binary index, checking for the existence of a node in a list costs O(log (n)) where n is the number of nodes in each list, which meant the overall runtime would be O(n*log(n)) where n is the distance in nodes from start to goal. This really hurt performance on my netbook, bringing it from about 60 fps to 30. To alleviate the problem, I started using a variable grid-size so I could vary how many nodes the path would search by, for example, treating a group of 3x3 group of nodes as a single node. That meant there were a lot fewer nodes to search. The resolution would vary with the distance from begin to goal to keep the number of search nodes in check while controlling the cost of searching. This didn't work as well as I wanted though because it's possible to find no path at a larger node size when there actually is a valid path available (although it'd require a smaller node size to find.) I tried some variations on the same algorithm, but decided it wouldn't work after all.
While looking for solutions online, I found a tutorial on gamasutra about using a navigation mesh for pathfinding [http://www.gamasutra.com/features/20020405/smith_01.htm], which looked like it'd take more time to implement than I'd like to invest, so I didn't end up using the idea, but the article described a technique of "sectorizing" the nodes in a search space to effectively consolidate nodes without losing the ability to treat the search space as a grid. This seemed like a really useful technique that would work well with existing code, so I prototyped a version called QuadPathFinder that subdivides the search space in a manner similar to the way a quadtree. When looking for the nodes adjacent to a given node, the algorithm quadrisects the search space until it finds a square area without any obstacles and, instead of treating each unit square within as a node, only considers the squares on the inner perimeter of the area, which are all then considered nodes adjacent to the given node. That meant instead of the adjacent nodes of coordinate x,y being (x+1,y) (x,y+1) (x-1,y) and (x,y-1), the adjacent nodes become all the nodes on the inner perimeter of the largest obstacle-free area containing the given node. What that means is we can skip all the intermediary nodes between the given node and its adjacent nodes. So in a square area without obstacles, instead of searching n*n nodes, where n is the width of the area, we only need to search 4*n-4 nodes (the number of nodes that make up the inner perimeter of the square area.) That ends up saving a ton of time when searching large areas without obstacles, as is the case in the Appalachia project. This does require one last step when creating the final path though: while tracing the path from goal node back to the start (after the algorithm's found a valid path), the missing nodes we skipped need to be recreated, since we didn't add them when looking for adjacent nodes. In this step, the QuadPathFinder uses a variation on Bresenham's algorithm to figure out the coordinates of the skipped nodes.
This algorithm seems to be good in places where there are lots of empty spaces, but is probably bad in maze-like maps with small areas that can be traversed. Another important thing to note is that the algorithm doesn't account for the cost of traversal through each node; a node can either be traversed or not, a big difference between it and the standard A* algorithm (but one that doesn't matter for Appalachia.)
Hope this has been interesting and possibly of use to you!