J02: Project 2: grid pathfinding with a correctness oracle

Prerequisites and observable goals#

Level: Second integrated project; directly relevant to games but explainable as a general graph problem.

Purpose and exact problem#

Find a shortest path through a rectangular grid with four-neighbor moves of cost one. Coordinates are integer pairs $(x,y)$, with $0\le x<\text{width}$ and $0\le y<\text{height}$. Walls are forbidden cells. Width and height are integers from 1 to 1000, and start and goal must be valid traversable cells. The output is a list of coordinates from start through goal, or None when no path exists. Path cost is the number of edges, one less than the number of listed cells.

The problem does not include diagonal moves, terrain weights, moving obstacles, multi-agent collision avoidance, or navigation meshes. Those changes require different neighbor rules or heuristics and cannot be added by renaming a function. A path valid on one immutable grid snapshot may become invalid after the world changes; the caller must define that update boundary.

Architecture and method choice#

Separate a validated immutable Grid, neighbor generation, A*, a simple BFS distance oracle, and a JSON CLI. A* maintains the best known cost $g(n)$ and orders its frontier by $f(n)=g(n)+h(n)$. For the four-neighbor unit-cost model, use Manhattan distance

Every move changes one coordinate by one, so any path needs at least that many moves to close the coordinate gaps. Walls can make the true path longer but cannot make this lower bound too large. Thus the heuristic is admissible. For adjacent cells, $h(u)\le1+h(v)$ by the triangle inequality, giving consistency.

The heap may contain an older entry for a node whose best cost was later improved. Store both cost and priority and skip an entry when its stored cost no longer equals the best known cost. Parent links reconstruct the selected path. Do not mark a node permanently solved merely because it was first discovered; discovery and optimal settlement are different events.

Milestones and acceptance criteria#

First validate coordinates and neighbors. Next implement BFS and check tiny grids by hand. Then implement A* with parent reconstruction and compare returned cost to BFS on many generated small grids. Add the CLI only after the algorithms are independently testable. Finally measure representative map families, retaining unreachable cases and validating every timed result.

For every returned path, assert correct endpoints, in-bounds traversable cells, four-neighbor adjacency, and cost equal to BFS’s shortest distance. If A* returns no path, BFS must also report unreachable. Include start equals goal, a blocked or out-of-bounds endpoint, no walls, a corridor, a disconnected goal, duplicate wall input handling, and a route that initially moves away from the goal.

The supplied fixture’s shortest path costs 13. Different shortest paths are acceptable; exact coordinate-list equality is not required unless tie-breaking is explicitly part of the interface. The reference uses deterministic tuple ordering, but the semantic contract concerns validity and optimal cost.

Complete solutions: J02#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

Complete reference implementation#

"""J02: four-neighbor unit-cost A*, checked against an independent BFS."""
import argparse
from collections import deque
from dataclasses import dataclass
import heapq
import json
from pathlib import Path
import sys
Point = tuple[int, int]

@dataclass(frozen=True)
class Grid:
    width: int
    height: int
    walls: frozenset[Point]

    def __post_init__(self):
        if any(type(n) is not int or not 1 <= n <= 1000 for n in (self.width, self.height)):
            raise ValueError("dimensions must be integers in [1,1000]")
        if not isinstance(self.walls, frozenset) or any(not self.inside(p) for p in self.walls):
            raise ValueError("walls must be an in-bounds frozenset of integer coordinates")

    def inside(self, p: Point) -> bool:
        return (len(p) == 2 and all(type(x) is int for x in p)
                and 0 <= p[0] < self.width and 0 <= p[1] < self.height)

    def neighbors(self, p: Point):
        x, y = p
        for q in ((x+1, y), (x, y+1), (x-1, y), (x, y-1)):
            if self.inside(q) and q not in self.walls:
                yield q

    def validate_endpoints(self, start: Point, goal: Point):
        if any(not self.inside(p) or p in self.walls for p in (start, goal)):
            raise ValueError("endpoints must be in bounds and traversable")

