请问割草游戏的几百个怪物寻路不重叠的算法是什么？

Creator 2.x
#1

割草游戏几百个怪同屏寻路,而且不重叠。。是怎么做到的？

2赞
#2

流畅的做不出来，卡顿的还做不出来么
做一个卡顿的出来再去优化，比空想来的快多了

1赞
#3

不寻路，碰撞后弹开

#4

我做的是没有用物理，怪物不重叠是直接算距离，强制不让重叠。然后再用四叉树优化了一下。这么多怪物用寻路会卡死去

#5

A*和碰撞都试过了。。群怪一起走路会很不自然。。。多了有算不过来。。现在打算使用rvo2试试

#6

同一条路的只算正中一条路径，其余设置位置偏移。设计怪物类时加上位置偏移，速度参数和基准路径

#7

这个之前我想过,怪物进入队伍和离开队伍,会比较麻烦吧。。还有多条路的怪物分组之间的碰撞。。

#8

不寻路，动态避障，单线程最少可以达到2000单位以上

#9

我个人认为割草游戏的同屏寻路 应该更多的是路点
且 寻路应该只需要做一次就可以了 即新的出口位置 开始 到出口结束
另外 割草类游戏 不能完全使用 寻路 而是需要碰撞效果 即寻路只是影响移动方向 并不强制更改位置

而小兵的移动应该更多的是 使用重力向前移动 即更改world重力方向为 z=9.81f * 系数

#10

另外 在检测路径点时候 应该做好算法优化


var newPos = currentPos + dir * speed * Time.deltaTime

var currentPathPos =  paths[ currentIndex ]

var currentDistance = Vectory3.Distance( currentPos, currentPathPos )
var nextDistance = Vectory3.Distance( newPos, currentPathPos  )

if (  currentDistance  < 1e - 2 || nextDistance > currentDistance  ) {
    
       currentIndex+1;
}

 transfrom.position = newPosition;
#11

代码只供参考 你需要根据情况来使用
比如你是cc3.0+ 然后你需要割草类的移动
这里的 transform.position = newPosition 就是不行的 这里你需要改成移动增量处理 应该作用到 rigidbody上赋值一个线性liner的作用力去改变小兵移动方向 而非设置position
但是任然可以用position来检测

#12

这不是普通的碰撞，寻路能解决的

推荐一本书

游戏开发中的人工智能

DM_20220827122316_001
其他的主题包括：

·使用基于势函数的单一技术处理追赶、躲避、聚集和避障等问题。

·使用包括路径点和经典A*算法解决寻径问题。

·利用AI脚本扩充AI引擎的功能，让设计者和玩家更好地设计和玩游戏。

·给你的游戏角色赋予基于规则的AI推理能力，包括模糊逻辑和有限状态机。

·使用概率分析和诸如贝叶斯推理的高级技术处理不确定性问题。

1赞
#13

rvo …

#14

我怎么感觉就朝着目标移动就好，生成的时候外围一圈生成怪，所以就算直接瞄准移动也不会有重叠

#15

碰撞用圆与圆的碰撞来算，多少个都只是数学运算，快得飞起
寻路…其实我觉得割草不用寻路了，目标接近就朝着目标走，走不过去就随机换方向走一段再尝试，反正下一刀就死一片了

#16

割草不用寻路吧，是朝着你移动，计算个角度
重叠就是碰撞检测，算x和y轴距离是否小于一定距离就行了
然后分帧计算，例如一帧只算1/2或者1/4怪物，计算量立马就小了。

#17

rvo2,可以去了解下.

#18

嗯。。已经搞定了

#19

可以考虑用bug算法寻路

#20

我也是这么写的 剩下的是由刚体碰撞去防止重叠的，不过有个要注意的地方就是优化怪物生成的逻辑。如果怪物生成在已经存在的并且扎堆的怪物堆里头，会出现短暂的卡顿。