Pathfinder — Integration Skill

Use this skill when the user asks to "pathfinding", "A star", "find path",

"shortest route", "navigation", or "enemy movement AI".

WHAT IT DOES

A generic A* pathfinder for 2D tile grids. Given a start position, a grid of tile values, and one or more target positions, it finds the shortest path while respecting per-tile movement costs. Tiles can be impassable (walls, water) or have variable cost (roads are cheap, mud is expensive). Returns an array of pixel-coordinate waypoints, or null if no path exists. Includes an optional path-smoothing pass that removes redundant waypoints on straight segments.

REQUIREMENTS

• Framework: Any (Phaser, Three.js, vanilla JS, Node.js)
• Language: TypeScript or JavaScript
• Dependencies: None
• Files: 1 TypeScript file (~100 LOC)

INSTALL

1. Copy the findPath and smoothPath functions into your project (e.g., src/utils/Pathfinder.ts).
1. Import wherever needed:

`typescript

import { findPath, smoothPath } from './utils/Pathfinder';

`

1. Provide your grid and a cost function.

INTEGRATION

Core Implementation

interface Point {
  x: number;
  y: number;
}

interface Node {
  col: number;
  row: number;
  g: number;
  h: number;
  f: number;
  parent: Node | null;
}

/**
 * A* pathfinding on a 2D tile grid (4-directional).
 *
 * @param startX - Start X in pixels
 * @param startY - Start Y in pixels
 * @param grid - 2D array of tile values (number[][])
 * @param targets - Array of goal positions in pixels
 * @param tileSize - Pixel size of one tile
 * @param getCost - Returns movement cost for a tile value, or undefined if impassable
 * @returns Array of pixel-coordinate waypoints, or null if no path
 */
function findPath(
  startX: number,
  startY: number,
  grid: number[][],
  targets: Point[],
  tileSize: number,
  getCost: (tileValue: number) => number | undefined
): Point[] | null {
  const startCol = Math.floor(startX / tileSize);
  const startRow = Math.floor(startY / tileSize);
  const rows = grid.length;
  const cols = grid[0]?.length ?? 0;

  // Convert targets to grid coords
  const goalSet = new Set<string>();
  for (const t of targets) {
    goalSet.add(`${Math.floor(t.x / tileSize)},${Math.floor(t.y / tileSize)}`);
  }

  const open: Node[] = [];
  const closed = new Set<string>();

  // Heuristic: Manhattan distance to nearest target
  function heuristic(col: number, row: number): number {
    let best = Infinity;
    for (const t of targets) {
      const tc = Math.floor(t.x / tileSize);
      const tr = Math.floor(t.y / tileSize);
      best = Math.min(best, Math.abs(col - tc) + Math.abs(row - tr));
    }
    return best;
  }

  const start: Node = {
    col: startCol, row: startRow,
    g: 0, h: heuristic(startCol, startRow), f: 0, parent: null,
  };
  start.f = start.g + start.h;
  open.push(start);

  const dirs = [[0, -1], [1, 0], [0, 1], [-1, 0]]; // N, E, S, W

  while (open.length > 0) {
    // Find node with lowest f (simple array scan)
    let bestIdx = 0;
    for (let i = 1; i < open.length; i++) {
      if (open[i].f < open[bestIdx].f) bestIdx = i;
    }
    const current = open.splice(bestIdx, 1)[0];
    const key = `${current.col},${current.row}`;

    if (goalSet.has(key)) {
      // Reconstruct path
      const path: Point[] = [];
      let node: Node | null = current;
      while (node) {
        path.unshift({
          x: (node.col + 0.5) * tileSize,
          y: (node.row + 0.5) * tileSize,
        });
        node = node.parent;
      }
      return path;
    }

    closed.add(key);

    for (const [dc, dr] of dirs) {
      const nc = current.col + dc;
      const nr = current.row + dr;
      if (nc < 0 || nc >= cols || nr < 0 || nr >= rows) continue;

      const nKey = `${nc},${nr}`;
      if (closed.has(nKey)) continue;

      const cost = getCost(grid[nr][nc]);
      if (cost === undefined) continue; // Impassable

      const g = current.g + cost;
      const existing = open.find(n => n.col === nc && n.row === nr);

      if (existing) {
        if (g < existing.g) {
          existing.g = g;
          existing.f = g + existing.h;
          existing.parent = current;
        }
      } else {
        const h = heuristic(nc, nr);
        open.push({ col: nc, row: nr, g, h, f: g + h, parent: current });
      }
    }
  }

  return null; // No path found
}

