Pathfinding with Quadtrees and A*

For some reason, I've always be fascinated by spatial partitioning with Quadtrees.

However, when applying the A* algorithm to the structure, you have to pay an overhead due to the fetching of the current Quadtree's neighbors, which isn't done in O(1).

Of course I don't even consider A* on the single pixels, but then again I didn't want a classic subdivision in tiles of equal dimension, because many of them would be pointless: why partitioning a fully-walkable zone in many small tiles?

In this little experiment made with SDL2, I partitioned the walkable area with a Quadtree as an initial pre-computation stage, then I computed the neighbors for each Quadtree and finally applied A* on the resulting tiles.

Basically, the first step is passing an SDL_Surface to the partitioner: this image is simply a bit mask with black representing space and white representing void (see image below).

Now, thegetPixels method simply returns a monodimensional array of pixel values, by calling thegetPixel method (explained in the official SDL wiki) for each (x, y) of the surface.

Once obtained, the actual construction of the Quadtree can start:

We then stop recursively subdividing a Quadtree Q in 3 cases:

1. The area described by Q is completely white (unnecessary)

2. The area described by Q is completely black (fully walkable)

3. The area described by Q contains both black and white pixels but has already reached the minimum dimension allowed

This is exactly what the method mustBeSubdivided below does:

You can see how I'm also marking the type of each Quadtree so that, when we extract a graph of tiles out of it, we can only consider the fully black areas and discard the others.

The minimum size I've chosen for a Quadtree is 10.

Below is the resulting Quadtree visually represented, with blue EMPTY Quadtrees, red FULL Quadtrees and green MISC Quadtrees:

Now, how do we extract a Search Graph out of this Quadtree? There are several algorithms for neighbors finding in Quadtrees, but instead of using one of them I came up with another geometry-fashioned solution:

1. Visit the whole Quadtree and map each FULL Quadtree by x position and by y position both in ascending order;

2. For each Quadtree Q with x position Q_x, consider all the Quadtrees Q´ with x position Q_x + Q_width (possible eastern neighbors);

3. For each Q´, let Q_s and Q_b be the respectively the Quadtree with smaller width and the one with greater width between Q and Q´ (width might also be the same): if Q_s has a side that overlaps with Q_b, then Q´ is an eastern neighbor of Q and Q is a western neighbor of Q´;

4. For each Quadtree Q with y position Q_y, consider all the Quadtrees Q´ with y position Q_y + Q_height (possible southern neighbors);

5. For each Q´, let Q_s and Q_b be the respectively the Quadtree with smaller height and the one with greater height between Q and Q´ (height might also be the same): if Q_s has a side that overlaps with Q_b, then Q´ is a southern neighbor of Q and Q is a northern neighbor of Q´;

The method below executes step 1:

Also, note that explicit sorting of x and y elements in the maps is unneeded, since it's already being visited in a sorted order (NW, NE, SW, SE).

All remaining steps are executed by the following method:

Now I have a regular Search Graph: a small tool I developed allowed me to verify the neighbors (highlighted in blue) for each node (highlighted in green):

I will not show the code for A* itself, but a great explanation can be found here.

For costs and heuristics, I considered the euclidean distance between the centers of the tiles.

Now, let's see the results of the application of A* to this graph below:

We do have the shortest path from tile A to tile B measured in tiles, but of course we must still decide where to walk within each tile.

While the optimal solution can be obtained with raycasting, it is overkill and makes all this procedure useless (we could have applied raycasting to the single pixels in the first place).

So, first I tried to choose the midpoint of each common side between tiles, with a final result that I found acceptable. See below:

Now, pay attention to the three bigger tiles stacked together: what if we had a huge tile instead of them, 5 times larger? The solution wouldn't be acceptable anymore, because the path would divert to its center, making a detour that is not acceptable.

Instead, the best compromise I could think of is, for each common side, compute the euclidean distance from the goal of three "checkpoints" lying on the side: first endpoint, second endpoint and the midpoint.

Each time we traverse a tile, we choose to traverse the point with the smaller euclidean distance to the goal.

This was the result for the same path:

As you can see, the problem with a possible larger tile replacing the three stacked tiles has been solved.

This solution looks acceptable to me and a good compromise.

It's not as good as a path computed with A* applied on single pixels or with pure raycasting, but it's very close and less costly, provided the creation of the Quadtree and the Search Graph is done and saved earlier and the resulting tile set can be read as any other game resource/asset.