Maze

import sequence from "/scratchpad/_lib/sequence.asset.mjs"
import palette from "/scratchpad/_lib/palette.asset.mjs"
import * as random from "/scratchpad/_lib/random.asset.mjs"

const dpi = window.devicePixelRatio || 1

const last = (arr) => arr[arr.length - 1]

// Possible moves between grid cells
const moves = {
  N: { r: -1, c: +1 },
  E: { r: +0, c: +1 },
  S: { r: +1, c: -1 },
  W: { r: +0, c: -1 },
}

// Array of direction keys
const directions = Object.keys(moves)

// Map of opposite directions { a: "b", b: "a" ...}
const reverse = Object.fromEntries(
  directions.map((a) => [
    a,
    directions.find(
      (b) => moves[a].r === -moves[b].r && moves[a].c === -moves[b].c
    ),
  ])
)

// Move from one cell to another
const move = ({ r, c }, dir) => {
  const offset = moves[dir]
  return { r: r + offset.r, c: c + offset.c }
}

const getAvailableCells = (cell, cells) => {
  return directions.reduce((m, dir) => {
    const q = move(cell, dir)
    const p = cells.find((p) => p.r === q.r && p.c === q.c)

    if (p) m[dir] = p

    return m
  }, {})
}

const getTileImageIndex = (cell) => {
  const values = Object.fromEntries(
    directions.map((d, i) => [d, Math.pow(2, i)])
  )

  return (cell.joins || [])
    .filter((e, i, a) => a.indexOf(e) === i)
    .reduce((m, e) => m + values[e], -1)
}

export default async (canvas) => {
  canvas.width = canvas.offsetWidth * dpi
  canvas.height = canvas.offsetHeight * dpi

  const ctx = canvas.getContext("2d")

  const chanceToBranch = 0.15

  let cells = []
  let tiles = []

  const cellWidth = 48 * dpi
  const cellHeight = 32 * dpi

  const cols = Math.floor(canvas.width / cellWidth) - 3
  const rows = Math.floor(canvas.height / cellHeight) - 4

  let offset = [
    0.5 * (canvas.width - (cols - 1) * cellWidth),
    0.5 * (canvas.height - (rows - 1) * cellHeight),
  ]

  return sequence([
    // Fill canvas
    () => {
      ctx.fillStyle = palette.dark
      ctx.beginPath()
      ctx.rect(0, 0, canvas.width, canvas.height)
      ctx.fill()
    },

    // Create cells
    () => {
      for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
          cells.push({
            r,
            c,
          })
        }
      }

      // Top-left entry into grid
      cells.unshift({
        r: 0,
        c: -1,
      })

      // Bottom-right exit from grid
      cells.push({
        r: rows - 1,
        c: cols,
      })

      cells.forEach((p, i) => {
        p.i = i
        p.x = offset[0] + p.c * cellWidth
        p.y = offset[1] + p.r * cellHeight
      })
    },

    // Label cells
    () => {
      const fs = 6 * dpi
      ctx.font = `${fs}px sans`
      ctx.textAlign = "center"
      ctx.fillStyle = palette.canvas

      cells.forEach(({ i, x, y }) => ctx.fillText(i, x, y + fs * 0.4))
    },

    // Draw grid
    () => {
      ctx.beginPath()
      ctx.strokeStyle = palette.canvas

      cells.forEach((cell) => {
        ctx.moveTo(cell.x + cellWidth * 0, cell.y - cellHeight / 2)
        ctx.lineTo(cell.x + cellWidth * 1, cell.y - cellHeight / 2)

        ctx.moveTo(cell.x + cellWidth * 1, cell.y - cellHeight * 0.5)
        ctx.lineTo(cell.x + cellWidth * 0, cell.y + cellHeight * 0.5)

        if (cell.c <= 0 && cell.i !== 1) {
          ctx.moveTo(cell.x - cellWidth * 0, cell.y - cellHeight * 0.5)
          ctx.lineTo(cell.x - cellWidth * 1, cell.y + cellHeight * 0.5)
        }

        if (cell.c <= 0 || cell.r === rows - 1) {
          ctx.moveTo(cell.x - cellWidth * 1, cell.y + cellHeight / 2)
          ctx.lineTo(cell.x - cellWidth * 0, cell.y + cellHeight / 2)
        }
      })

      ctx.stroke()
    },

    () => {
      const stack = [cells[0]]
      const remaining = [...cells]
      let running = true

      ctx.lineWidth = cellWidth / 4
      ctx.lineCap = "round"
      ctx.lineJoin = "round"
      ctx.strokeStyle = palette.canvas
      ctx.beginPath()

      const goal = {
        c: cols + 1,
        r: rows,
      }

      const promise = new Promise((res) => {
        const explore = () => {
          if (!running) return

          let cell

          if (random.maybe(chanceToBranch)) {
            cell = random.sample(stack.slice(0, -1)) || stack[0]
          } else {
            cell = last(stack)
          }

          if (cell.c === goal.c && cell.r === goal.r && !solved) {
            solved = true
          }

          const available = getAvailableCells(cell, remaining)
          const entries = Object.entries(available)

          if (entries.length) {
            const [dir, next] = random.sample(entries)

            ctx.moveTo(cell.x, cell.y)
            ctx.lineTo(next.x, next.y)

            cell.joins = cell.joins || []
            next.joins = next.joins || []

            cell.joins.push(dir)
            next.joins.push(reverse[dir])
            next.from = cell

            // Remove from remaining available tiles
            remaining.splice(remaining.indexOf(next), 1)

            stack.push(next)
          } else {
            stack.splice(stack.indexOf(cell), 1)
          }

          if (stack.length > 0) {
            explore()
          } else {
            res()
          }
        }

        explore()
      }).then(() => {
        ctx.stroke()
      })

      return {
        promise,
        cancel: () => {
          running = false
        },
      }
    },

    // Load tile images
    () => {
      return Promise.all(
        Array.from({ length: 15 }, (e, i) => {
          const img = new Image()
          img.src = `/assets/img/scratchpad/maze/tile-${i + 1}.svg`
          tiles[i] = img

          return new Promise((res, rej) => {
            img.onload = res
            img.onerror = rej
          })
        })
      )
    },

    // Fill background
    () => {
      ctx.beginPath()
      ctx.rect(0, 0, canvas.width, canvas.height)
      ctx.fillStyle = palette.dark
      ctx.fill()
    },

    // Draw tile images
    () => {
      cells.forEach((cell) => {
        const img = tiles[getTileImageIndex(cell)]
        if (img) {
          ctx.drawImage(
            img,
            cell.x - cellWidth,
            cell.y - cellHeight / 2,
            cellWidth * 2,
            cellHeight
          )
        } else {
          console.log("No tile available at index:", getTileImageIndex(cell))
        }
      })
    },

    // Draw solution
    // Because of the initial search pattern, we can trace
    // back along the `from` key to find the original tile
    () => {
      const stack = [...cells].reverse()

      let cell = stack[0]
      const solution = [cell]

      while (cell.i !== 0) {
        cell = cell.from
        solution.push(cell)
      }

      ctx.beginPath()
      solution.forEach((p) => ctx.lineTo(p.x, p.y))
      ctx.strokeStyle = palette.dark
      ctx.lineWidth = 1
      ctx.stroke()
    },
  ])
}