/maze

Recursive backtracking depth first search to generate a maze from a rectangular grid.

Primary LanguageJavaScript

Maze Generation

Simple JavaScript recursive backtracking implementation of a maze with shortest path from top left to center of maze overlaid on the maze.

Demo

Screenshot of maze generated by the program.

TODO

  • Redo with AMD instead of contructor fn + prototype.
  • Performance tests.
  • Unit tests.
  • Typed Arrays for speed.
  • Without using a grid, cells as linked list.
  • Use adjacency list, adjacency matrix.
  • Animate shortest path drawing.
  • Use seeds to be able to reproduce a given maze.

Reference Documentation

Steps

  • Start with a grid that has every possible wall filled in.
  • Choose a cell to start from.
  • From your current cell, choose a random neighbor that you haven't visited before and move to that cell, knocking down the wall between them.
  • If there are no unvisited neighbors, backtrack to the previous cell you were in and repeat.
  • Otherwise, repeat from your new cell.

Links