Maze Generation with Recursive Backtracker Algorithm

Hello.

I want to generate a maze procedurally using the Apparance.
A maze generated using the Recursive Backtracker algorithm would be ideal, but I don’t know how to do it with Apparance.
Do you have ideas on how to implement the Recursive Backtracker algorithm in Apparance?

The basic algorithm of the Recursive Backtracker is

  1. Given a current cell as a parameter
  2. Mark the current cell as visited
  3. While the current cell has any unvisited neighbour cells
    1. Choose one of the unvisited neighbours
    2. Remove the wall between the current cell and the chosen cell
    3. Invoke the routine recursively for the chosen cell

which is invoked once for any initial cell in the area.

1 Like

Hi, good question. I may need to think about the best implementation of this as Apparance can be considered a ‘functional language’, in that state is immutable, this means, for example, that an array of cell information is copied whenever a change is made. There are ways around this (you could store the cell state as an Image [experimental feature] instead (which, like geometry, operate outside the immutable data). Regardless of the approach I would suggest something like this approach:

  1. Fill a cell grid with zeros (either a 1D List of Int, or a Black Low Precision Image).
  2. Each value in a cell represents bit flags of the directions you can leave the cell, e.g. 1=north, 2=south, 4=west, 8=east, 0 meaning an unused and non-navigable cell. By combining these values you store four independant flags. (see: bitfields and flags).
  3. Follow the algorithm you describe, where
    a. Marking a cell as visited by the flag being set showing which neighbouring cells you can get to.
    b. Choosing unvisited neighbours is just looking for 0 to N/S/W/E directions (avoiding edge of grid).
    c. There is no ‘removing the wall’ as you are instead storing the ‘I can go in this direction’.
    d. Advancing to a neighbouring cell means you set both cells to ‘point’ to each other since you can go both ways.
    e. The recursing bit would be invoking the same procedure (embed a proc node in itself) with a different cell coordinate.
    f. For immutable lists, the new grid will need to be passed down into the recursed procedure and then passed back up once it’s been modified further. For mutable images, you only need to pass them down as the state is shared.
    g. If you need to actually build the geometry as you go, you can do this for a cell/room whenever you leave it to drop back up the recursion. At this point you know what all the entry/exit points for it are.

This should work, but if you are using lists you may be limited on the number of cells you can work on, the image based version allowing many more.

There are some interesting effects and possibilities with this approach:

  1. Randomly modifying cells afterwards to add extra links (more routes through maze, and loops), although you risk shortcutting it a bit.
  2. Using other flags in each cell to build up and then later indicate the direct route back to the starting cell from anywhere (not necessarily the fastest if you’re added extra links).
  3. Adding links that are one-way, that you can later build out as one-way doors or wall+ladder, etc.
  4. You can take the cell grid and then build the actual maze geometry from it, but you don’t have to do this all at once, you could instead place ‘markers’ in the world where each cell is with the information about it’s connections that later spawn the actual walls/floor/etc when the player approaches (on-demand maze building, for efficiency).
  5. Additional lists/images to indicate where treasure/enemies, etc. are in the map so that when you generate the maze geometry you can include gameplay elements.
  6. These mazes can be used in a modular fashion and placed down next to each other with doorways between. This allows splitting up of the maze into separate procedural generation tasks. Each maze grid can have access points added on any edge that is next to a populated cell.

I hope these ideas are useful and I look forward to seeing your results. Let us know how you get on.