def astar(grid: Grid, start: Point, goal: Point) -> list[Point] | None:
    grid.validate_endpoints(start, goal)
    def h(p): return abs(p[0]-goal[0]) + abs(p[1]-goal[1])
    best, parent = {start: 0}, {}
    heap = [(h(start), 0, start)]
    while heap:
        _, cost, u = heapq.heappop(heap)
        if cost != best[u]: continue
        if u == goal:
            path = [u]
            while u != start:
                u = parent[u]
                path.append(u)
            return path[::-1]
        for v in grid.neighbors(u):
            new = cost + 1
            if new < best.get(v, float("inf")):
                best[v], parent[v] = new, u
                heapq.heappush(heap, (new+h(v), new, v))
    return None

def bfs_distance(grid: Grid, start: Point, goal: Point) -> int | None:
    grid.validate_endpoints(start, goal)
    todo, seen = deque([(start, 0)]), {start}
    while todo:
        u, distance = todo.popleft()
        if u == goal: return distance
        for v in grid.neighbors(u):
            if v not in seen:
                seen.add(v)
                todo.append((v, distance+1))
    return None

def main(argv=None):
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument("json", type=Path)
    args = parser.parse_args(argv)
    try:
        obj = json.loads(args.json.read_text())
        grid = Grid(obj["width"], obj["height"], frozenset(map(tuple, obj["walls"])))
        path = astar(grid, tuple(obj["start"]), tuple(obj["goal"]))
        print(json.dumps({"path": path, "cost": None if path is None else len(path)-1}))
    except (OSError, KeyError, TypeError, ValueError) as error:
        print(str(error), file=sys.stderr)
        return 2
    return 0

if __name__ == "__main__":
    raise SystemExit(main())

Run and validate#

python -m solutions.pathfinding fixtures/grid.json
python -m unittest discover -s tests -v

The fixture report must contain cost 13 and a valid path. The test suite also compares 120 generated small-grid cases against BFS in a fixed seeded process. This is bounded randomized verification, not a proof for every grid. The algorithmic argument and the tests address different obligations.

Failure analysis and design tradeoffs#

Allowing diagonal moves while retaining Manhattan distance can make the heuristic overestimate: from $(0,0)$ to $(1,1)$, a unit-cost diagonal needs one move while Manhattan predicts two. Use a heuristic appropriate to the revised movement costs. Introducing negative edge costs invalidates the ordinary A*/Dijkstra assumptions and changes the problem substantially. Dynamic obstacles require snapshot consistency or replanning; sharing a mutable wall set with a running search without synchronization breaks the model.

An unreachable path is not an exceptional parser failure. It is a valid answer for a valid graph, represented by None and JSON null cost. An invalid endpoint is a contract violation and produces an error. Keeping these distinct makes the caller’s recovery behavior clear.

For benchmarking, report map dimensions, wall-generation method, seed, reachability distribution, start/goal policy, repeated samples, and whether parsing is timed. Validate costs before accepting timings. No universal A* speedup is claimed here, and the reference correctness tests are not themselves a pathfinding performance study.

Evaluation rubric and unassigned extensions#

Use the five dimensions from J01. Highest reasoning credit requires a heuristic proof and a clear stale-entry explanation. Highest verification credit requires path validity checks as well as cost comparison; comparing only lengths can miss an illegal route. Highest communication credit states the immutable-world assumption and distinguishes unreachable from malformed input. Weighted terrain, bidirectional search, hierarchical maps, and dynamic replanning are unassigned extensions requiring new proofs and tests, not features claimed complete in this reference.

Retention and readiness#

Retrieve C08 shortest-path assumptions and C14 oracle independence. Advance when you can adapt the movement model and identify which parts of the correctness argument must change, rather than applying A* by name to every navigation problem.