有对游戏中寻路感兴趣吗?

happyking

一个精灵在方格中移动,从A点到B点,用前后左右来控制.
方格当中有障碍物,精灵要绕开,然后到达终点.

1.想到A*算法,一个精灵周围有前后左右四个点,四个点周围也有四个点.
用逆归的办法,到达终点,再返回.但是游戏是不停的循环,如果有很多精灵寻路会不会有停顿.

2.然后又想到一种简单的方法,遇到障碍物,就着障碍物边沿运动.

轩辕崇正

第1个问题：
既然是鼠标/键盘控制寻路，那寻路范围必定很短，这种方式的寻路开销会相当小
而如果精灵自动寻路，可能就得需要一个线程了。
这个线程负责计算每个人的路径到队列中，每创建完一个角色的路径，便设个标识位，主线程中每个角色判断他自己的标识位是否已经被激活，然后决定是否开始按照路径寻路。

第2个问题：
既然选择了A*算法，就不用关心障碍物了。A*是很快的

Enigmaya

a*不用递归来实现，效率很高的。如果一帧寻路的对象太多，确实影响到了效率，可以简单限制下每帧总的寻路计算次数，几帧的延迟，看不出来的。
如果想要动态躲避，如想让几个精灵之间能互相绕开,那就要看更多东西了。如VO,RVO等等。

轩辕崇正

Enigmaya: Re:有对游戏中寻路感兴趣吗?

a*不用递归来实现，效率很高的。如果一帧寻路的对象太多，确实影响到了效率，可以简单限制下每帧总的寻路计...

既然使用了A*,就不用关心障碍物了
每一帧精灵的位置都是绝对固定的,精灵再怎么活蹦乱跳,对于A*仍然是一个障碍物.A*会顺利的饶开.
不过要想逼真一些,人物的障碍点可能设多一点。否则一个tile恐怕不够准确。

GordenFreemen

Enigmaya: Re:有对游戏中寻路感兴趣吗?

a*不用递归来实现，效率很高的。如果一帧寻路的对象太多，确实影响到了效率，可以简单限制下每帧总的寻路计...

请问VO和RVO是什么技术？