/**
 * Remove redundant waypoints on straight segments.
 */
function smoothPath(path: Point[]): Point[] {
  if (path.length <= 2) return path;

  const result: Point[] = [path[0]];
  for (let i = 1; i < path.length - 1; i++) {
    const prev = result[result.length - 1];
    const next = path[i + 1];
    // Keep point only if direction changes
    const dx1 = path[i].x - prev.x;
    const dy1 = path[i].y - prev.y;
    const dx2 = next.x - path[i].x;
    const dy2 = next.y - path[i].y;
    if (dx1 !== dx2 || dy1 !== dy2) {
      result.push(path[i]);
    }
  }
  result.push(path[path.length - 1]);
  return result;
}

Enemy Movement Example

// Grid: 0 = ground, 1 = wall, 2 = mud (slow)
const grid: number[][] = [
  [0, 0, 0, 1, 0],
  [0, 1, 0, 2, 0],
  [0, 0, 0, 0, 0],
];

const TILE_SIZE = 64;

function tileCost(value: number): number | undefined {
  if (value === 1) return undefined; // Wall — impassable
  if (value === 2) return 3;         // Mud — 3x cost
  return 1;                          // Ground — normal
}

// Find path from enemy to player
const path = findPath(
  enemy.x, enemy.y,
  grid,
  [{ x: player.x, y: player.y }],
  TILE_SIZE,
  tileCost
);

if (path) {
  const smoothed = smoothPath(path);
  enemy.followPath(smoothed);
}

Multiple Targets Example

// Find path to nearest exit (any of several goal tiles)
const exits: Point[] = [
  { x: 64, y: 0 },
  { x: 256, y: 320 },
  { x: 448, y: 160 },
];

const path = findPath(npc.x, npc.y, grid, exits, TILE_SIZE, tileCost);
// A* will find the shortest path to whichever exit is closest

CONFIGURATION

Option	Type	Default	Description
grid	number[][]	*required*	2D array where grid[row][col] is the tile value
tileSize	number	*required*	Pixel size of one tile
getCost	`(value) => number \	undefined`	*required*	Cost function: return cost (>0) or undefined for impassable
targets	Point[]	*required*	One or more goal positions in pixel coordinates

API REFERENCE

Function	Signature	Returns	Description
findPath	findPath(startX, startY, grid, targets, tileSize, getCost)	`Point[] \	null`	A* path as pixel waypoints, or null
smoothPath	smoothPath(path: Point[])	Point[]	Remove redundant straight-line waypoints

Point interface: { x: number, y: number } — pixel coordinates (path waypoints are tile centers).

GOTCHAS

• 4-directional only. This implementation does not support diagonal movement. Extending to 8-directional requires adjusting the dirs array and using Math.SQRT2 cost for diagonals.
• Uses a simple array, not a priority queue. The open list is scanned linearly to find the lowest f-cost node. This is fine for grids under ~1000 tiles. For larger grids, replace with a binary heap.
• Grid is grid[row][col], not grid[x][y]. Row = Y axis, Col = X axis. This matches standard 2D array conventions.
• Targets are pixel positions. They are converted to grid coordinates internally. The path output is also in pixel coordinates (tile centers).
• getCost must return undefined for impassable tiles, not 0 or -1. A cost of 0 would make the tile free (which might be intentional for roads), but negative costs break the algorithm.
• No path caching. Each call recomputes from scratch. If many entities need paths to the same target, consider a flow field instead.