First, the direction of movement is randomized. Then, the step is made and recorded on a stack.
| [1] | [X] | |
STACK:
RIGHT
| [X] | ||
| [1] | [2] | |
STACK:
RIGHT
UP
This cycle repeats until there is no turn available - then values are taken one by one from the stack and each step is repeated in reverse, e.g. step to the left means we now step to the right.
| [5] | [4] | [3] |
| [6] | [1] | [2] |
| [7] | [8] | [X] |
STACK:
RIGHT
UP
LEFT
LEFT
DOWN
DOWN
RIGHT
RIGHT
| [5] | [4] | [3] |
| [6] | [1] | [2] |
| [X] | [#] | [#] |
STACK:
RIGHT
UP
LEFT
LEFT
DOWN
DOWN
RIGHT
RIGHT
Every step back a check is run if any other direction of movement except of the return direction is available. If there is any available, the next step direction is randomized from available directions. Then the first cycle is applied as previously described. For each visited cell that is not on a stack anymore we leave a mark (#) meaning the cell was visited once and should not be revisited.The algorithm finishes when the stack is empty.
There is a simplification in the example above. To represent the maze we need data about walls. The solution is simple - make grid bigger and jump two cells at a time. Also mark in-between cells as visited.
| [5] | [#] | [4] | [#] | [3] | ||
| [#] | [#] | |||||
| [6] | [1] | [#] | [2] | |||
| [#] | ||||||
| [X] | [#] | [#] | [#] | [#] | ||
So this more or less how it works - and now you can try it for yourself. Simply clone the repository from here and build the program. Make sure you have required dependencies (OpenGL, glfw, X11, glad etc. - check Makefile). Camera zoom is adjustable by using Q and E keyboard keys.
