Model the map as one grid so every neighbor, path, and cost is an exact value you can assert against, with no randomness you cannot reproduce. Each lesson is one concrete spec: the fixed North, East, South, West neighbor order, a FIFO frontier and a came-from map, a binary min-heap with deterministic tie-breaking, edge relaxation over terrain weights, the f = g + h loop and the exact node-expansion counts that prove A* does less work, a self-defined seeded generator, and two maze algorithms that each produce a perfect maze reproduced exactly from a seed.
Over 32 lessons you build a working pathfinding and maze library from scratch, designed so that every result is exactly reproducible. A grid of walkable and wall cells with a fixed North, East, South, West neighbor order, a binary min-heap with explicit tie-breaking, and a self-defined seeded random number generator together make every path, cost, node-expansion count, and generated maze a specific value you can pin down and assert against. That determinism is the whole point: the library you write behaves identically in any language.
You start with the grid and its graph view (cells are nodes, adjacent cells are edges, terrain sets edge cost), then build the search algorithms in order of power: breadth-first search for the unweighted shortest path with a FIFO frontier and path reconstruction, Dijkstra over weighted terrain using a min-heap you build by hand, and A* with admissible heuristics (Manhattan for four-way movement, octile for eight-way) that finds the same optimal path as Dijkstra while expanding strictly fewer nodes. Then you generate perfect mazes, ones with exactly one path between any two cells, using a recursive backtracker and randomized Prim's, both seeded so a given seed yields a specific maze. The capstone generates a maze from a fixed seed, solves it with A*, asserts the exact optimal path and its length, and renders the maze with the path overlaid.
This is a teaching-grade library built around the classic grid-pathfinding design from Amit Patel's Red Blob Games and the original A* paper: it searches a single in-memory grid, is deterministic by construction, and represents paths as lists of coordinates. It is honest about what it stops short of. It does not implement hierarchical or any-angle pathfinding, jump point search, contraction hierarchies, or dynamic replanning (D* / LPA*), and it uses a simple integer cost model rather than floating-point Euclidean distances. Those are exactly the extensions a production navigation system layers on top of this honest core.
Every pathfinder needs a map to search. Ours is a grid, a rectangle of cells laid out in rows and columns, and today you build it and have it report its own size. Everything later carves paths and mazes through this one structure.
Create a grid of a fixed width and height and report both dimensions.
A pathfinder works over a map, and the simplest useful map is a grid: a
rectangle of cells addressed by column x and row y. Keeping the map an explicit
grid, rather than real-world geometry, is what makes every later result an exact
value you can check: a path is a list of cell coordinates, a cost is an integer, a
maze is a specific pattern of walls.
Today is deliberately tiny. A grid needs to know how wide and how tall it is,
because those dimensions bound every coordinate the search will ever touch. That
width by height rectangle is the entire world our pathfinder lives in, so
pinning it down precisely is where everything starts.
// the whole pathfinder searches inside this one gridtype Grid struct {W, H int}func NewGrid(w, h int) *Grid { return &Grid{W: w, H: h} }func (g *Grid) Width() int { return g.W }func (g *Grid) Height() int { return g.H }
A genuinely working, fully deterministic library: BFS, Dijkstra, and A* (four-way and eight-way) shortest-path search over a grid of walkable, wall, and weighted-terrain cells with a hand-built min-heap and explicit tie-breaking, plus two perfect-maze generators (recursive backtracker and randomized Prim's) driven by a self-defined seeded RNG, an ASCII renderer with path overlay, and a runnable seed-driven CLI - but it searches a single in-memory grid with an integer cost model, generates only unweighted perfect (single-solution) mazes, and stops short of the advanced techniques a production navigator layers on top.
The clearest visual explanation of breadth-first search, Dijkstra, greedy best-first, and A* on a grid, with interactive diagrams of frontier, came-from, cost-so-far, and heuristics. This project follows its progression from BFS to A* almost beat for beat.
The companion implementation notes: priority-queue tie-breaking, the difference between early exit and full search, heuristic scaling, and admissibility. The reference for the min-heap and tie-break lessons here.
The original A* paper. It defines the evaluation function f = g + h and proves that an admissible heuristic (one that never overestimates) guarantees an optimal path. Read it for why the algorithm you build is correct.
A whole book of maze-generation algorithms, including the recursive backtracker and Prim's built here, each producing a perfect maze. The grid-of-cells-with-passages model and the rendering approach in the maze chapter follow this book.
A concise catalogue of maze-generation algorithms with animations, comparing the texture and bias of recursive backtracker, Prim's, Kruskal's, and others. Useful when you want a third or fourth generator after the two in this project.