Backtracking

Maze generation using backtracking.

Created by kellyjosephprice on 2018/12/20
106
0

Log in to post a comment.

const OFFSETS = [[-1, 0], [0, -1], [1, 0], [0, 1]]

const getRandomInt = max => Math.floor(Math.random() * max)
const getRandomElement = array => array[getRandomInt(array.length)]

class Nodes {
  static offset([x, y]) {
    return [x - 100, y - 100]
  }

  constructor() {
    this.nodes = Array.from(Array(201)).map(() => Array.from(Array(201)))
    this.queue = []
  }

  hasNext() {
    return this.queue.length > 0
  }

  next() {
    const index = getRandomInt(this.queue.length)
    return this.queue.splice(index, 1)[0]
  }

  visit([x, y]) {
    this.nodes[x][y] = true
    this.queue.push([x, y])

    return this
  }

  visible([x, y]) {
    return 0 <= x && x <= 200 && 0 <= y && y <= 200
  }

  getAdjacent([x, y]) {
    return OFFSETS.map(([xOffset, yOffset]) => ([x + xOffset, y + yOffset]))
      .filter(([_x, _y]) => this.visible([_x, _y]))
  }

  getUnvisitedNodes(node) {
    return this.getAdjacent(node).filter(([x, y]) => !this.nodes[x][y])
  }
}

Canvas.setpenopacity(-1)
const turtle = new Turtle()
const nodes = new Nodes()

nodes.visit([getRandomInt(201), getRandomInt(201)])

const walk = i => {
  if (!nodes.hasNext()) {
    console.log('done')
    return
  }

  const current = nodes.next()

  const neighbors = nodes.getUnvisitedNodes(current)

  if (neighbors.length) {
    const neighbor = getRandomElement(neighbors)

    turtle.penup()
    turtle.goto(...Nodes.offset(current))
    turtle.pendown()
    turtle.goto(...Nodes.offset(neighbor))

    nodes.queue.push(current)
    nodes.visit(neighbor)
  }

  return i < 1000000
}