[ sys ] · pathfinding-simulator
sha 1fb8919 · c++23 · header-only · measured-in-repo
Five searches,one templatedbody.
A header-only C++23 maze library where every pathfinder is one generic method, and the same solver code drives both a headless findPath() and a live, threaded terminal animation.
The repo's own tests assert the headline: routing around a weight-10 barrier, Dijkstra and A* reach the optimal weighted path at cost 4.0, while step-counting search takes the 2-step route straight through it.
Make graph search legible, in real time, without forking the solver.
Most pathfinding demos either show a static "here's the path" screenshot or fold the visualization into the algorithm until the two can never come apart. I wanted the visualization and the solver to share one body of code: the thing that animates on screen is the exact code that runs headless.
The point is to make the behavioral difference watchable. BFS and Dijkstra flood. A* leans toward the goal. Greedy sprints and sometimes pays for it. Weighted terrain bends the optimal route in a way you can see happen. The UI runs the exact same solver code, instrumented from the outside.
The second constraint is concurrency. A terminal UI that redraws on every expanded node stutters if the search blocks the render loop. So under the animation sits the real problem: run the solver off the UI thread, stream its frontier and visited sets back safely, and never tear a frame.
One generic maze, one callback, five algorithms that share it.
The whole engine is a single class template, GenericMaze<G>, parameterized over any cell type that satisfies a C++20 concept. GraphCell requires exactly four members: wall, glyph, color, and weight. Nothing in the algorithms knows what a cell is beyond that contract, so the same solvers work for an ANSI terminal cell or anything else you hand them.
Each algorithm is one templated method. The piece that keeps the visualization and the solver identical is the ExploreCallback: an optional std::function the solver calls once per expanded node, handing out the current cell plus snapshots of the frontier and visited sets. Pass nullptr and you get a fast headless findPath(). Pass a callback and the identical code drives the animation. The solver never branches on whether anyone is watching.
Dijkstra and A* share one lazy-deletion priority queue, skipping stale entries instead of doing a decrease-key. A* adds a Manhattan heuristic on top of Dijkstra's cost accumulation. Kruskal generation carves its spanning tree with a union-find that does path compression and union by rank. The pieces are textbook. I composed them through one generic spine instead of five copy-pasted solvers.
// any cell that exposes these four members is a maze cell
template <typename T>
concept GraphCell = requires(T t) {
{ t.wall } -> std::convertible_to<bool>;
{ t.glyph } -> std::convertible_to<char>;
{ t.color } -> std::convertible_to<Color>;
{ t.weight } -> std::convertible_to<float>;
};
// one signature; nullptr = headless, callback = animated
Path findPath(Algorithm algo, Cell start, Cell dest,
ExploreCallback on_explore = nullptr);The solver runs on a worker thread. The UI only ever reads snapshots.
app.cpp runs findPath() on a worker thread. The callback locks a mutex, copies the frontier/visited snapshot, and posts an FTXUI redraw. Solid blue is the search write path. Dashed grey is the UI read path. Drawn from the real header tree: no docs/ diagram exists upstream, so this is the threaded data flow the README only describes in prose.Roads not taken, and the one I'd flag in review.
Two of these are deliberate simplicity-over-speed calls that are correct for interactive maze sizes. The last is a defect I would fix before calling this production-grade.
chose · control over RAII
Raw G** grid with hand-written new[]/delete[]
The maze owns a raw 2D array and a custom move-only DirectionMap instead of std::vector or mdspan. It trades RAII safety for explicit ownership and a predictable layout. The move-only type deletes its copy constructor specifically to make a double-free impossible, so the control is at least disciplined.
chose · simplicity over speed
The callback rebuilds the whole frontier every step
To hand the UI a clean snapshot, ExploreCallback copies the entire queue, stack, or priority_queue into a vector on every expanded node: O(n) per node. For a terminal-sized maze that is invisible, and it keeps the solver code free of UI bookkeeping. On a million-node graph it would dominate.
loss · would fix in review
The findPath switch lambda has no default return
The dispatch lambda in maze.tpp:106 returns from each case but has no trailing return, so the compiler flags -Wreturn-type. It is only reachable through an invalid Algorithm enum value, but it should be a std::unreachable(). There is also a dangling MAZE_BUILD_BENCHMARKS CMake option with no benchmark behind it yet.
There is no named baseline to benchmark against. No competing maze library is in scope, and I did not commit a micro-benchmark harness. The comparison the repo's own tests make is between the algorithms themselves. That is the evidence below.
What each algorithm guarantees, asserted by the test suite.
The repo ships 5 algorithms and 3 generators behind 12 Catch2 cases. Two of those cases carry the load here: a flood-fill check that every passage of a 21x21 maze is reachable for all three generators, and the weighted-optimality assertion below. The numbers are what the suite asserts.
what each of the five searches guarantees
categorical properties, not measured here · completeness and optimality are what the algorithm promises, by construction
| Algorithm | Complete | Optimal | Cost-aware | How it searches |
|---|---|---|---|---|
| BFS | ✓ | ✓ | · | floods evenly, ring by ring |
| Dijkstra | ✓ | ✓ | ✓ | floods, ordered by accumulated cost |
| A* | ✓ | ✓ | ✓ | leans at the goal, heuristic prunes the rest |
| DFS | ✓ | · | · | dives down one branch first |
| Greedy | ✓ | · | · | sprints toward the goal on the heuristic alone |
BFS and Dijkstra are complete and optimal but explore broadly. A* keeps the optimality guarantee while a Manhattan heuristic prunes the search. DFS and Greedy reach a goal faster by giving up optimality, which is the trap the weighted test below catches. These are properties of each algorithm, so no expansion counts are shown: none are committed to the repo.
weighted optimality: routing around a weight-10 barrier
asserted in tests/test_pathfinding.cpp:90-120 · the 2-step direct route crosses a weight-10 cell
| Algorithm | Routes by | Path cost | Optimal? |
|---|---|---|---|
| BFS | fewest steps | crosses the barrier | no |
| Greedy | heuristic only | crosses the barrier | no |
| DFS | first path found | arbitrary | no |
| Dijkstra | accumulated cost | 4.0 | yes ✓ |
| A* | cost + heuristic | 4.0 | yes ✓ |
Step-counting search takes the 2-step route straight through the weight-10 cell. Dijkstra and A* detour to reach cost 4.0, the optimal weighted path. This is the exact result tests/test_pathfinding.cpp:90-103 (Dijkstra) and :106-120 (A*) assert, so it reproduces on every CI run.
[ sys ] · inline demo
Watch the same maze, four searches, side by side.
Four TypeScript reimplementations of the repo's solvers run on one generated maze: BFS floods evenly, Dijkstra weighs its way out, A* leans toward the goal, and Greedy sprints and sometimes pays for it.
floods evenly outward, ring by ring
floods, but follows accumulated cost
leans toward the goal, prunes the rest
sprints at the goal, skips the cost
repo & demo
Header-only, 12 tests green, every passage reachable.
The generic core is ~1,603 lines. The Catch2 suite proves full connectivity on a 21x21 maze for all three generators and asserts the weighted-optimality cost above. The live demo runs in any terminal: arrow keys, Space to solve, R to regenerate.
pathfinding-simulator · C++23 · FTXUI · Catch2 · MIT
sha 1fb8919 · measured-in-repo