explore-nodes.ts

function exploreNodes(nodes, exploredNodes) {
  if (nodes.length === 0) return

  // sort nodes by cost
  nodes.sort((a, b) => a.cost < b.cost ? -1 : 0)

  // remove the lowest cost node from the list
  const lowestCostNode = nodes.shift()

  // add it to the explored nodes
  exploredNodes.push(lowestCostNode)
  
  // add any nodes around it that haven't been explored yet
  for (let neighborX = -1; neighborX <= 1; neighborX += 1) {
    for (let neighborY = -1; neighborY <= 1; neighborY += 1) { 
      // if it's the center of the 3x3 grid, ignore it
      if (neighborX === 0 && neighborY === 0) continue;

      // calculate the actual position in the world
      const nx = lowestCostNode.x + neighborX
      const ny = lowestCostNode.y + neighborY

      // if it's already in the set of nodes we are exploring, ignore it
      if (nodes.find(node => node.x === nx && node.y === ny)) continue
      // if it's already been explored, ignore it
      if (exploredNodes.find(node => node.x === nx && node.y === ny)) continue

      // must be a new node -- let's explore it!
      // diagonal moves cost 1.4, horizontal / vertical cost 1
      const cost = (neighborX === 0 || neighborY === 0) ? 1 : 1.4
      // now let's make a new explorable node
      nodes.push({
        x: nx,
        y: ny,
        cost: lowestCostNode.cost + cost,
        previous: lowestCostNode
      })
    }
  }
}