Gerador de labirinto

extends Node

const COLUMNS: int = 31
const ROWS: int = 17
const PER_FRAME: int = 10
const SEED: int = 20260814

const WALL: Color = Color('#2a2f3d')
const CARVED_START: Color = Color('#8da5f3')
const CARVED_END: Color = Color('#8eef97')

const DIRECTIONS: Array = [Vector2i.RIGHT, Vector2i.LEFT, Vector2i.DOWN, Vector2i.UP]

var rng: RandomNumberGenerator = RandomNumberGenerator.new()
var steps: Array[Vector2i] = []
var revealed: int = 0
var image: Image
var texture: ImageTexture


func _ready() -> void:
	_add_background()

	rng.seed = SEED
	image = Image.create(COLUMNS * 2 + 1, ROWS * 2 + 1, false, Image.FORMAT_RGBA8)
	image.fill(WALL)

	_carve()

	texture = ImageTexture.create_from_image(image)

	var view: Vector2 = get_viewport().get_visible_rect().size
	var pixel: float = maxf(1.0, floorf(minf(view.x / image.get_width(), view.y / image.get_height())))

	var maze: Sprite2D = Sprite2D.new()
	maze.texture = texture
	maze.texture_filter = CanvasItem.TEXTURE_FILTER_NEAREST
	maze.scale = Vector2(pixel, pixel)
	maze.position = view * 0.5
	add_child(maze)

	print('a backtracker carves every cell exactly once, change SEED for another maze')


func _process(_delta: float) -> void:
	if revealed >= steps.size():
		return

	var target: int = mini(revealed + PER_FRAME, steps.size())

	while revealed < target:
		image.set_pixelv(steps[revealed], CARVED_START.lerp(CARVED_END, float(revealed) / steps.size()))
		revealed += 1

	texture.update(image)


func _carve() -> void:
	var visited: Dictionary = {Vector2i.ZERO: true}
	var stack: Array[Vector2i] = [Vector2i.ZERO]

	steps.append(_to_pixel(Vector2i.ZERO))

	while not stack.is_empty():
		var cell: Vector2i = stack[stack.size() - 1]
		var options: Array[Vector2i] = []

		for direction in DIRECTIONS:
			var next: Vector2i = cell + direction

			if next.x >= 0 and next.x < COLUMNS and next.y >= 0 and next.y < ROWS and not visited.has(next):
				options.append(next)

		if options.is_empty():
			stack.pop_back()
			continue

		var chosen: Vector2i = options[rng.randi_range(0, options.size() - 1)]
		visited[chosen] = true
		steps.append(_to_pixel(cell) + chosen - cell)
		steps.append(_to_pixel(chosen))
		stack.append(chosen)


func _to_pixel(cell: Vector2i) -> Vector2i:
	return cell * 2 + Vector2i.ONE


func _add_background() -> void:
	var background: ColorRect = ColorRect.new()
	background.color = Color('#12141a')
	add_child(background)
	background.set_anchors_and_offsets_preset(Control.PRESET_FULL_RECT)