关于网络游戏寻径的思考

免费打工仔

自己写了A*的寻径，自作聪明的用set容器自己实现一个优先队列，结果大部分时间都花飞到插入和移出上面了，结果效率慢得要命，上网上找到云风写的例子，改了之后，觉得比自己的快上至少100倍。

不过觉得A*还是不够快，如果同时很多寻径的话会卡住，毕竟客户端1/60秒渲染。

1000*1000的地图 如果摄像机固定 就只能看到20*20左右吧，如果只做能看到的范围，就能从1000000个节点减少到400个，我想这个是大家理所当然的优化吧。
但是如果摄像机不固定而且地形很复杂的，比如天堂II，用地面的3角形来作节点么？这样用A*是不是会慢呢，是否是划分成区域呢？还是用其他的寻径方法，比如导航点？

在服务器端不是纯正的A*寻径吧，因为服务器只要验证客户端的行走要求是否合理然后批准就好了，那服务器端用什么样的算法去判断合理呢？

有业内的朋友透露一下吧，到底是怎么做的。我都是瞎猜 [em10]

wingser

用树，做大a*和小a*
npc 分frame做path finding，不要大家一起做

我乱说的：）

sea_bug

服务器一般都会有自己的算法，A*只是作为一种思考的方向，主要还是在于如何解决问题，比如网络游戏我们可以这样考虑，由客户端来进行A*运算，然后直接回传结果服务器，服务器再对结果进行简单验证，这样也可以缓解服务器寻径的压力。

kingmark

估计A*算法是放在服务器处理10之8-9会超级Lag。
如果放在客户端处理。20个人寻路估计好不到哪里去。当然可以减少搜索长度。
尝试在服务器或者客户端用《盟军》的路径算法是否可以呢？

从图中的+364标记的多边形中的某点 走到 +387标记的多边形中的某点
红线和绿线的走法都存在，感觉上也差不多合理，速度就快多了。这样的算法放在服务器和客户端都随便。

不过这个算法需要地图制作者花费更多的心血。
数据结构初始化内存可能要大些，空间换时间我觉得值。

这个是《盟军》一代产品，N年了，一直没有删除。虽然是2D表现效果，但是依然有太多值得学习的地方了。

喜欢参与讨论这样的问题，嘿嘿嘿。抛转引玉，希望高手指点。

免费打工仔

从364，363，362，367，366，走到387
怎么得到这些走动节点的顺序呢，首先想到的还是A*，在我脑海里面显示的是用不规则节点表示地图，然后用A*来寻径。如果不用A*怎么得到顺序呢？
当节点面积过大时候，还会有问题，从364到363，会选择走连接两边中点，这样很不自然，因为靠着下端走更近，这方面还要处理。

kingmark

免费打工仔: Re:关于网络游戏寻径的思考

从364，363，362，367，366，走到387
怎么得到这些走动节点的顺序呢，首先想到的还是A*，在我脑海里面显示...

你也不睡觉啊，嘿嘿嘿。
我没有说走中间的点啊。我也没有说不用A*，取巧的改改阿。结合凸多边形寻路算法[忘记学名了]。
下载《盟军》看看先，我没有视屏捕捉阿。

免费打工仔

sea_bug: Re:关于网络游戏寻径的思考

服务器一般都会有自己的算法，A*只是作为一种思考的方向，主要还是在于如何解决问题，比如网络游戏我们可以...

站长的想法我也想过，似乎要增加网络传输的负担，为了减少这种负担，最好只转送路径转点的信息（走折线），这样的话还要保证路径尽可能少转弯，多直线（编程精粹1中看到这样的文章）。