This project focused on implementing and evaluating the A* pathfinding algorithm within procedurally generated maze environments. A* is a best-first search algorithm that operates over a weighted graph, prioritizing exploration based on a combination of path cost and heuristic distance to a goal. While conceptually well known, a correct and efficient implementation requires careful handling of data structures, ordering, and edge cases.

The project was completed as part of coursework and intentionally built on a previously implemented maze generator. This structure made it possible to focus on algorithmic correctness, container behavior, and performance tradeoffs without conflating those concerns with generation logic.

Implementation and Design

The program allows users to specify the number of generated mazes and their dimensions, then runs each maze through an A* implementation to compute a path from start to goal. During execution, the algorithm tracks explored nodes and candidate paths, reporting both the resulting path data and the elapsed time required to find a solution.

After completing a working implementation, I extended the project to explore how different STL containers affected behavior and performance. Multiple variants of the algorithm were implemented, allowing the Open and Closed lists to be backed by different container types. New nodes were inserted into the Open list in sorted order based on combined cost and heuristic values, rather than relying on repeated full sorts.

This approach made it possible to compare container tradeoffs while keeping the core algorithmic logic consistent.

Objectives

The primary objectives were to implement a correct A* search algorithm, validate it using a previously developed maze generator, and explore how different STL containers influence performance and complexity. An additional goal was to gain a deeper understanding of ordered insertion strategies and their impact on search efficiency.

Challenges and Outcomes

One challenge involved debugging behavior that differed between container implementations. Code that functioned correctly with one container would fail under another, requiring careful reasoning about iterator invalidation, ordering assumptions, and ownership semantics.

Another issue surfaced when an edge case in the maze generator produced an unexpected segmentation fault during pathfinding. Identifying this problem required tracing failures across system boundaries rather than within the A* implementation itself, reinforcing the importance of validating assumptions about upstream data.

Despite these challenges, the project resulted in multiple functioning A* implementations and a clearer understanding of how container choice affects algorithm behavior more than raw asymptotic performance.

Results

The final implementation successfully computed paths through randomly generated mazes and supported multiple container strategies for managing the Open and Closed lists. While detailed benchmark data was not preserved, observed runtime differences between container configurations were modest, reinforcing that correctness, ordering strategy, and data locality often outweigh theoretical container advantages at this scale.

If revisited, the project would benefit from visualizing the maze and computed path directly, rather than relying solely on textual output. Additionally, the container-selection logic would be refactored to use templates instead of preprocessor directives, improving maintainability and extensibility.