## Creates a maze using the [url=https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_depth-first_search]recursive backtracker algorithm[/url].
extends Resource
class_name Maze
## This mazes size.
var size: Vector2i
## The maze, in a 2d array.
## Type: [Array][[Array][[PackedInt32Array]].
var maze := []
## The north constant.
const N := 1
## The east constant.
const E := 2
## The south constant.
const S := 4
## The west constant.
const W := 8
## The N E S W mappings to UP RIGHT DOWN LEFT
const cell_walls := {Vector2i.UP: N, Vector2i.RIGHT: E, Vector2i.DOWN: S, Vector2i.LEFT: W}
const _dirs := [Vector2i.UP, Vector2i.RIGHT, Vector2i.DOWN, Vector2i.LEFT]
## The image representation of this maze.
var image: Image = null:
get:
if not image:
_gen_image()
return image
func _init(p_size: Vector2i) -> void:
size = p_size
generate()
erase_walls()
## Get a maze cells value.
func get_cellv(cell: Vector2i) -> int:
return maze[cell.y][cell.x]
## Turns a 4b tile into a array of walls. [code]4[/code] => [code][Vector2i.DOWN][/code].
static func tile_4b_to_wall_array(tile_4b: int) -> Array[Vector2i]:
var array: Array[Vector2i] = []
for dir in _dirs:
if tile_4b & cell_walls[dir]:
array.append(dir)
return array
## Turns a 4b tile into a array of paths. [code]4[/code] => [code][Vector2i.UP, Vector2i.LEFT, Vector2i.RIGHT][/code].
static func tile_4b_to_path_array(tile_4b: int) -> Array[Vector2i]:
var array: Array[Vector2i] = []
for dir in cell_walls.keys():
if not tile_4b & cell_walls[dir]:
array.append(dir)
return array
func _check_neighbours(cell: Vector2i, unvisited: Array[Vector2i]) -> Array[Vector2i]:
# checks if neighbour is visited.
# returns array of unvisited neighbours.
var list: Array[Vector2i] = []
for n in cell_walls.keys():
if cell + n in unvisited:
list.append(cell + n)
return list
func _set_cellv(cell: Vector2i, v: int) -> void:
maze[cell.y][cell.x] = v
## Generates the maze using the [url=https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_depth-first_search]recursive backtracker algorithm[/url].
func generate() -> void:
randomize()
var unvisited: Array[Vector2i] = []
var stack: Array[Vector2i] = []
# fill maze
maze.clear()
for x in range(size.x):
var row: PackedInt32Array = []
for y in range(size.y):
row.append(N|E|S|W)
unvisited.append(Vector2i(x, y))
maze.append(row)
var current := Vector2i(0, 0)
unvisited.erase(current)
# recurive backtracking algorithm
while unvisited.size() > 0:
# check neighbours of current cell.
var neighbours := _check_neighbours(current, unvisited)
# if neighbours exist, pick one at random and move in that direction.
# remove wall between current cell and neighbour cell.
if neighbours.size() > 0:
var next := neighbours[randi() % neighbours.size()]
stack.append(current)
# remove wall from both cells.
var dir := next - current
var current_walls: int = get_cellv(current) - cell_walls[dir]
var next_walls: int = get_cellv(next) - cell_walls[-dir]
_set_cellv(current, current_walls)
_set_cellv(next, next_walls)
current = next
unvisited.erase(current)
elif stack:
# if neighbours don't exist, retrieve new current from stack.
current = stack.pop_back()
## Randomly remove walls. Prefers deleting 3 and 2 walled cells.
func erase_walls() -> void:
randomize()
const three_walls: Array[int] = [7, 11, 13, 14]
const two_walls: Array[int] = [3, 5, 6, 9, 10, 12]
for x in range(size.x):
for y in range(size.y):
if maze[y][x] in three_walls or maze[x][y] in two_walls or randi() % 3 == 0:
var cell := Vector2i(x, y)
var i := randi() % 4
for _i in range(4):
var n: Vector2i = cell_walls.keys()[i]
i = wrapi(i + _i, 0, 3)
if get_cellv(cell) & cell_walls[n]:
var n_cell := (cell + n)
if n_cell.x > size.x - 1 or n_cell.y > size.y - 1 or n_cell.x < 0 or n_cell.y < 0:
continue
var walls: int = get_cellv(cell) - cell_walls[n]
var n_walls: int = get_cellv(n_cell) - cell_walls[-n]
if (
(x == 0 and walls & W)
or (y == 0 and walls & N)
or (x == size.x and walls & E)
or (y == size.y and walls & S)
or (n_cell.x == 0 and n_walls & W)
or (n_cell.y == 0 and n_walls & N)
or (n_cell.x == size.x and n_walls & E)
or (n_cell.y == size.y and n_walls & S)
):
continue
if walls in three_walls or n_walls in three_walls:
continue
_set_cellv(cell, walls)
_set_cellv(n_cell, n_walls)
break
func _gen_image() -> void:
var img = Image.create(size.x * 3, size.y * 3, false, Image.FORMAT_L8)
var position := Vector2i.ZERO
for i in len(maze):
for j in len(maze[i]):
var paths := Maze.tile_4b_to_path_array(maze[i][j])
if not paths.is_empty():
var middle := position + Vector2i.ONE
img.set_pixelv(middle, Color.WHITE)
for path in paths:
img.set_pixelv(middle + path, Color.WHITE)
position.x += 3
position.y += 3
position.x = 0
image = img