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

Godot shader 泛光效果

        近日在画画的时候，想让一个光源有泛光效果，发现godot虽然有自带的泛光效果，在worldEnvironment节点上，但这个会作用到全屏幕，连你的ui都会有效果，所以尝试了下自己实现一个shader来产生泛光效果。

一、泛光效果的原理：

简单地说就是：

1. 原图根据灰度过滤掉一部分颜色。
2. 把过滤掉颜色的图片模糊化(blur)
3. 把原图和模糊化之后地图片颜色相加(combine)，得到泛光图。

二、项目构成：

• 一张颜色分明的图，节点树里sprite类型的colors节点，我这张图是32*32大小的，图片背景透明。

• Shader类型的材质Bloom.material（会在下面介绍），绑定在colors上。

        这里先说明一下，下面的内容是基于你对godot的shader有一定了解的情况下进行介绍的。

• Bloom.material:

        我们的效果都只会用到片段着色器（fragment shader)，所以只会用到godot Shader里的fragment()函数：

        然后我们需要一些参数来改变shader的效果，于是在fragment()函数外面定义：

        这几个变量目前来说就只是数值而已，后面用到的时候会再详细讲它们的作用。

        我们需要对每个fragment进行取样，并根据灰度过滤一部分颜色，我这里用了一个自定义函数：

上面这段计算灰度那里，百度一下rgb转灰度基本都能查到这个公式，另外更详细的介绍可以看维基

计算思路：

       首先我们要对图片进行取样，取样的函数是texture(sampler2D tex,vec2 uv)，这个函数返回一个vec4变量，其实就是tex图片在uv上的颜色rgba值，范围在[0.0,1.0]。

        然后我们要向某个方向取样，就这么写：

就在UV那里添加一个2d的偏移量，这个radius就是我们之前定义的取样半径，但现在这个半径是一个绝对半径，我们不知道这个radius数值在屏幕上到底有多宽，因为我们不知道一个像素有多宽，所以还要把偏移量乘上像素大小，让radius变为基于像素的取样半径：

        然后把取样颜色存起来：

偏移8个方向取样，并把颜色叠加起来：

颜色叠加起来会很亮，所以叠加了多少次就除回去多少。

        现在我们知道怎么取样了，但我们现在要的不是单纯的取样结果，而是根据灰度过滤颜色，

于是，每一条取样都变成

用之前定义的limitGrayColor()函数过滤掉低于grayLimit的颜色。这里的grayLimit就是我们之前定义好的最低灰度。

        现在，我们已经完成了8个方向的取样，但是，我们只取了一次，模糊范围就只有radius*TEXTURE_PIXEL_SIZE 这么大，所以我们还要向外进行多次取样。于是代码就变成：

这里的sampleCount就是我们之前定义的取样次数。

        然后我们获得了过滤灰度之后的模糊颜色

        最后把模糊色和原色叠加，获得泛光颜色并输出：

这里的brightness就是我们之前定义的模糊亮度，用来调节模糊色的亮度的，实际上只是使col的rgba线性增减。

最终效果：

[spoilerblock text="【代码】"]

shader_type canvas_item;

uniform float radius:hint_range(0.0,2.0) = 0.5;//取样半径（基于像素）
uniform int sampleCount:hint_range(1, 8) = 4;//取样次数
uniform float grayLimit :hint_range(0.0, 1.0) = 0.3;//取样最低灰度
uniform float brightness :hint_range(0.0, 1.0)= 0.5;//模糊亮度

vec4 limitGrayColor(vec4 color,float limit){

if(limit <=0.0)//没限制，输入什么就输出什么
return color;

//计算灰度
float gray = dot(color.rgb,vec3(0.299, 0.587, 0.114));

if (gray<=limit){//灰度小于限制，就返回透明颜色
return vec4(0.0);

}else //不然就保留该颜色
return color;

}void fragment(){

vec2 ps = TEXTURE_PIXEL_SIZE;//像素大小

vec4 col = vec4(0.0);//最终输出的颜色

for(int i = 1;i<=sampleCount;i++){

//**当前为向8个方向取样，时间复杂度为O(n)，模糊效果不是特别好,尤其是对角
//当然你也可以向外n*n个格子取样，不过时间复杂度是O(n^2),模糊效果较为精确
//网上那些n+n的取样方式是对一张图处理1次后把图提取出来再处理1次，要配合底层代码来写的。
col+=limitGrayColor(
texture(TEXTURE,UV + vec2(0,-radius)*ps*float(i)),grayLimit);
col+=limitGrayColor(
texture(TEXTURE,UV + vec2(0,radius)*ps*float(i)),grayLimit);
col+=limitGrayColor(
texture(TEXTURE,UV + vec2(-radius,0)*ps*float(i)),grayLimit);
col+=limitGrayColor(
texture(TEXTURE,UV + vec2(radius,0)*ps*float(i)),grayLimit);
col+=limitGrayColor(
texture(TEXTURE,UV + vec2(radius,radius)*ps*float(i)),grayLimit);
col+=limitGrayColor(
texture(TEXTURE,UV + vec2(radius,-radius)*ps*float(i)),grayLimit);
col+=limitGrayColor(
texture(TEXTURE,UV + vec2(-radius,radius)*ps*float(i)),grayLimit);
col+=limitGrayColor(
texture(TEXTURE,UV + vec2(-radius,-radius)*ps*float(i)),grayLimit);}

col/=(8.0*float(sampleCount));
COLOR = col*brightness+texture(TEXTURE,UV);

}


[/spoilerblock]

Godot简易状态机

Godot做角色移动的时候，为了不让代码在一个脚本里扎堆强奸我们的眼睛和大脑，就需要做一些小优化，比如，用状态机。

本文将介绍如何在godot里控制角色移动动画根据移动方向而切换，并进行移动。

• 项目构成：

1. 以kinematicBody2d为根节点的玩家节点

        2.角色运动图集(玩家节点中的Sprite）

        3. 控制角色运动动画的animationPlayer(玩家节点中的AnimationPlayer)

   我根据图集创建了3个动画，分别是“待机（idle）”、“向左跑（runLeft)”和“向右跑（runright)”

        4. 绑定在角色节点kinematicBody2d上的脚本dog_mov.gd（详情在下面）

        5. 简易的状态机脚本Bh_dog_test.gd（详情在下面）

• 脚本介绍

        1.dog_mov.gd:

   这个脚本并不控制动画切换，只是提供了动画切换的函数，方便调用：

其中aniPlayer是玩家节点中的AnimationPlayer

在脚本里我定义了角色移动方向和速度

定义了移动函数：

并在_physics_process(delta):里控制移动：

这个函数里的bhv就是状态机实例，下面会继续介绍，而上面这个脚本就介绍结束了，并没有什么太复杂的内容。

        2. Bh_dog_test.gd

首先是定义变量和设置构造函数_init()

如果对funcref(obj,funcName)不熟悉的可以看这里：

[GodotAPI][FuncRef]

[GodotAPI][@GDScript.funcref]

当然你也可以用 signal 来做，目的是只调用一个函数，而函数内容根据条件变化。

obj就是dog_mov.gd实例，现在在dog_move.gd中就可以新建一个Bh_dog_test.dg实例了：

回到Bh_dog_test.gd，编码状态机：

状态机的状态转换示意图：

待机状态（idle）：

奔跑状态（running）

再细分左右奔跑（runleft,runright)

以上就是角色动画切换的状态机，其实角色移动控制也可以写在这里面的，看个人喜好吧。

至于为什么只截图，不发代码，由于过于简单，大家还是自己动手打打吧（手动笑哭）。

最终效果

近日在做navigation2d加navigationPolygonInstance做寻路的时候遇到了一些坑，先记录下来。

使用的示例是官方自带的navigation2d示例，脚本没有进行修改，只改了相关的navigationPolygonInstance

1.如果在navigation2d的子孙节点里有多个NavigationPolygonInstance，且这些NavigationPolygonInstance不粘连，而当get_simple_path( Vector2 start, Vector2 end, bool optimize=true )传入的start和end跨越两个不粘连的NavigationPolygonInstance时，该函数不起作用，不过有时候也能以小概率在NavigationPolygonInstance的边缘卡进另外一个NavigationPolygonInstance。

如图：在navpoly和navpoly2不粘连的时候，即使是重叠，也不能使agent跑到navpoly2的区域上去

2.即使多个NavigationPolygonInstance紧贴在一起，如果紧贴的地方没有重合的顶点，则get_simple_path()函数返回绕过没重合顶点的路径数组，假如两个NavigationPolygonInstance完全没有重合顶点，则造成了问题一

下图为2个navpoly的形状，可以看到只有一对重合顶点。

最终运动效果：

结论：

1.要想navigation2d对所有子节点的navigationPolygonInstance起作用，就要让它们有重合的点。

2.最好用“依附”功能来做重合，因为navigationPolygonInstance里的每个顶点都是一个vector2，向量你懂的，xy都可以是小数，不知道算重合的精度是多少。

.............................

另外一个坑其实算小进阶，就是在已有的navigationPolygonInstance里挖个不能走的坑，比如你要在地图上放一个花盆，AI要绕过去，又不想手动改navigationPolygonInstance，就代码改改。

这个问题我在下面这个网址上看到的

https://www.reddit.com/r/godot/comments/7k4qos/why_does_this_script_created_hole_in_the/

然后试了下里面的代码，其实还有点旧了，可能那时候还没to_local和to_global函数，就还是用transform的逆矩阵乘另一个transform来获取本地transform，但这种方法也有局限性，说起来还挺麻烦，不说了，知道有局限就好（想了解矩阵的相关知识的可以点一下

https://www.bilibili.com/video/av6731067

这个b站的链接）。

再然后根据里面的代码改了下项目唯一的脚本navigation.gd:

1.添加变量Cutout,类型是polygon2d，在场景中添加一个polygon2d节点，弄个形状，使Cutout变量指向这个节点。

2.添加函数：

#调节polygon2d的位置

func adjustPolygonPosition(inTransform, inPolygon):

    var outPolygon = PoolVector2Array()

    #把顶点转换到本地坐标，要求navpoly和cutout要有相同的父节点，或各自父节点的transform相同

    #var finalTransform = $navpoly.transform.inverse() * inTransform

    for vertex in inPolygon:

        #outPolygon.append(finalTransform.xform(vertex))

        #下面这个方法就没有父节点限制

        var finalPos = $navpoly.to_local(Cutout.to_global(vertex))

        outPolygon.append(finalPos)

return outPolygon

#重新修改节点

func modifyNavPoly():

    #其实outline就是顶点数组，输出一下就知道了

    $navpoly.navpoly.add_outline(adjustPolygonPosition(Cutout.transform, Cutout.polygon))

    $navpoly.navpoly.make_polygons_from_outlines()

    #下面这些是必须的，用于更新navpoly

    $navpoly.enabled = false

    $navpoly.enabled = true

3.在_ready()里添加一行代码：

modifyNavPoly()

就ok了，要注意的是，cutout不能挖到navpoly外面，不然就没效果。

下图是我的节点结构:

把cutout放在Node2D下面是为了测试我自己改了的代码和原本的代码有没有区别，可以移动一下Node2D节点对比下新旧代码效果。

navpoly就是被挖的NavigationPolygonInstance，而navpoly2是我测试看两个粘合的NavigationPolygonInstance能不能一起挖，发现是不能的。

至于再怎么填回去。。。

Emmm

我自己也没做，但可以猜测下。

首先NavigationPolygonInstance的get_outline(0)返回的是本身的顶点数组，然后每调用一次add_outline()就会使outline数加一，也就是这时候用get_outline(1)会获得新加上去的顶点数组，然后你就可以用remove_outline()函数来试试咯。

另外，如果各位小伙伴在测试上面这些内容的时候发现有问题请留言！我看到会马上改的！万分感激！