tile based随机地图--检测地图连通性

最近在做一个游戏，用到随机地图算法，参考了这篇文章[随机生成 Tile Based 地图之——洞穴 ]，深受启发的同时，又想彻底解决概率极小的生成了不可连通地图的情况，所以就写了个地图连通性检测的函数，这里跟大家分享一下思路。

大概思路：

假设有一个地图，白色方块表示路，黑色表示墙： Image title

地图连通意味着，任意两个方块可以互相抵达，那不连通就意味着，如果我从任意一条路开始走，走完我能走的所有路，地图上仍然有路，那就是不连通的。所以我只要走完我能走的路，再看看地图上还有没有路就可以了，如下图（红色是起始点，绿色表示我能走的我都走过了）：

Image title

如果从右下角的方块开始走也是同理：

Image title

以上就是大概思路，简单粗暴。

编程思路：

可用广度优先或深度优先算法来暴力走图。我这里用的是广度优先。

1. 建一个跟地图大小一样的数组，用于表示哪些方块走过了：（黑色表示没走过，白色表示走过，初始值为都没走过）

Image title

2. 建一个队列用来表示哪个方块是可以走的，并以队列第一个方块为起点检测四周的方块是否连通，如果连通并且在第1步中的数组中表示该方块没有走过，就把联通的方块再放到队列里：

Image title

3. 每走过一个方块，或者每检测到一个连通的方块就更新第1步的数组：

Image title

4. 把队列第一个方块丢掉，重新返回第2步，直到队列里的所有方块都清空。 Image title

5. 最后，把原地图与第1步建的数组做匹配，如果相等，则连通，否则不连通：

Image title

[godot]效果展示：

有请劳模godot图标（ Image title ）上场，左边的是算法生成的地图，godot图标表示墙，空地方表示路，右边是上面第1步的数组：

连通图：左右相等

Image title

不连通图：左右不相等

Image title

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里面是会出错的，所以不能直接用的哦