tile based随机地图--检测地图连通性
最近在做一个游戏,用到随机地图算法,参考了这篇文章[随机生成 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 shader 泛光效果
近日在画画的时候,想让一个光源有泛光效果,发现godot虽然有自带的泛光效果,在worldEnvironment节点上,但这个会作用到全屏幕,连你的ui都会有效果,所以尝试了下自己实现一个shader来产生泛光效果。
一、泛光效果的原理:
简单地说就是:
- 原图根据灰度过滤掉一部分颜色。
- 把过滤掉颜色的图片模糊化(blur)
- 把原图和模糊化之后地图片颜色相加(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做角色移动的时候,为了不让代码在一个脚本里扎堆强奸我们的眼睛和大脑,就需要做一些小优化,比如,用状态机。
本文将介绍如何在godot里控制角色移动动画根据移动方向而切换,并进行移动。
项目构成:
- 以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)
以上就是角色动画切换的状态机,其实角色移动控制也可以写在这里面的,看个人喜好吧。
至于为什么只截图,不发代码,由于过于简单,大家还是自己动手打打吧(手动笑哭)。
最终效果
[godot]navigation2d的一些坑
近日在做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()函数来试试咯。
另外,如果各位小伙伴在测试上面这些内容的时候发现有问题请留言!我看到会马上改的!万分感激!