Image Path Finder Tool

async function processImage(originalImg, startRegion = "top", endRegion = "bottom", pathPreference = "bright", pathColor = "#ff0000", pathThickness = "3") {
  // To avoid freezing the browser on very large images, calculate the path on a downscaled version.
  const MAX_DIM = 400;
  let scale = 1;
  if (originalImg.width > MAX_DIM || originalImg.height > MAX_DIM) {
    scale = MAX_DIM / Math.max(originalImg.width, originalImg.height);
  }
  
  const W = Math.round(originalImg.width * scale);
  const H = Math.round(originalImg.height * scale);
  
  const offscreen = document.createElement('canvas');
  offscreen.width = W;
  offscreen.height = H;
  const ctxOff = offscreen.getContext('2d');
  ctxOff.drawImage(originalImg, 0, 0, W, H);
  const imgData = ctxOff.getImageData(0, 0, W, H).data;
  
  // Create a cost map based on image brightness. 
  // Using a cubic function ensures the algorithm strictly avoids walls (which represent massive costs).
  const cost = new Float32Array(W * H);
  const prefersDark = String(pathPreference).toLowerCase() === "dark";
  for (let i = 0; i < W * H; i++) {
    const r = imgData[i * 4];
    const g = imgData[i * 4 + 1];
    const b = imgData[i * 4 + 2];
    const lum = 0.299 * r + 0.587 * g + 0.114 * b;
    if (prefersDark) {
      cost[i] = 1 + Math.pow(lum, 3);
    } else {
      cost[i] = 1 + Math.pow(255 - lum, 3);
    }
  }

  // Fast Binary MinHeap for Dijkstra's Algorithm
  class MinHeap {
    constructor() {
      this.heap = [];
    }
    push(val, priority) {
      this.heap.push({val, priority});
      this.bubbleUp(this.heap.length - 1);
    }
    pop() {
      const h = this.heap;
      if (h.length === 0) return null;
      if (h.length === 1) return h.pop().val;
      const top = h[0].val;
      h[0] = h.pop();
      this.sinkDown(0);
      return top;
    }
    isEmpty() {
      return this.heap.length === 0;
    }
    bubbleUp(idx) {
      const h = this.heap;
      const el = h[idx];
      while (idx > 0) {
        let pIdx = (idx - 1) >>> 1;
        let parent = h[pIdx];
        if (el.priority >= parent.priority) break;
        h[idx] = parent;
        idx = pIdx;
      }
      h[idx] = el;
    }
    sinkDown(idx) {
      const h = this.heap;
      const len = h.length;
      const el = h[idx];
      while (true) {
        let leftIdx = (idx << 1) + 1;
        let rightIdx = leftIdx + 1;
        let swap = -1;
        
        if (leftIdx < len && h[leftIdx].priority < el.priority) {
          swap = leftIdx;
        }
        if (rightIdx < len) {
          if ((swap === -1 && h[rightIdx].priority < el.priority) ||
              (swap !== -1 && h[rightIdx].priority < h[leftIdx].priority)) {
            swap = rightIdx;
          }
        }
        if (swap === -1) break;
        h[idx] = h[swap];
        idx = swap;
      }
      h[idx] = el;
    }
  }

  const dist = new Float32Array(W * H).fill(Infinity);
  const prev = new Int32Array(W * H).fill(-1);
  const visited = new Uint8Array(W * H);
  const isEnd = new Uint8Array(W * H);
  const pq = new MinHeap();

  // Helper mapping regions to flat array indices
  function getRegionIndices(region) {
    const indices = [];
    region = String(region).toLowerCase();
    if (region === "top") {
      for (let x = 0; x < W; x++) indices.push(x);
    } else if (region === "bottom") {
      for (let x = 0; x < W; x++) indices.push((H - 1) * W + x);
    } else if (region === "left") {
      for (let y = 0; y < H; y++) indices.push(y * W);
    } else if (region === "right") {
      for (let y = 0; y < H; y++) indices.push(y * W + (W - 1));
    } else if (region === "top-left") {
      indices.push(0);
    } else if (region === "bottom-right") {
      indices.push(W * H - 1);
    } else if (region === "top-right") {
      indices.push(W - 1);
    } else if (region === "bottom-left") {
      indices.push((H - 1) * W);
    } else if (region === "center") {
      indices.push(Math.floor(H / 2) * W + Math.floor(W / 2));
    } else {
      for (let x = 0; x < W; x++) indices.push(x); // default to top
    }
    return indices;
  }

  const starts = getRegionIndices(startRegion);
  const ends = getRegionIndices(endRegion);
  
  for (let idx of ends) {
    isEnd[idx] = 1;
  }

  // Initialize start priorities inside the queue
  for (let idx of starts) {
    dist[idx] = cost[idx];
    pq.push(idx, dist[idx]);
  }

  // 8-Connected grid offsets (ensuring paths aren't strongly locked to taxi-cab geometry)
  const neighbors = [
    [-1, -1], [0, -1], [1, -1],
    [-1, 0],           [1, 0],
    [-1, 1],  [0, 1],  [1, 1]
  ];

  let endNode = -1;

  // Dijkstra's Shortest Path evaluation
  while (!pq.isEmpty()) {
    const current = pq.pop();
    if (current === null) break;
    
    // Prevent duplicate evaluation
    if (visited[current]) continue;
    visited[current] = 1;

    // Check if reached destination region
    if (isEnd[current]) {
      endNode = current;
      break;
    }

    const cx = current % W;
    const cy = Math.floor(current / W);

    for (const [dx, dy] of neighbors) {
      const nx = cx + dx;
      const ny = cy + dy;
      if (nx >= 0 && nx < W && ny >= 0 && ny < H) {
        const nIdx = ny * W + nx;
        if (visited[nIdx]) continue;
        
        // Diagonals cost slightly more mathematically
        const stepDist = (dx === 0 || dy === 0) ? 1 : 1.414;
        const newDist = dist[current] + cost[nIdx] * stepDist;
        
        if (newDist < dist[nIdx]) {
          dist[nIdx] = newDist;
          prev[nIdx] = current;
          pq.push(nIdx, newDist);
        }
      }
    }
  }

  // Output onto full-resolution canvas
  const outCanvas = document.createElement('canvas');
  outCanvas.width = originalImg.width;
  outCanvas.height = originalImg.height;
  const ctx = outCanvas.getContext('2d');
  ctx.drawImage(originalImg, 0, 0);

  // If a path was found, backtrack and trace it out
  if (endNode !== -1) {
    const path = [];
    let curr = endNode;
    while (curr !== -1) {
      path.push(curr);
      curr = prev[curr];
    }
    
    ctx.beginPath();
    for (let i = 0; i < path.length; i++) {
      const idx = path[i];
      const currX = (idx % W);
      const currY = Math.floor(idx / W);
      // Re-map back to the true resolution with +0.5 to anchor at the scaled pixel's exact center
      const x = (currX + 0.5) / scale;
      const y = (currY + 0.5) / scale;
      if (i === 0) ctx.moveTo(x, y);
      else ctx.lineTo(x, y);
    }
    ctx.strokeStyle = String(pathColor);
    ctx.lineWidth = parseInt(pathThickness) || 3;
    ctx.lineJoin = "round";
    ctx.lineCap = "round";
    ctx.stroke();
  }

  return outCanvas;
}