Hexgrid Algorithms

Complete reference for hexagonal grid mathematics and algorithms optimized for game development.

Coordinate Systems

Cube Coordinates (Recommended)

Three-axis system where q + r + s = 0 always.

interface CubeCoord { q: number; // Column r: number; // Row
s: number; // Derived: s = -q - r }

// Constraint: q + r + s must equal 0 function isValidCube(coord: CubeCoord): boolean { return coord.q + coord.r + coord.s === 0; }

Axial Coordinates (Storage-Efficient)

Two-axis system derived from cube (drop s).

interface AxialCoord { q: number; r: number; }

// Convert to cube function axialToCube(axial: AxialCoord): CubeCoord { return { q: axial.q, r: axial.r, s: -axial.q - axial.r }; }

// Convert from cube function cubeToAxial(cube: CubeCoord): AxialCoord { return { q: cube.q, r: cube.r }; }

Offset Coordinates (Display)

For rendering in standard grid layouts.

// Odd-q offset (pointy-top hexes) function axialToOffset(axial: AxialCoord): { col: number; row: number } { const col = axial.q; const row = axial.r + Math.floor((axial.q - (axial.q & 1)) / 2); return { col, row }; }

function offsetToAxial(col: number, row: number): AxialCoord { const q = col; const r = row - Math.floor((col - (col & 1)) / 2); return { q, r }; }

Core Operations

Distance

function hexDistance(a: CubeCoord, b: CubeCoord): number { return Math.max( Math.abs(a.q - b.q), Math.abs(a.r - b.r), Math.abs(a.s - b.s) ); }

// Or equivalently: function hexDistanceAlt(a: CubeCoord, b: CubeCoord): number { return (Math.abs(a.q - b.q) + Math.abs(a.r - b.r) + Math.abs(a.s - b.s)) / 2; }

Neighbors

const CUBE_DIRECTIONS: CubeCoord[] = [ { q: 1, r: -1, s: 0 }, // East { q: 1, r: 0, s: -1 }, // Southeast { q: 0, r: 1, s: -1 }, // Southwest { q: -1, r: 1, s: 0 }, // West { q: -1, r: 0, s: 1 }, // Northwest { q: 0, r: -1, s: 1 }, // Northeast ];

function getNeighbors(hex: CubeCoord): CubeCoord[] { return CUBE_DIRECTIONS.map(dir => ({ q: hex.q + dir.q, r: hex.r + dir.r, s: hex.s + dir.s })); }

function getNeighbor(hex: CubeCoord, direction: number): CubeCoord { const dir = CUBE_DIRECTIONS[direction]; return { q: hex.q + dir.q, r: hex.r + dir.r, s: hex.s + dir.s }; }

Ring

Get all hexes at exact distance from center.

function hexRing(center: CubeCoord, radius: number): CubeCoord[] { if (radius === 0) return [center];

const results: CubeCoord[] = []; let hex: CubeCoord = { q: center.q + CUBE_DIRECTIONS[4].q * radius, r: center.r + CUBE_DIRECTIONS[4].r * radius, s: center.s + CUBE_DIRECTIONS[4].s * radius };

for (let i = 0; i < 6; i++) { for (let j = 0; j < radius; j++) { results.push({ ...hex }); hex = getNeighbor(hex, i); } }

return results; }

Spiral (All Hexes Within Radius)

function hexSpiral(center: CubeCoord, radius: number): CubeCoord[] { const results: CubeCoord[] = [center];

for (let r = 1; r <= radius; r++) { results.push(...hexRing(center, r)); }

return results; }

Pathfinding

A* for Hex Grids

interface PathNode { coord: CubeCoord; g: number; // Cost from start h: number; // Heuristic to goal f: number; // Total: g + h parent: PathNode | null; }

function hexKey(coord: CubeCoord): string { return ${coord.q},${coord.r}; }

function findPath( start: CubeCoord, goal: CubeCoord, isPassable: (coord: CubeCoord) => boolean, getCost: (coord: CubeCoord) => number = () => 1 ): CubeCoord[] | null { const openSet = new Map<string, PathNode>(); const closedSet = new Set<string>();

const startNode: PathNode = { coord: start, g: 0, h: hexDistance(start, goal), f: hexDistance(start, goal), parent: null };

openSet.set(hexKey(start), startNode);

while (openSet.size > 0) { // Get node with lowest f let current: PathNode | null = null; for (const node of openSet.values()) { if (!current || node.f < current.f) { current = node; } }

if (!current) break;

// Check if reached goal
if (hexKey(current.coord) === hexKey(goal)) {
  const path: CubeCoord[] = [];
  let node: PathNode | null = current;
  while (node) {
    path.unshift(node.coord);
    node = node.parent;
  }
  return path;
}

// Move current to closed set
openSet.delete(hexKey(current.coord));
closedSet.add(hexKey(current.coord));

// Check neighbors
for (const neighbor of getNeighbors(current.coord)) {
  const key = hexKey(neighbor);
  
  if (closedSet.has(key) || !isPassable(neighbor)) {
    continue;
  }
  
  const g = current.g + getCost(neighbor);
  const existing = openSet.get(key);
  
  if (!existing || g < existing.g) {
    const node: PathNode = {
      coord: neighbor,
      g,
      h: hexDistance(neighbor, goal),
      f: g + hexDistance(neighbor, goal),
      parent: current
    };
    openSet.set(key, node);
  }
}

}

return null; // No path found }

Spreading Algorithms

Trouble Spread (Farming in Purria)

function spreadTrouble( cluster: TroubleCluster, gridRadius: number, occupiedHexes: Set<string> ): CubeCoord[] { const newHexes: CubeCoord[] = []; const spreadChance = 0.3 + (cluster.severity * 0.1); // 30-80%

for (const hex of cluster.hexCoords) { for (const neighbor of getNeighbors(hex)) { const key = hexKey(neighbor);

  // Skip if already occupied or out of bounds
  if (occupiedHexes.has(key)) continue;
  if (hexDistance({ q: 0, r: 0, s: 0 }, neighbor) > gridRadius) continue;
  
  // Random spread chance
  if (Math.random() < spreadChance) {
    newHexes.push(neighbor);
    occupiedHexes.add(key);
  }
}

}

return newHexes; }

Flood Fill

function floodFill( start: CubeCoord, maxDistance: number, isValid: (coord: CubeCoord) => boolean ): CubeCoord[] { const visited = new Set<string>(); const result: CubeCoord[] = []; const queue: { coord: CubeCoord; dist: number }[] = [{ coord: start, dist: 0 }];

while (queue.length > 0) { const { coord, dist } = queue.shift()!; const key = hexKey(coord);

if (visited.has(key) || dist > maxDistance || !isValid(coord)) {
  continue;
}

visited.add(key);
result.push(coord);

for (const neighbor of getNeighbors(coord)) {
  queue.push({ coord: neighbor, dist: dist + 1 });
}

}

return result; }

Rendering

Pixel Coordinates

const HEX_SIZE = 50; // Radius in pixels

// Pointy-top hex function hexToPixel(hex: AxialCoord, size: number = HEX_SIZE): { x: number; y: number } { const x = size * (Math.sqrt(3) * hex.q + Math.sqrt(3) / 2 * hex.r); const y = size * (3 / 2 * hex.r); return { x, y }; }

function pixelToHex(x: number, y: number, size: number = HEX_SIZE): AxialCoord { const q = (Math.sqrt(3) / 3 * x - 1 / 3 * y) / size; const r = (2 / 3 * y) / size; return hexRound({ q, r }); }

// Round fractional hex to nearest hex function hexRound(hex: AxialCoord): AxialCoord { const cube = axialToCube(hex); let rq = Math.round(cube.q); let rr = Math.round(cube.r); let rs = Math.round(cube.s);

const qDiff = Math.abs(rq - cube.q); const rDiff = Math.abs(rr - cube.r); const sDiff = Math.abs(rs - cube.s);

if (qDiff > rDiff && qDiff > sDiff) { rq = -rr - rs; } else if (rDiff > sDiff) { rr = -rq - rs; }

return { q: rq, r: rr }; }

SVG Hex Path

function hexCorners(center: { x: number; y: number }, size: number): { x: number; y: number }[] { const corners: { x: number; y: number }[] = []; for (let i = 0; i < 6; i++) { const angle = (Math.PI / 180) * (60 * i - 30); // Pointy-top corners.push({ x: center.x + size * Math.cos(angle), y: center.y + size * Math.sin(angle) }); } return corners; }

function hexPath(center: { x: number; y: number }, size: number): string { const corners = hexCorners(center, size); return corners.map((c, i) => ${i === 0 ? 'M' : 'L'} ${c.x} ${c.y}).join(' ') + ' Z'; }

Performance Tips

• Use string keys for Map/Set operations: ${q},${r}

• Pre-calculate neighbors for static grids

• Limit pathfinding with max iterations

• Batch render updates instead of per-hex

• Use spatial hashing for large grids (chunk into regions)