0

Description

"??? guide TL;DR\r\nAttach the main script somewhere. Invoke the `generate_kruskal` function that takes a `Vector2i` as maze size and an optional `int` as random seed. It returns a packed array (`PackedByteArray`) where each byte is a bit mask of the present walls on the four first bits (from low to high : norh, west, south, east). For a usage example see [the example below](#example).\r\n???\r\n\r\nThe present script allows generating a simple 2D maze made of square cells. It relies on the randomized Kruskal algorithm (cf. [Mazes For Programmers by Jamis Buck](http:\/\/mazesforprogrammers.com\/) ).\r\n\r\nIt only consists in a single function, `generate_kruskal` that takes the following parameters:\r\n- **size** : A `Vector2i` representing the width and height (in cells) of the maze. Each coordinate must be strictly greater than 1.\r\n- **sd** : An optional `int` that is used as a seed for the random number generator. Set to -1 by default, it won't change the seed.\r\n\r\nThe function returns a `PackedByteArray` containing data about walls for each cells as a bit mask. The mask is:\r\n- 1 : North\r\n- 2 : West\r\n- 4 : South\r\n- 8 : East\r\n\r\nAs usual, given a coordinate `(x, y)`, the corresponding cell index in the array is `x + y * size.x`.\r\n\r\n## Example{#example}\r\n\r\nLet's test this really quick. We will only need a `TileMapLayer` node. The generator script can be set as autoload or attached to a utility `Node`. For this example, I've used the following scene structure:\r\n\r\n\r\nThe main script is attached to the node `Generator`.\r\n\r\nThe `TileMapLayer` node (named `Maze` here) is configured with `TileSet` using this texture:\r\n\r\n\r\nThis texture contains all the cell configuration (0 to 4 exits).\r\n\r\nFinally, let's attach a script to the root `Node2D` (named `Main`) :\r\n??? guide Example Script\r\n```gdscript\r\nextends Node2D\r\n\r\n@export var maze_size : Vector2i\r\n\r\n# Enum mapping kind of cells and coordinate in the tileset\r\nenum {\r\n\tMAZE_CELL_X = 0, # Crossing\r\n\tMAZE_CELL_T = 1, # T-Shape (3 exits)\r\n\tMAZE_CELL_I = 2, # I-Shape (2 opposite exits)\r\n\tMAZE_CELL_U = 3, # U-Shape (1 exit)\r\n\tMAZE_CELL_L = 4, # L-Shape (2 adjacent exits)\r\n\tMAZE_CELL_O = 5 # Closed cell (no exits)\r\n}\r\n\r\n# Dictionary mapping maze cell value and coordinate tileset + alternative\r\n# given NORTH = 1, WEST = 2, SOUTH = 4, EAST = 8\r\nconst CELLS : Dictionary[int, Vector2i] = {\r\n\t0 : Vector2i(MAZE_CELL_X, 0), # NO WALL\r\n\t1 : Vector2i(MAZE_CELL_T, 0), # NORTH\r\n\t2 : Vector2i(MAZE_CELL_T, TileSetAtlasSource.TRANSFORM_TRANSPOSE), # WEST\r\n\t3 : Vector2i(MAZE_CELL_L, TileSetAtlasSource.TRANSFORM_FLIP_H), # WEST + NORTH\r\n\t4 : Vector2i(MAZE_CELL_T, TileSetAtlasSource.TRANSFORM_FLIP_V), # SOUTH\r\n\t5 : Vector2i(MAZE_CELL_I, TileSetAtlasSource.TRANSFORM_TRANSPOSE), # SOUTH + NORTH\r\n\t6 : Vector2i(MAZE_CELL_L, TileSetAtlasSource.TRANSFORM_FLIP_H + TileSetAtlasSource.TRANSFORM_FLIP_V), # SOUTH + WEST\r\n\t7 : Vector2i(MAZE_CELL_U, TileSetAtlasSource.TRANSFORM_TRANSPOSE), # SOUTH + WEST + NORTH\r\n\t8 : Vector2i(MAZE_CELL_T, TileSetAtlasSource.TRANSFORM_TRANSPOSE + TileSetAtlasSource.TRANSFORM_FLIP_H), # EAST\r\n\t9 : Vector2i(MAZE_CELL_L, 0), # EAST + NORTH\r\n\t10 : Vector2i(MAZE_CELL_I, 0), # EAST + WEST\r\n\t11 : Vector2i(MAZE_CELL_U, 0), # EAST + WEST + NORTH\r\n\t12 : Vector2i(MAZE_CELL_L, TileSetAtlasSource.TRANSFORM_TRANSPOSE + TileSetAtlasSource.TRANSFORM_FLIP_H), # EAST + SOUTH\r\n\t13 : Vector2i(MAZE_CELL_U, TileSetAtlasSource.TRANSFORM_TRANSPOSE + TileSetAtlasSource.TRANSFORM_FLIP_H), # EAST + SOUTH + NORTH\r\n\t14 : Vector2i(MAZE_CELL_U, TileSetAtlasSource.TRANSFORM_FLIP_V), # EAST + SOUTH + WEST\r\n\t15 : Vector2i(MAZE_CELL_O, 0), # ALL\r\n}\r\n\r\n@onready var maze : TileMapLayer = $Maze\r\n\r\n@onready var generator : MazeGenerator = $Generator\r\n\r\nfunc _ready() -> void:\r\n\trandomize()\r\n\treset_maze()\r\n\r\nfunc _input(event : InputEvent) -> void:\r\n\tvar kev : InputEventKey = event as InputEventKey\r\n\tif !kev:\r\n\t\treturn\r\n\tif kev.pressed and (not kev.echo) and kev.keycode == KEY_SPACE:\r\n\t\treset_maze()\r\n\r\nfunc reset_maze() -> void:\r\n\tassert(maze_size.x > 0 && maze_size.y > 0)\r\n\tmaze.clear()\r\n\tvar maze_data : PackedByteArray = generator.generate_kruskal(maze_size, randi() )\r\n\tvar idx : int = 0\r\n\tfor y in range(maze_size.y):\r\n\t\tfor x in range(maze_size.x):\r\n\t\t\tvar tile_data : int = maze_data[idx]\r\n\t\t\tassert(CELLS.has(tile_data))\r\n\t\t\tvar coords : Vector2i = CELLS[tile_data]\r\n\t\t\tmaze.set_cell(Vector2i(x, y), 0, Vector2i(coords.x, 2), coords.y)\r\n\t\t\tidx += 1\r\n```\r\n???\r\n\r\nThe script exports a `Vector2i` parameters named **maze_size** that control generated maze size. Each time you hit the space bar, a new maze is generated."

