tile based随机地图--检测地图连通性
廿木
2020-01-06
最近在做一个游戏,用到随机地图算法,参考了这篇文章[随机生成 Tile Based 地图之——洞穴],深受启发的同时,又想彻底解决概率极小的生成了不可连通地图的情况,所以就写了个地图连通性检测的函数,这里跟大家分享一下思路。
大概思路:
假设有一个地图,白色方块表示路,黑色表示墙:
地图连通意味着,任意两个方块可以互相抵达,那不连通就意味着,如果我从任意一条路开始走,走完我能走的所有路,地图上仍然有路,那就是不连通的。所以我只要走完我能走的路,再看看地图上还有没有路就可以了,如下图(红色是起始点,绿色表示我能走的我都走过了):
如果从右下角的方块开始走也是同理:
以上就是大概思路,简单粗暴。
编程思路:
可用广度优先或深度优先算法来暴力走图。我这里用的是广度优先。
1. 建一个跟地图大小一样的数组,用于表示哪些方块走过了:(黑色表示没走过,白色表示走过,初始值为都没走过)
2. 建一个队列用来表示哪个方块是可以走的,并以队列第一个方块为起点检测四周的方块是否连通,如果连通并且在第1步中的数组中表示该方块没有走过,就把联通的方块再放到队列里:
3. 每走过一个方块,或者每检测到一个连通的方块就更新第1步的数组:
4. 把队列第一个方块丢掉,重新返回第2步,直到队列里的所有方块都清空。
5. 最后,把原地图与第1步建的数组做匹配,如果相等,则连通,否则不连通:
[godot]效果展示:
有请劳模godot图标()上场,左边的是算法生成的地图,godot图标表示墙,空地方表示路,右边是上面第1步的数组:
连通图:左右相等
不连通图:左右不相等
[spoilerblock text="godot代码"]
#广度优先算法,检查连通性 func checkConnectivity(map) ->bool: var queue:=[]#队列 var myMap:=[]#与地图等大小的数组 var wall:=false #墙 var road:=true #路 for i in range(map.size()): var mRow :=[] for j in range(map[i].size()): mRow.append(wall) myMap.append(mRow) for i in range(map.size()): var isIt:=false for j in range(map[i].size()): if map[i][j] == road and queue.empty():#找到第一块路 queue.append(Vector2(i,j)) isIt = true myMap[i][j] = map[i][j] break if isIt: break while ! queue.empty() : var curPos = queue.pop_front() #放入myMap表示这个位置检查过了 #如果某个方向上也是非空的位置,并且没有检查过,就放入队列 var upX = max(curPos.x -1,0) var downX = min(curPos.x+1,map.size()-1) var leftY = max(curPos.y-1,0) var rightY = min(curPos.y+1,map[curPos.x].size()-1) if map[upX][curPos.y] and !myMap[upX][curPos.y]:#上 queue.append(Vector2(upX,curPos.y)) myMap[upX][curPos.y] = road if map[downX][curPos.y] and !myMap[downX][curPos.y]:#下 queue.append(Vector2(downX,curPos.y)) myMap[downX][curPos.y] = road if map[curPos.x][leftY] and !myMap[curPos.x][leftY]:#左 queue.append(Vector2(curPos.x,leftY)) myMap[curPos.x][leftY] = road if map[curPos.x][rightY] and !myMap[curPos.x][rightY]:#右 queue.append(Vector2(curPos.x,rightY)) myMap[curPos.x][rightY] = road #上面这一段while在检查完一片完整的区域后就会结束,所以如果还有第二片完整的区域,map!=myMap,就是不连通地图 for i in range(map.size()): for j in range(map[i].size()): if map[i][j] != myMap[i][j]: return false return true
#按上面这段代码的缩进复制到godot里面是会出错的,所以不能直接用的哦
[/spoilerblock]
(转发自:原日志地址)