Maze Generation Using DFS with specific movement rules

Question

I have specific need of generating route/maze with some movement constrains.

Given the random picked cell in Matrix of 10x10 where level is number of movable fields that needs to be generated, generate the route trough Matrix.

Movement constrains are as follows:

• Exactly 3 cells horizontally and vertically
• Exactly 2 cells in all diagonally
• You can not step on the same field twice

I have figured it out for lower levels but generating max lvl is currently impossible.

I can't seem to wrap my head around backtracking properly.

interface Cell extends Cords {
  visited: boolean
  neibhoursAvailable: Cords[]
  pickedEdge: Cords | {}
}

interface Cords {
  x: number
  y: number
}

type Matrice = Cell[][]

const rand = (arr: Cords[]) => {
  return arr[~~(Math.random() * arr.length)]
}

const matrix = (width: number, height: number): Cell[][] => {
  return Array(width)
    .fill({
      x: 0,
      y: 0,
      visited: false,
      neibhoursAvailable: [],
      pickedEdge: {},
    })
    .map(() =>
      Array(height).fill({
        x: 0,
        y: 0,
        visited: false,
        neibhoursAvailable: [],
        pickedEdge: {},
      }),
    )
}

const createCell = (
  x: number,
  y: number,
  visited: boolean,
  neibhoursAvailable: [],
): Cell => {
  return { x, y, visited, neibhoursAvailable, pickedEdge: {} }
}

let matrice = matrix(10, 10).map(
  (i, idx): Cell[] => {
    return i.map((_, idy) => {
      return {
        x: idx,
        y: idy,
        visited: false,
        neibhoursAvailable: [],
        pickedEdge: {},
      }
    })
  },
)

const checkTraversability = (
  startCords: Cords,
  matrice: Matrice,
): Cell | undefined => {
  // Check left
  console.log(startCords)
  if (startCords.x === undefined) {
    return undefined
  }
  if (startCords.y === undefined) {
    return undefined
  }
  const { x, y } = startCords
  const cell: Cell = matrice[x][y]

  if (cell.x - 3 >= 0 && !matrice[cell.x - 3][cell.y].visited) {
    cell.neibhoursAvailable.push({ x: cell.x - 3, y: cell.y })
  }

  // Check right
  if (cell.x + 3 < 10 && !matrice[cell.x + 3][cell.y].visited) {
    cell.neibhoursAvailable.push({ x: cell.x + 3, y: cell.y })
  }

  if (cell.y - 3 >= 0 && !matrice[cell.x][cell.y - 3].visited) {
    cell.neibhoursAvailable.push({ x: cell.x, y: cell.y - 3 })
  }
  if (cell.y + 3 < 10 && !matrice[cell.x][cell.y + 3].visited) {
    cell.neibhoursAvailable.push({ x: cell.x, y: cell.y + 3 })
  }

  // Check Diagonals

  if (
    cell.x + 2 < 10 &&
    cell.y + 2 < 10 &&
    !matrice[cell.x + 2][cell.y + 2].visited
  ) {
    cell.neibhoursAvailable.push({ x: cell.x + 2, y: cell.y + 2 })
  }

  if (
    cell.x + 2 < 10 &&
    cell.y - 2 >= 0 &&
    !matrice[cell.x + 2][cell.y - 2].visited
  ) {
    cell.neibhoursAvailable.push({ x: cell.x + 2, y: cell.y - 2 })
  }

  if (
    cell.x - 2 >= 0 &&
    cell.y + 2 < 10 &&
    !matrice[cell.x - 2][cell.y + 2].visited
  ) {
    cell.neibhoursAvailable.push({ x: cell.x - 2, y: cell.y + 2 })
  }

  if (
    cell.x - 2 >= 0 &&
    cell.y - 2 >= 0 &&
    !matrice[cell.x - 2][cell.y - 2].visited
  ) {
    cell.neibhoursAvailable.push({ x: cell.x - 2, y: cell.y + 2 })
  }
  return cell
}

let stack: Cell[] = []

const generateMaze = (
  matrice: Cell[][],
  stack: Cell[],
  startCords: { x: number; y: number },
  level: number,
) => {
  const traversable = checkTraversability(startCords, matrice)
  if (level >= 0) {
    traversable.visited = true
    const randomEdge = rand(traversable.neibhoursAvailable)
    traversable.neibhoursAvailable = traversable.neibhoursAvailable.filter(
      i => !(i.x === randomEdge.x && i.y === randomEdge.y),
    )
    traversable.pickedEdge = randomEdge
    stack.push(traversable)
    generateMaze(matrice, stack, randomEdge, level - 1)
  }
  return matrice
}

const gen = generateMaze(matrice, stack, { x: 0, y: 0 }, 10)
console.log(gen)

Any suggestions or guidance will be appreciated.

Answer 1

Indeed, the backtracking poses a problem.

Some issues:

• There is a bug near the end of checkTraversability: you push a coordinate with cell.y + 2 while it should be cell.y - 2
• The matrix function has a useless argument passed to the first fill() call. That value is never used, since you map that array to become a 2D array, so that first fill might just be fill(null).
• There is a loop missing for when the randomly chosen edge leads to no solution and another one should be selected and tried with.
• The generateMaze returns matrice, but you could reserve the return value for something more useful, since the caller will already have access to matrice which it passed to the function in the first place, and which gets mutated by the call.
• There is no need to have a global stack variable, and pass it to the function. Instead you can build it in reverse, starting at the moment when you have reached level 0. You could return then a path with just that final cell and while backtracking you could prepend that path with the current cell. In the end you will have the path you want to have as return value of the initial call.
• I don't see a need to remove selected edges from a cell's neighbor list, as you don't intend to visit that cell again anyway. On the other hand, the condition that a cell cannot be visited twice is enough to avoid that the same edge is followed.
• There needs to be a distinction in the return value to indicate that the search was successful or not. In case of success you could return the path (as mentioned above), and in the case of failure, you could return undefined.
• The function should return undefined when checkTraversability returns an empty array and we're not yet at level 0.
• You should only mark an edge as "picked" when it is certain that the recursive call successfully found a solution.
• Don't forget to remove the visited mark when there is no edge that leads to a solution
• Instead of picking one random edge using rand, create a function that shuffles the edges, and then iterate over them until one brings success. If none bring success, then return undefined.

Here are some code parts you could use:

The shuffle function:

function shuffle(a) {
    for (let i = a.length - 1; i > 0; i--) {
        let j = Math.floor(Math.random() * (i + 1));
        let x = a[i];
        a[i] = a[j];
        a[j] = x;
    }
    return a;
}

The generateMaze function

const generateMaze = (
  matrice: Cell[][],
  startCords: { x: number; y: number },
  level: number,
) => {    
  const traversable = checkTraversability(startCords, matrice);
  traversable.visited = true;
  if (level <= 0) return [traversable]; // found a solution: just return the end of the path
  for (let randomEdge of shuffle([...traversable.neibhoursAvailable])) {
    // Not needed to remove edge.
    let path = generateMaze(matrice, randomEdge, level - 1);
    if (path) { // Success: Only now mark the edge as picked
      traversable.pickedEdge = randomEdge;
      return [traversable, ...path]; // and backtrack building the path
    }
  }
  // failure: unmark this node (!), and just return undefined
  traversable.visited = false;
}

const path = generateMaze(matrice, { x: 0, y: 0 }, 10);
console.log(path);

This will actually return a path with 11 cells and 10 edges. I was not sure if level 10 meant 10 other cells or included the starting cell. If this needs to be one less, then change if (level <= 0) to if (level <= 1).