Blocker Detection and Relocation

Blocker Detection

findBlockers(const PhysicalBoard& board, const Path& path) — Function

Parameters: board – current occupancy; path – the path to inspect

Returns: std::vector<BoardCoord> – occupied intermediate squares

Scans every square in path except the destination and returns all that are occupied. The destination is excluded because captures are handled separately by the gantry controller (the captured piece is removed before the primary move begins).

Parking Spot Selection

When a blocker must be moved temporarily, it needs to be placed on an empty square that is not on the primary piece’s path. The parking spot finder uses BFS expanding outward from the blocker’s position to find the nearest such square.

findParkingSpot(const PhysicalBoard& board, const BoardCoord& blockerPos, const std::set<BoardCoord>& excludeSquares) — Function

Parameters: board – current occupancy; blockerPos – the blocker’s current position; excludeSquares – squares that must not be used

Returns: BoardCoord – nearest valid parking spot, or BoardCoord(-1,-1) on failure

The BFS explores the 8-connected neighbourhood of each visited square. A candidate square is accepted when it is empty and not in excludeSquares. The excludeSquares set is pre-populated with every square on the primary piece’s path, ensuring that parked pieces do not block the main move.

Recursive Blocker Relocation

static bool planBlockerRelocation(
    PhysicalBoard&              board,
    const BoardCoord&           blockerPos,
    std::set<BoardCoord>&       excludeSquares,
    std::vector<RelocationPlan>& relocations,
    int                         depth);

This internal function handles the case where the path to the parking spot is itself blocked. The algorithm proceeds as follows:

  1. Find a parking spot for the blocker via findParkingSpot.

  2. Attempt to find a clear path to the parking spot using A* (findClearPath).

  3. If a clear path exists, record the RelocationPlan and update the board state. Done.

  4. If no clear path exists, identify the pieces blocking the route to the parking spot using a secondary BFS.

  5. Recursively call planBlockerRelocation for each of those secondary blockers (depth-first).

  6. After recursive relocations, retry A* to the parking spot.

  7. If still blocked, try up to five alternative parking spots.

  8. Return false if no solution is found.

A maximum recursion depth of 16 is enforced to prevent infinite loops in degenerate board configurations.

false parkingSpot $\gets$ false path $\gets$ record relocation, update board true pathBlockers $\gets$ BFS to find blockers between blockerPos and parkingSpot false path $\gets$ try up to 5 alternative parking spots false record relocation, update board true