Pathfinding

// A* pathfinding with binary heap priority queue
const GRID_W = 100
const GRID_H = 100
grid = null  // 0=walkable, 1+=cost multiplier, -1=wall

on start {
  grid = new Int8Array(GRID_W * GRID_H)
  // Populate grid from terrain
  for x = 0 to GRID_W {
    for y = 0 to GRID_H {
      terrainType = terrain.getTile(x, y)
      if terrainType == "water" grid[x + y * GRID_W] = -1
      else if terrainType == "mud" grid[x + y * GRID_W] = 4
      else if terrainType == "grass" grid[x + y * GRID_W] = 2
      else grid[x + y * GRID_W] = 1  // road/walkable
    }
  }
}

func findPath(startX, startY, endX, endY) {
  // A* with binary heap
  open = new PriorityQueue((a, b) -> a.f < b.f)
  closed = new Set()
  gScore = {}
  cameFrom = {}

  startKey = startX + "," + startY
  gScore[startKey] = 0
  open.enqueue({
    x: startX, y: startY, f: heuristic(startX, startY, endX, endY)
  })

  while open.size() > 0 {
    current = open.dequeue()
    currentKey = current.x + "," + current.y

    // Goal reached
    if current.x == endX && current.y == endY {
      return reconstructPath(cameFrom, currentKey)
    }

    closed.add(currentKey)

    // Check 8 neighbors
    neighbors = [
      [1,0], [-1,0], [0,1], [0,-1],  // 4-connected
      [1,1], [1,-1], [-1,1], [-1,-1]  // diagonals
    ]

    for n = 0 to neighbors.length {
      nx = current.x + neighbors[n][0]
      ny = current.y + neighbors[n][1]

      // Bounds check
      if nx < 0 || nx >= GRID_W continue
      if ny < 0 || ny >= GRID_H continue

      nKey = nx + "," + ny
      if closed.has(nKey) continue

      // Terrain cost
      tileCost = grid[nx + ny * GRID_W]
      if tileCost < 0 continue  // Wall

      // Diagonal movement costs more
      moveCost = (neighbors[n][0] != 0 && neighbors[n][1] != 0) ? 1.414 : 1.0
      tentativeG = gScore[currentKey] + moveCost * tileCost

      // Check if this is a better path
      if gScore[nKey] == null || tentativeG < gScore[nKey] {
        cameFrom[nKey] = currentKey
        gScore[nKey] = tentativeG
        f = tentativeG + heuristic(nx, ny, endX, endY)
        open.enqueue({ x: nx, y: ny, f: f })
      }
    }
  }

  return null  // No path found
}

// Manhattan heuristic (never overestimates on 4-connected grid)
func heuristic(x1, y1, x2, y2) {
  return math.abs(x1 - x2) + math.abs(y1 - y2)
}

// Reconstruct path from cameFrom map
func reconstructPath(cameFrom, endKey) {
  path = [endKey]
  current = endKey
  while cameFrom[current] != null {
    current = cameFrom[current]
    path.unshift(current)
  }
  // Convert keys to positions
  result = []
  for key in path {
    parts = string.split(key, ",")
    result.push(vec3(math.parse(parts[0]), 0, math.parse(parts[1])))
  }
  return result
}

// Path caching for shared destinations
pathCache = {}

func findPathCached(start, end) {
  cacheKey = start.x + "," + start.z + "->" + end.x + "," + end.z
  if pathCache[cacheKey] != null {
    return pathCache[cacheKey]
  }
  path = findPath(start.x, start.z, end.x, end.z)
  pathCache[cacheKey] = path
  return path
}

// Invalidate cache when terrain changes
on event("terrainChanged", data) {
  pathCache = {}  // Clear all cached paths
}

[A* Algorithm]
   --> [Init: open=PriorityQueue, closed=Set, gScore={}] --> [Start: g=0, f=heuristic]
   --> [While: open not empty]
        --> [Dequeue: lowest-f node]
        --> [Branch: goal reached?]
             +-- True --> [Reconstruct path] --> [Return]
        --> [Add: to closed set]
        --> [For Each: 8 neighbors]
             --> [Bounds + wall check]
             --> [Calculate: tentative g = currentG + moveCost * tileCost]
             --> [Branch: better than known g?]
                  +-- True --> [Update: cameFrom, gScore, f]
                            --> [Enqueue: into open]
   --> [Return: null (no path)]

[Function: heuristic] --> [Manhattan: |x1-x2| + |y1-y2|]

[Path Caching]
   --> [Check: cache key exists] --> [Return cached]
   --> [Else: compute + cache]
   --> [On terrainChanged: clear cache]