Maze generating algorithm in grid

Question

What is the best algorithm to generate a maze in a grid?

I have heard of Kruskal's algorithm and the recursive backtracker amongst other but both of these rely on walls.What would be the best algorithm to create amaze where one entire cell is a wall?

Answer 1

Modifying recursive backtracking or Prim's algorithm should be simple enough (code derived from Wikipedia)

Randomized Prim's algorithm

• Start with a grid of filled cells.
• Pick a cell, mark it as part of the maze. Add the surrounding filled cells of the cell to the cell list.
• While there are cells in the list:
  • Pick a random cell from the list. If the cell doesn't have 2 explored neighbours:
    • Clear the cell.
    • Add the neighbouring filled cells to the cell list.
  • Remove the cell from the list.