hexgrid-algorithms
六边形网格数学、坐标系、路径查找和基于六边形的游戏空间算法。用于实现六边形网格、计算六边形距离、查找邻居、在六边形地图上路径查找、在六边形间传播效果或转换坐标系时使用。触发于涉及六边形网格、六边形坐标、六边形地图上的A*或基于六边形的游戏机制请求。
📖 中文导读:六边形网格数学、坐标系、路径查找和基于六边形的游戏空间算法。用于实现六边形网格、计算六边形距离、查找邻居、在六边形地图上路径查找、在六边形间传播效果或转换坐标系时使用。触发于涉及六边形网格、六边形坐标、六边形地图上的A*或基于六边形的游戏机制请求。 以下正文为该技能的原始 SKILL.md 内容(英文),上方安装命令可直接使用。
name: hexgrid-algorithms description: Hexagonal grid mathematics, coordinate systems, pathfinding, and spatial algorithms for hex-based games. Use when implementing hex grids, calculating hex distances, finding neighbors, pathfinding on hex maps, spreading effects across hexes, or converting between coordinate systems. Triggers on requests involving hexagonal grids, hex coordinates, A* on hex maps, or hex-based game mechanics.
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)