I read some about quadtrees, and I am trying to take advantage of them for pathfinding. To this end, I am trying to use a quadtree to create a connected graph, where each "minimum rectangle" (a childless node) is directly connected to its adjacent minimum rectangles. To illustrate... if you take a look at the bottom-right rectangle in http://en.wikipedia.org/wiki/File:Point_quadtree.svg, that rectangle is a childless node in the tree, and it should be directly connected to the three rectangles surrounding it, which are also childless nodes.
Creating the quadtree is pretty easy, but I'm not sure how to detect connections with it. Can anyone offer me some insight?
Thanks in advance!
The bottom right rectangle is just a child of the adjacent 3 rectangle. Look from above at it like a pyramid when you are standing at the top and look how the quadtree divide the space recursivley into 4 directions. here is a better explanation http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves