这里有各种迷宫的生成各种类型的迷宫在线免费生成，支持迷宫查找路径
迷宫表示
直观来看，迷宫总是能一眼看到密密麻麻的墙壁，但是如果反转思路来看，可行的迷宫是自起点通往终点的路径，不考虑迷宫的回路和无法到达的死路，那么迷宫的路径实际上可以看作图论里的树
既然路径是一棵树，那么难免就想到最小生成树算法。当然，此处没有权值，也无需考虑最小，随便生成一棵树即可。在本文里使用prim算法。
随机prim算法
与原版的prim算法不同，随机prim算法每次选择新的顶点不需要根据距离，随便取一个顶点就可以了。
首先将所有格子设置一个false的状态，然后可以随机取一个格子作为起点，并修改其状态为true。需要维护一个数组，里面存后面要进行操作的格子，将起点加入这个数组。
当这个数组里还有未处理的格子时，进行如下操作：
随便取出一个格子a，逐个访问它相邻的格子b，如果它相邻的格子b的状态为false，说明当前没有能访问b的路径，将b加入数组，并修改状态为true；如果为true，那么说明之前已经有路径抵达b，那么a和b之间可以添加墙壁。
当数组为空时，迷宫生成完成。
Godot实现
准备工作
设置一个Node2D根节点，添加TileMapLayer和Camera2D节点，根据我的上一篇博客完成相机的设置
要在TileMapLayer里显示迷宫，需要设置TileSet图集，在这里简单手绘了一张，可以放进去使用。
另外，Godot没有C/C++那种二维数组，在这里手写一个初始化函数得到一个类似的二维数组
| |
由于需要随机取点，需要先进行初始化或者是种子设置，可以在_ready()函数里添加randomize()，或是手动设置种子seed(998244353)
迷宫生成
接下来其实就算简单了，如果之前接触过最小生成树的话，可以略过这一部分了。
首先是一些变量的定义，包括地图大小和四个方位以及格子的状态，
| |
用lambda表达式设置了一个函数用于把后续需要操作的格子放进去，避免后面的格子把之前的格子再判断一次，把之前的格子也复制了一遍，其实也可以全局变量维护下状态，当时懒得改了。
| |
接下来就是把起点放入维护的数组，一遍遍进行操作了。
| |
迷宫绘制
迷宫的绘制主要就算把TileMapLayer的格子根据是否有墙设置成TileSet里的块。
在这里遵循下面的对应关系
| 序号 | 墙的存在情况 | TileSet坐标 |
|---|---|---|
| 0 | 无 | (0,0) |
| 1 | 上 | (1,0) |
| 2 | 下 | (2,0) |
| 3 | 上下 | (3,0) |
| 4 | 左 | (0,1) |
| 5 | 左上 | (1,1) |
| 6 | 左下 | (2,1) |
| 7 | 左上下 | (3,1) |
| 8 | 右 | (0,2) |
| 9 | 右上 | (1,2) |
| 10 | 右下 | (2,2) |
| 11 | 右上下 | (3,2) |
| 12 | 右左 | (0,3) |
| 13 | 右左上 | (2,3) |
| 14 | 右左下 | (1,3) |
设置字典来方便后面选择图块，
| |
接下来就是根据ans_walls的墙的情况添加图块了，四个方向赋予四个权值，然后遍历每一个方格的四个方向，该方向有就累加权值，根据最后的权值设置图块即可。
| |
效果展示
有点丑，不过能看清墙就算成功啦
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
extends Node2D
@onready var tilemap = $TileMapLayer
var SIZEH = 15
var SIZEW = 15
var directions = [Vector2i(0, -1), Vector2i(0, 1), Vector2i(-1, 0), Vector2i(1, 0)] # 上下左右
var tile_source = 2
var tiles = {
0: Vector2i(0, 0),
1: Vector2i(1, 0),
2: Vector2i(2, 0),
3: Vector2i(3, 0),
4: Vector2i(0, 1),
5: Vector2i(1, 1),
6: Vector2i(2, 1),
7: Vector2i(3, 1),
8: Vector2i(0, 2),
9: Vector2i(1, 2),
10: Vector2i(2, 2),
11: Vector2i(3, 2),
12: Vector2i(0, 3),
13: Vector2i(2, 3),
14: Vector2i(1, 3),
}
@onready var camera = $Camera2D
@onready var sprite = $Sprite2D
var CamScale = Vector2(1.0, 1.0)
var CamPos = Vector2(0.0, 0.0)
var offset = 20
var scale_delta = 0.05
var offsets: Vector2
var mouse_position
var isDrag = false
var startPos: Vector2
func _ready():
randomize()
var walls = generate_maze(Vector2i(SIZEW, SIZEH), Vector2i(SIZEW / 2, SIZEH / 2))
set_tile(walls)
func create_2d_array(x: int, y: int, default_val):
var _array_ = []
for i in range(x):
_array_.append([])
for j in range(y):
_array_[i].append(default_val)
return _array_
func set_tile(ans_walls): # 根据墙存在的情况来添加tile
var dict = {0: 1, 1: 2, 2: 4, 3: 8}
for i in range(SIZEW):
for j in range(SIZEH):
var neighbours = 0
var current: Vector2i = Vector2i(i, j)
for k in range(4):
var next_grid: Vector2i = directions[k]
var another_grid: Vector2i = current + next_grid
if another_grid.x < 0 or another_grid.y < 0 or another_grid.x >= SIZEW or another_grid.y >= SIZEH:
continue
if ans_walls.has(Vector4i(current.x, current.y, another_grid.x, another_grid.y)):
neighbours += dict[k]
tilemap.set_cell(current, tile_source, tiles[neighbours])
func generate_maze(size: Vector2i, start: Vector2i): # 以start为起点
var map = create_2d_array(size.x, size.y, false)
var grids: Array[Vector4i] = [] # 保存哪两格之间的墙
var ans_walls = {} # 保存最后生成的墙
map[start.x][start.y] = true
#把新标记的格子的墙放进去
var add_wall = func(current: Vector2i, before = null):
for next_grid: Vector2i in directions:
var another_grid: Vector2i = current + next_grid
if another_grid.x < 0 or another_grid.y < 0 or another_grid.x >= SIZEW or another_grid.y >= SIZEH:
continue
if before != null and another_grid == before: # 避免加入之前被破掉的墙
continue
var grid: Vector4i
grid.x = current.x
grid.y = current.y
grid.z = another_grid.x
grid.w = another_grid.y
grids.append(grid)
add_wall.call(start)
while !grids.is_empty():
var length = grids.size() - 1
var index = randi_range(0, length)
var grid: Vector4i = grids.pop_at(index) # 可能很耗费性能
var first_grid = Vector2i(grid.x, grid.y)
var second_grid = Vector2i(grid.z, grid.w)
var gridd = Vector4i(second_grid.x, second_grid.y, first_grid.x, first_grid.y)
if ans_walls.has(gridd):
continue
if map[second_grid.x][second_grid.y] == false:
map[second_grid.x][second_grid.y] = true
add_wall.call(second_grid, first_grid)
else:
#可以有墙
ans_walls[grid] = true
ans_walls[gridd] = true
return ans_walls
func _input(event: InputEvent) -> void:
mouse_position = get_viewport().get_mouse_position()
if event.is_action_pressed("ui_recovery"):
CamPos = Vector2(0.0, 0.0)
CamScale = Vector2(1.0, 1.0)
camera.zoom = CamScale
if event is InputEventMouseButton:
var BeforeScale = CamScale
if event.button_index == MOUSE_BUTTON_WHEEL_UP:
CamScale.x = exp(log(CamScale.x) + scale_delta)
CamScale.y = exp(log(CamScale.y) + scale_delta)
if event.button_index == MOUSE_BUTTON_WHEEL_DOWN:
CamScale.x = exp(log(CamScale.x) - scale_delta)
CamScale.y = exp(log(CamScale.y) - scale_delta)
if event.button_index == MOUSE_BUTTON_MIDDLE:
if event.is_pressed():
startPos = mouse_position
isDrag = true
else:
isDrag = false
var pscale = CamScale / BeforeScale
if pscale != Vector2(1, 1):
var delta_mouse_posion = (pscale * (position + mouse_position) - mouse_position) / CamScale
CamPos += delta_mouse_posion
camera.zoom = CamScale
if isDrag:
CamPos += (mouse_position - startPos) * CamScale
startPos = mouse_position
func _process(delta: float) -> void:
var input_direction = Input.get_vector("ui_left", "ui_right", "ui_up", "ui_down")
offsets = offset * input_direction / CamScale
CamPos += offsets
# 这里去掉了相机锚点限制
camera.position = CamPos