A* Pathfinding¶

Overview¶

A* pathfinding is used exclusively for routing blocker pieces to their parking spots. Unlike primary piece paths (which follow chess movement rules), blocker paths must avoid all occupied squares and find the shortest physically traversable route.

findClearPath(const PhysicalBoard& board, const BoardCoord& from, const BoardCoord& to) — Function

Parameters: board – current occupancy; from – start; to – goal

Returns: Path – shortest clear path, or empty path if none exists

Algorithm Details¶

The implementation uses a standard A* search over the 8-connected grid:

Open set: std::priority_queue (min-heap) of AStarNode values keyed on $f = g + h$.
Heuristic $h$: Chebyshev distance (maximum of $|\Delta\text{row}|$ and $|\Delta\text{col}|$), which is admissible because the gantry can move diagonally and each step costs 1.
Edge cost: Uniform cost of 1 per step regardless of direction.
Obstacle avoidance: Occupied squares are skipped, except for the goal square (which may be occupied by the piece being relocated there).
Path reconstruction: Follows cameFrom pointers from goal back to start, then reverses.

struct AStarNode {
    BoardCoord coord;
    int        fScore;   // g + h

    bool operator>(const AStarNode& other) const {
        return fScore > other.fScore;
    }
};

Distance Metrics¶

Two distance metrics are defined for use in heuristics and path evaluation:

chebyshevDistance(const BoardCoord& from, const BoardCoord& to) — Function

Parameters: from, to – two squares

Returns: int – $\max(|\Delta r|, |\Delta c|)$

The Chebyshev (chessboard) distance is the minimum number of king moves needed. It is the A* heuristic because the gantry can step diagonally.

manhattanDistance(const BoardCoord& from, const BoardCoord& to) — Function

Parameters: from, to – two squares

Returns: int – $|\Delta r| + |\Delta c|$

Manhattan distance counts only orthogonal steps. Available for use in contexts where diagonal travel is not permitted.