Hello everyone,
Eller's Algorithm is an algorithm for generating mazes.
Here's what it looks like:
The way it works is it walks down the maze, one row at a time, sorting cells in sets and randomly placing walls, based on certain criteria. Since it only needs to keep the last row in memory, you can use it to generate infinitely tall mazes.
But it's known as one of the hardest algorithms to implement due to its reliance on sets (which require lots of state management) and complex series of checks.
But what if I told you that states are a lie told to you by the government?
This implementation exploits a regularity of the finished rows: There is never a wall inside of a set. The only exception is a brief step during row creation, but that information is lost as soon as it moves on to the next. If you can guarantee an unbiased distribution of the bottom walls, then it is possible to have a completely stateless version of Eller's algorithm. I couldn't, so instead I kept an array with the open cells in the current room.
Anyway, here's the code:
extends Node2D
# Eller's algorithm: http://www.neocomputer.org/projects/eller.html
# Tileset from https://kidscancode.org/blog/2018/08/godot3_procgen1/
# These constants define the presence of WALLS, not ROADS,
# e.g. W means that a cell has passages N, E and S.
const N = 1
const E = 2
const S = 4
const W = 8
var tile_size := 64 # tile size (in pixels)
var width := 9 # width of map (in tiles)
var height := 9 # height of map (in tiles)
var bias := 0.7 # > 0.5 makes more horizontal mazes
# get a reference to the map for convenience
onready var Map: TileMap = $TileMap
func _ready():
randomize()
make_first_row()
for x in range(1, height):
make_row(x, x == height - 1)
# The first row differs from the rest in that all cells have a
# N wall, and it doesn't reference an earlier row.
func make_first_row():
Map.set_cell(0, 0, N | W)
var set = [Vector2(0, 0)]
for col in range(1,width):
Map.set_cell(col, 0, N)
set = _union(set, Vector2(col, 0))
_set_bounds(0)
# The main algorithm. If last is true, it will generate a last row.
# The last row only has E/W walls under horizontal passages
# (i.e. 2 same-set cells without S walls)
func make_row(row: int, last: bool = false):
assert(row > 0, "%s" % row)
# All of the cells in the current room without a S wall
# _union() chooses one of these when it decides to add a S wall
var set = [Vector2(0, row)]
# The cell N of the current cell
var c: int
# The cell NW of the current cell
# This is used to detect horizontal corridors
var last_cell = Map.get_cellv(Vector2(0, row - 1))
# Initialise 1st cell
Map.set_cell(0, row, W)
# If last_cell has a S wall
if last_cell & S == S:
_wall(0, row, N)
for col in range(1, width):
# Update counters
c = Map.get_cell(col, row - 1)
last_cell = Map.get_cell(col - 1, row - 1)
# If c has no S wall
if c & S == 0:
Map.set_cell(col, row, 0)
# If last_cell has no S, nor E/W wall
if (last_cell & S) == 0 and last_cell & E == 0:
# Force an E/W wall on the current cell and start a new
# set
_make_wall(Vector2(col, row))
set = [Vector2(col, row)]
else:
Map.set_cell(col, row, N)
if last:
# Add a S wall and remove E/W walls
_wall(col, row, S & ~(W | E))
else:
# Join the cells. See _union() below
set = _union(set, Vector2(col, row))
_set_bounds(row, row == height - 1)
func _union(set: Array, cell: Vector2):
# Randomly add a W wall. See _make_wall() below
if randf() > bias:
_make_wall(cell)
# Start a new set
set = [cell]
else: # Continue set
# Join cells
set.append(cell)
# Randomly add a S wall
if randf() < bias:
# Pick a random open cell (without a S wall)
var i = randi() % set.size()
# Add S wall, remove cell from set
_wallv(set[i], S)
set.remove(i)
return set
#### Helper functions
# Add a W wall to cell and an E wall to the cell before it.
# This is just a quirk of working with tilesets.
# This function assumes that both cells are valid and that cell > 0
func _make_wall(cell: Vector2):
assert(cell.x > 0, "%s" % cell)
assert(Map.get_cellv(cell) > -1, "%s" % cell)
var prev_cell := cell - Vector2(1, 0)
assert(Map.get_cellv(prev_cell) > -1, "%s" % prev_cell)
_wallv(prev_cell, E)
_wallv(cell, W)
# Force the first and last cells of a row to have a W and E wall
# respectively. Force a S wall, too, if last is true.
func _set_bounds(row: int, last: bool = false):
_wall(0, row, W)
_wall(width - 1, row, E)
if last:
_wall(0, row, S)
_wall(width - 1, row, S)
# Add walls to cell. This function assumes that the cell is valid
# and that walls is some combination of the consts above
func _wallv(cell: Vector2, walls: int):
assert((N | E | S | W) & walls > 0, "%x" % walls)
assert(Map.get_cellv(cell) > -1, "%s" % cell)
Map.set_cellv(cell, Map.get_cellv(cell) | walls)
# Add walls to cell at col, row. This function assumes that the cell is valid
# and that walls is some combination of the consts above
func _wall(col: int, row: int, walls: int):
assert((N | E | S | W) & walls > 0, "%x" % walls)
assert(Map.get_cell(col, row) > -1, "%s" % Vector2(col, row))
Map.set_cell(col, row, Map.get_cell(col, row) | walls)
