How to Build: Pathfinding

When the player taps a location during active play, they shouldn't walk through walls. They should find a path around them. That means we need pathfinding -- specifically, A* adapted for hex grids.

Here's an important distinction: auto-battle road following does NOT use pathfinding. The road path comes directly from the Wave Function Collapse output as a pre-computed sequence of waypoints. A* is only needed for active play, when the player taps somewhere off the beaten path and we need to route around obstacles.

Hex grid neighbors

On a hex grid with axial coordinates, every hex has exactly six neighbors. The direction offsets are:

const HEX_DIRECTIONS: Array<{ q: number; r: number }> = [
  { q: 1, r: 0 },  { q: -1, r: 0 },
  { q: 0, r: 1 },  { q: 0, r: -1 },
  { q: 1, r: -1 }, { q: -1, r: 1 },
]

function getNeighbors(q: number, r: number): Array<{ q: number; r: number }>

This is the foundation of everything that follows. A* expands nodes by checking their neighbors, and on a hex grid, those neighbors are always these six offsets added to the current axial coordinates.

The distance heuristic

A* needs an admissible heuristic -- a function that estimates the distance between two hexes without overestimating. For axial coordinates, hex distance works perfectly:

function hexDistance(
  a: { q: number; r: number },
  b: { q: number; r: number },
): number

The formula is (|a.q - b.q| + |a.q + a.r - b.q - b.r| + |a.r - b.r|) / 2. This gives the exact number of hex steps between two hexes in an unobstructed grid, which makes it both admissible and consistent -- ideal for A*.

Determining walkability

Before we can pathfind, we need to know which hexes the player can walk on. The Wave Function Collapse level data tells us what's at each hex position:

function isWalkable(q: number, r: number, levelData: LevelData): boolean

Road tiles and open terrain are walkable. Wall tiles, edge tiles, and certain point-of-interest tiles are not. If the hex doesn't exist in the level data at all (out of bounds), treat it as unwalkable.

Keep this function separate from the A* implementation. The pathfinder accepts a walkability callback, which means you can swap in different walkability rules for different contexts (maybe enemies can walk through certain tiles the player can't, or a future flying mount ignores terrain entirely).

The A* algorithm

Standard A* with a priority queue (min-heap sorted by f-score). The public interface:

function findPath(
  start: HexCoord,
  end: HexCoord,
  isWalkable: (q: number, r: number) => boolean,
  maxIterations?: number,
): HexCoord[] | null

Returns an array of hex coordinates from start to end, or null if no path exists. The maxIterations parameter is a safety valve -- on large grids, a pathfinding request to an unreachable location could expand thousands of nodes before giving up. Cap it at a reasonable number (500-1000) and return null if exceeded. The player gets a "can't reach that" feedback, which is better than a frozen frame.

The algorithm itself is textbook:

1. Initialize the open set with the start node (f-score = heuristic to end)
2. Pop the node with the lowest f-score
3. If it's the end node, reconstruct and return the path
4. For each walkable neighbor, calculate the tentative g-score (current g + 1, since all hex moves cost the same)
5. If this path to the neighbor is better than any previously found, update it and add to the open set
6. Repeat until the open set is empty or max iterations exceeded

For the priority queue, a simple binary heap works fine at our scale. You could also use a sorted array for prototyping and optimize later if profiling shows it matters.

Path smoothing (optional)

Raw A* on a hex grid produces paths that zigzag along hex edges. On a flat grid this looks fine since movement snaps to hex centers anyway. But if you're interpolating smoothly between waypoints, consider a post-processing pass that removes redundant waypoints where the path continues in a straight line.

This is a nice-to-have. Skip it initially and add it if the zigzag looks bad in practice.

Integrating with the movement system

When the player taps a location during active play, the tap handler from the movement system needs to route through pathfinding:

1. Convert the tap world position to hex coordinates
2. Run findPath from the player's current hex to the target hex
3. If a path is found, convert each hex coordinate to a world position
4. Load the world positions into the player's WaypointQueue trait

const path = findPath(
  playerHex,
  targetHex,
  (q, r) => isWalkable(q, r, levelData),
)
if (path) {
  const worldPoints = path.map(hex => hexToWorldPosition(hex.q, hex.r))
  player.set(WaypointQueue, { points: worldPoints })
}

The movement system (from the previous guide) already handles WaypointQueue -- it pops the next point into MovementTarget whenever the current target is reached. So pathfinding just fills the queue, and the existing movement loop does the rest. No changes needed to the core movement system.

A note about ribbon complexity

This is the highest-risk part of the prototype. A* on a flat hex grid is straightforward, but the ribbon projection adds a wrinkle: world-space distances don't map linearly to hex distances on a curved surface.

The fallback plan is simple and probably good enough: implement A* in flat hex space, ignoring the ribbon curvature. The path will be approximately correct. Players won't notice minor inaccuracies on a curved surface because the camera follows the player and the deviation is small relative to the hex tile size.

If you do want ribbon-aware pathfinding later, the approach would be to adjust the heuristic to account for arc-length distances. But spike the flat version first and see if anyone notices.

File organization

src/core/pathfinding/
├── hex-math.ts       # Neighbor calculation, hex distance, coordinate conversions
├── a-star.ts         # A* algorithm with priority queue
├── walkability.ts    # Query level data for walkable hexes
└── index.ts          # Public API: findPath(start, end, grid) -> HexCoord[]

Keep the pathfinding module self-contained. It takes hex coordinates in, returns hex coordinates out. The conversion between hex coords and world positions happens at the call site, not inside the pathfinder. This makes the A* implementation testable in isolation -- you can write unit tests with small hex grids without needing a full level loaded.