Godot随机prim算法生成方格迷宫
参考 学校永远不会告诉你的迷宫秘密 这里有各种迷宫的生成各种类型的迷宫在线免费生成，支持迷宫查找路径 迷宫表示 直观来看，迷宫总是能一眼看到密密麻麻的墙壁，但是如果反转思路来看，可行的迷宫是自起点通往终点的路径，不考虑迷宫的回路和无法到达的死路，那么迷宫的路径实际上可以看作图论里的树 既然路径是一棵树，那么难免就想到最小生成树算法。当然，此处没有权值，也无需考虑最小，随便生成一棵树即可。在本文里使用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++那种二维数组，在这里手写一个初始化函数得到一个类似的二维数组 1 2 3 4 5 6 7 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_ 由于需要随机取点，需要先进行初始化或者是种子设置，可以在_ready()函数里添加randomize()，或是手动设置种子seed(998244353) 迷宫生成 接下来其实就算简单了，如果之前接触过最小生成树的话，可以略过这一部分了。 首先是一些变量的定义，包括地图大小和四个方位以及格子的状态， 1 2 3 4 5 6 7 8 var SIZEH = 15 var SIZEW = 15 var directions = [Vector2i(0, -1), Vector2i(0, 1), Vector2i(-1, 0), Vector2i(1, 0)] # 上下左右 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 = {} # 保存最后生成的墙 用lambda表达式设置了一个函数用于把后续需要操作的格子放进去，避免后面的格子把之前的格子再判断一次，把之前的格子也复制了一遍，其实也可以全局变量维护下状态，当时懒得改了。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 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) 接下来就是把起点放入维护的数组，一遍遍进行操作了。 ...