Godot-StartUP

创建于:2018-07-28

创建人: Justus

44 信息 140 成员
讨论基于Godot以及Unity引擎的游戏开发经验,理论和最佳实践。共享一些通用思路以启发另一种生产工具中的实践。独立开发群QQ: 122017359

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

廿木 2020-01-06

        最近在做一个游戏,用到随机地图算法,参考了这篇文章[随机生成 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


[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]




(转发自:原日志地址

近期喜欢的会员

 

加入 indienova

  • 建立个人/工作室档案
  • 建立开发中的游戏档案
  • 关注个人/工作室动态
  • 寻找合作伙伴共同开发
  • 寻求线上发行
  • 更多服务……
登录/注册