Spiele - Labyrinth zeichnen mit Excel

Maze generation

Methods to find a way out of a maze have been descried aundantly. This contribution describes how to generate a maze.

Algorithm of Wilson

Wilson's algorithm generates a maze through a sequence of random walks with loop elimination. Starting from a randomly chosen cell, an inital walk is created, with a final length equal to the sum of width and height of the maze range. This walk is the initial maze.

A new random walks is begun, starting from cells not yet covered by the maze, and pursued until

1. encounters its own trace, which indicates a loop. The loop is removed and the walk is resumed from the cell encountered
2. hits the maze, in which case the walk is joined to the maze

New walks are begun while there are cells not covered by the maze.

Demo video

The video shows the generation and drawing of a maze by the VBA-Module in the Excel workbook developed for this purpose.