Screenshots

Main code

class_name MazeGenerator
extends Node

# Functions in this script generate mazes as PackedByteArrays.
# Each bytes contains the present walls, using the enum below as mask.

enum { MAZE_WALL_NORTH = 1, MAZE_WALL_WEST = 2, MAZE_WALL_SOUTH = 4, MAZE_WALL_EAST = 8 }

enum { CNX_HORIZONTAL = 0, CNX_VERTICAL }

# Generate a maze using Kruskal algorithm. Returns an array of bytes corresponding
# to masks of present wall.
func generate_kruskal(size : Vector2i, sd : int = -1) -> PackedByteArray:
	assert(size.x > 1 and size.y > 1)
	if sd >= 0:
		seed(sd)
	var count : int = size.x * size.y
	var maze : PackedByteArray = PackedByteArray()
	# The maze is initially composed of sealed rooms
	maze.resize(count); maze.fill(MAZE_WALL_NORTH + MAZE_WALL_WEST + MAZE_WALL_SOUTH + MAZE_WALL_EAST)
	# We start with a set per cell. They will be progressively merged until only one left
	var sets : PackedInt32Array = PackedInt32Array()
	sets.resize(count)
	var idx : int = 0
	for y in range(size.y):
		for x in range(size.x):
			sets[idx] = idx
			idx += 1
	# A connections is characterized by 4 parameters : x, y, horizontal/vertical, weight.
	# For convenience, we'll use a Vector4i
	var sorted_connections : Array[Vector4i] = []
	# Horizontal connections is a (x-1) * y matrix
	for y in range(size.y):
		for x in range(size.x - 1):
			sorted_connections.append(Vector4i(x, y, CNX_HORIZONTAL, randi()))
	# Vertical connections is a x * (y-1) matrix.
	for y in range(size.y - 1):
		for x in range(size.x):
			sorted_connections.append(Vector4i(x, y, CNX_VERTICAL, randi()))
	# Sort the connections according to their weight
	sorted_connections.sort_custom(func(a : Vector4i, b : Vector4i) -> bool :
		return a.w > b.w)
	# For all connections, from least weight to the most
	while not sorted_connections.is_empty():
		var c : Vector4i = sorted_connections.pop_back()
		var coord_a : Vector2i = Vector2i(c.x, c.y)
		var coord_b : Vector2i = Vector2i(c.x + 1, c.y) if c.z == CNX_HORIZONTAL else Vector2i(c.x, c.y + 1)
		var i_a : int = coord_a.x + coord_a.y * size.x; var i_b : int = coord_b.x + coord_b.y * size.x
		var set_a : int = sets[i_a]; var set_b : int = sets[i_b]
		if set_a == set_b: # the connection occurs in the same set, skip it
			continue
		# Depending on the nature of the connection, we remove walls from the adjacent cells
		if c.z == CNX_HORIZONTAL:
			maze[i_a] -= MAZE_WALL_EAST
			maze[i_b] -= MAZE_WALL_WEST
		else:
			maze[i_a] -= MAZE_WALL_SOUTH
			maze[i_b] -= MAZE_WALL_NORTH
		# Merge the two sets of cells
		var src_merge : int = max(set_a, set_b)
		var dst_merge : int = min(set_a, set_b)
		for i in range(count):
			if sets[i] == src_merge:
				sets[i] = dst_merge
	return maze

Comments