Rover Recursive Pathfinding

Rover was a college pathfinding project: give a rover a start, a destination, and a tile map, then find a route between them. The assignment called for recursive search over a 1024 × 1024 map. I worked on the traversal algorithm and the map representation, with a visual display of the rover’s progress.

Which direction comes first?

The search grows a route one tile at a time. At each position it tries an unvisited, traversable neighbor; when there are no more options, it backtracks. That leaves a useful decision: in what order should it try the four directions?

I used the distance from the current position to the destination along each axis to choose an instruction order. Directions toward the goal come first. The larger of the horizontal and vertical differences decides which axis gets priority, while the remaining directions determine how the search explores around obstructions.

Changing that order can change both the amount of exploration and the route found. I compared several orderings on two maps, recording total moves and final path length in a spreadsheet. Those are separate quantities: a short search can still find a long route. This is depth-first traversal, so the first route found carries no shortest-path guarantee.

Unwinding without losing the search

A long route also means a deep chain of recursive calls. The implementation divides that work into segments. When it reaches a configured recursion threshold, it saves the current path segment and unwinds the calls. The outer search loop transfers those coordinates into a container and resumes from the saved position.

The active example uses a threshold of 1,500. This makes the continuation state an explicit part of the algorithm, alongside the visited tiles and the partial route. It also makes the configured threshold and available memory relevant; the implementation should not be read as an unrestricted stack-safety guarantee.

Sixteen tiles in one integer

The map stores tiles in 4 × 4 regions. Each tile uses two bits, giving sixteen tiles per 32-bit integer. The four values cover the terrain states and visited ground. Reading or changing one tile means calculating its bit offset and applying a mask.

For a 1024 × 1024 map, the tile values themselves occupy 256 KiB, before surrounding objects and search state. I liked the bit manipulation as much as the storage problem. Packing the map and limiting recursive segments address different parts of the implementation; the compact map does not, by itself, reduce the depth of the search.

The original maps, specification, and instruction-order spreadsheet survive with the project. The linked articles go into the direction-order experiment and the bit-level map access in more detail.