A* Pathfinding

This A* implementation began as an experiment with data structures. I wanted to see how changing the containers behind the search affected its speed. The application generates a maze, searches for a route, and times the search, with alternative representations for its open and closed lists.

The work behind the next node

The pathfinder explores four orthogonal neighbors per tile. Each candidate combines the cost accumulated along its route with a Manhattan-distance estimate to the destination. Parent links keep enough information to reconstruct the route when the search reaches the goal.

The open list holds positions waiting for expansion. The closed list records positions already considered. Those names describe their purpose, but leave the storage decisions open: how should candidates be ordered, how should a position be found again, and what happens when the list changes?

Changing the containers

The implementation has vector and deque options for the open list, and map and vector options for the closed list. Preprocessor choices select the variants. The ordered-list operations use binary-position searches to locate insertion or removal points.

Finding an insertion position is only part of its cost. A container may also have to move elements, allocate storage, or perform another lookup later. That makes a complete search a useful workload for the experiment: it repeatedly mixes ordering, lookup, insertion, and removal rather than timing one operation in isolation.

The console driver generates maps, records their seeds, and prints individual and average search times. Retaining a seed gives a concrete way to return to a particular maze when comparing behavior. The generated maze and the search algorithm are separate parts of the application, so their responsibilities can be examined independently.

Correctness before a speed comparison

A separate checker compared the default pathfinder with an independent Dijkstra search on 102 bounded cases. The checks covered reachability and route cost, as well as endpoints, orthogonal adjacency, and traversable tiles. Those cases passed, and the unchanged console application built with CMake.

That check used a fresh process for each case. It did not cover every container configuration, repeated searches on one object, or map replacement. Those behaviors need their own checks before extending the result to the whole implementation.

The timing machinery survives, but no comparative results were recovered. I would need a controlled run across the variants to say which was faster on a given workload. The project’s useful technical focus is the connection between an algorithm’s operations and the containers chosen to support them; its source provides the variants and the harness for examining that question.