Project Overview
This project implements the A* pathfinding algorithm in modern C++14, as specified in the project brief. The application finds the shortest path between two points on a configurable grid while navigating around obstacles, producing a colour-coded ASCII representation of the result in the console.
The A* Algorithm
A* is a heuristic-based search algorithm that finds the shortest path between two points. It maintains an open list of candidate nodes, always expanding the node with the lowest total estimated cost f = g + h, where g is the actual cost from the start and h is a heuristic estimate of the remaining cost to the goal.
What makes A* effective is that it combines the thoroughness of Dijkstra's algorithm with the directional focus of greedy best-first search. By using an admissible heuristic (one that never overestimates), A* is guaranteed to find the optimal path while exploring significantly fewer nodes than an exhaustive search.
A* is complete (always finds a path if one exists) and optimal (the path found is guaranteed to be shortest) when the heuristic is admissible.
The five snapshots below show A* searching a 9x7 grid with two walls (columns 3 and 6, gaps at rows 3 and 5). Start is at (0,0), goal at (8,6). Each explored cell shows its f value with g and h below. Teal-bordered cells are in the open list (frontier). All values were computed by running the actual algorithm.
Design Choices
Structure-first Approach
Rather than jumping straight into the A* algorithm, I chose to build the project from the outside in, starting with the grid configuration and visualisation, then the test suite, and only then the pathfinding logic itself. This was a deliberate decision: I wanted to fully understand how the code would run and how the different components would interact before tackling the most complex part.
The gridParameters Struct
The gridParameters struct serves as a centralised settings hub for the entire project. It holds the grid dimensions, start and goal positions, the obstacle list, and the random generation toggle. All of these parameters are configurable. The algorithm, visualiser, and test suite all operate on this single struct, meaning any configuration change propagates everywhere automatically.
Memory Management with Smart Pointers
As part of the project requirements, smart pointers were to be used where possible. Nodes created during the A* search are managed using std::unique_ptr via a std::vector<std::unique_ptr<Node>> container. This ensures all dynamically allocated nodes are automatically cleaned up when the pathfinding function returns, without needing manual delete calls.
Dual Obstacle Modes
The project supports two obstacle modes. The default is a fixed maze layout with vertical walls at regular intervals, each with a gap at a different row to force a zigzag path. The second mode generates random obstacles, controlled by the randomObstaclesEnabled flag and randomObstaclesCount parameter. When random mode is active, the program automatically regenerates the obstacle layout if no valid path exists, retrying up to 20 attempts before reporting failure.
Development Process
This section documents how the project was built iteratively, from the first lines of code through to the final implementation.
Phase 1 - Grid Structure & Visualisation
I began by focusing on the gridParameters struct and the grid display, before writing any pathfinding code. The very first version used a std::vector<std::vector<int>> to represent the grid:
Changing the grid type from std::vector<std::vector<int>> to std::vector<std::vector<std::string>> let me use meaningful characters:
The switch from int to string was a small type change, but it unlocked a much more expressive grid. Each cell could hold not just a symbol but also ANSI colour codes, opening the door to the entire colour-coded visualisation system.
Phase 2 - Start and Goal Markers
Once the grid displayed obstacles clearly, I added S for start and G for goal:
Phase 3 - Test Suite (Before the Algorithm)
Before writing any A* code, I built the test suite. The runTests() function checks 10 conditions and the main function only proceeds if every test passes.
Phase 4 - Understanding A* (Theory)
Before writing the algorithm, I studied the theory by watching the video "A* Pathfinding Algorithm" (linked in References). This gave me a clear understanding of the Node struct, specifically the cost values g, h, and f = g + h.
Phase 5 - A* Implementation
With the theory understood and a validated, visual grid in place, I implemented the A* algorithm. Having the grid display already working meant I could immediately see the path output and verify it visually.
Phase 6 - Random Obstacle Generation
After A* was working with the fixed maze, I implemented random obstacle generation using std::mt19937. Obstacles are never placed on or adjacent to start and goal. If no path exists, the program regenerates and retries up to 20 times.
Phase 7 - Console Colours & Styling
The visual styling was the last thing I added. I created ConsoleColors.h for ANSI escape codes, added enableColors() for Windows, and implemented box-drawing borders with a colour-coded legend.
Data Structures
| Structure | Purpose |
|---|---|
gridParameters | Centralised settings: dimensions, start/goal, obstacle list, random generation config |
Node | Search cell with position, cost values (g, h, f), and parent pointer |
AStarAlgorithm | Pathfinding logic, open/closed list management, and grid visualisation |
Node Cost Values
File Structure
| File | Responsibility |
|---|---|
AStarAlgorithm.h | Declarations for gridParameters, Node, and AStarAlgorithm |
AStarAlgorithm.cpp | A* implementation, grid population, and rendering |
GridUtils.cpp | Random obstacle generation logic |
Tests.cpp | 10 validation checks for grid configuration |
ConsoleColors.h | ANSI colour constants and Windows console setup |
main.cpp | Entry point - runs tests, then pathfinding and display |
Heuristic: Manhattan Distance
The project brief specified Manhattan distance as the required heuristic. For a grid with only horizontal and vertical movement:
This is admissible because no path through adjacent cells can ever be shorter than the Manhattan distance. It is also consistent (monotone), avoiding redundant node re-expansion.
If diagonal movement were added in a future iteration, the heuristic would need to be updated to Euclidean or Chebyshev distance to preserve admissibility.
Grid Visualization
The grid visualisation evolved significantly during development (see Section 04). The final version uses ANSI escape codes for colour, box-drawing characters for borders, and a legend at the bottom.
Grid Symbols
Two Display Modes
The populateGrid() function is overloaded with two versions: one that shows the grid before pathfinding, and one that overlays the discovered path using * symbols.
Colour System
ANSI escape codes are defined in ConsoleColors.h and embedded directly into each grid cell string. On Windows, virtual terminal processing is enabled at startup via enableColors(). The colours are: green for start, cyan for goal, red for obstacles, and yellow for the path.
Testing & Validation
The test suite runs automatically before any pathfinding occurs. If any test fails, the program halts immediately.
| # | Test Case | Description | Status |
|---|---|---|---|
| 1 | Grid dimensions | Width and height must be positive | ✓ Pass |
| 2 | Start in bounds | Start position within grid extents | ✓ Pass |
| 3 | Goal in bounds | Goal position within grid extents | ✓ Pass |
| 4 | Obstacles in bounds | All obstacles within grid extents | ✓ Pass |
| 5 | Start not on obstacle | Start cell is not blocked | ✓ Pass |
| 6 | Goal not on obstacle | Goal cell is not blocked | ✓ Pass |
| 7 | Start ≠ Goal | Start and goal are different positions | ✓ Pass |
| 8 | Random count valid | randomObstaclesCount is non-negative | ✓ Pass |
| 9 | Random count feasible | Count does not exceed total grid cells | ✓ Pass |
| 10 | No duplicates | All obstacle coordinates are unique | ✓ Pass |
Building the test suite before the A* algorithm was a deliberate choice. It meant the algorithm was always tested against validated configurations from day one.
Limitations & Future Improvements
Current Limitations
Movement is restricted to four cardinal directions, and all traversable cells share a uniform cost of 1. The path is displayed in a single colour, which gives no indication of progress along the route.
Planned Enhancements
Weighted terrain would let different cells have different movement costs, so the algorithm could model things like rough ground or roads. This would require changing the cost calculation in findPath() from a flat +1 to a lookup based on cell type, and swapping the heuristic if diagonal movement were also added. A path colour gradient (fading from green to yellow along the route) would give a visual sense of progress and distance from the start, which the current single-colour path does not communicate.
Development Timeline
gridParameters struct, initial int grid displayint to string - introduced readable symbolsTools Used
| Tool | Purpose |
|---|---|
| Visual Studio 2022 | Primary IDE and debugger |
| C++14 Standard | Language specification |
Reflection
Challenges Encountered
The biggest early challenge was deciding how to represent the grid. Starting with a std::vector<std::vector<int>> worked for proving the basic structure, but the output was difficult to interpret. Switching to std::string solved the readability problem and opened up the ability to embed ANSI colour codes directly into each cell.
Building the test suite before the algorithm required discipline, as it felt like delaying the "real work", but it paid off significantly. Having validated inputs meant that when A* produced unexpected results, I could be confident the issue was in the algorithm, not the grid setup.
Key Learnings
Understanding A* required grasping not just the code but the mathematics behind it: why f = g + h works, why the heuristic must be admissible, and how the priority queue ensures the optimal node is always expanded next.
Working with std::unique_ptr for node management was a practical lesson in modern C++ memory management. Automatic cleanup via the allNodes vector eliminated the risk of memory leaks.
What I Would Do Differently
Looking back, the main thing I would change is better alignment with the C++ Core Guidelines from the start. The two populateGrid() overloads share most of their logic, with the only difference being the path overlay. Following F.51 (prefer default arguments over overloading), a single function with a default empty path parameter would remove that duplication. The grid dimensions are also static const int, meaning any size change requires recompiling. Making them regular members would allow runtime configuration without touching the header.
Inside findPath(), the isObstacle lambda scans the full obstacle list on every neighbour check. Building a std::vector<std::vector<bool>> once at the start would be simpler and faster. These are small things individually, but they add up, and catching them earlier would have saved time during later phases.
AI Assistance
I used AI tools (Claude) during this project for coding assistance and for formatting and styling the report. All AI-assisted code was limited in scope and adapted to fit my own design. I made sure I had a full understanding of everything in the codebase by building the project structure first, getting the grid, tests, and visualisation working before tackling the A* algorithm itself. This meant that by the time AI was involved in any coding help, I already understood how the components fit together and could verify that any suggestions were correct.