游戏中碰到个有点棘手的算法问题

月下临风

其实我想到一个解决方案了,只是用文字比较难表术:
我用的是计算几何+A*解决这个问题.计算几何里的射线扫描+线段树.
很多人写过A*,我也见过比A*更快速的搜索算法,不过在解决寻路问题上,都没什么创新,我也看过以前的程序写的A*算法,在游戏里,感觉很土,我这里说一种我对这个问题的解决方法,是有点麻烦,不过我一时想不出更好的了.

物体移动,只有两种状态,直线运动,或绕弯.如果起始点能够直线到目标点,那肯定是最短的,这个小学生都知道.
OK,这是非常重要的附加条件(1),我没有载入地图,我只有通过前期的预处理,得到障碍物的信息,每个障碍物,我都将它钩边,最后我得到的是n个多边形,对我来说多边形是没意义的,我只要他的边就够了,于是我保存了所有边的数据,附加条件(2).

接下来是算法的核心,我估计很多人想不到,即使想到也很难做出来,我怎么说没别的意思,从我个人经历看来,确实不大容易.
我将所有这些边用一个2维的线段树表示,如果你不理解线段树,那么将无法看下去了.搜索google:segment tree.
这样有什么好处呢?
我得到一个起点到终点的直线,判断有没障碍物的边和我的直线有交点,时间复杂度为O(2*LogN)N=2048,最多计算22次,每个线段求交做2个cross,就是向量的差基.所以一次判断直线是否直达目标点可以算是常数时间.

接下来,怎么做射线扫描和A*呢?
扫描说起来有点麻烦,不直观,明天去公司再画个图讲解一下.
目的就是找与障碍物的切点.
原理和凸包算法有点像.
就是以起点为根,到目标点,这跟线段,以起点S,为圆心,半径R = |V(S,D)|,S,为起始点,D就是目标点,为半径扫过去,扫一周,找出所有切点,最后的最短路径必然包含这些切线断,是不是,不知道我说的可以理解么?好接下来用A*的思路做下去就可以了.

扫描线的时间复杂度是O(nlogn),n = 线段的个数.因为对线段需要排序,所以最快也只能是这个复杂度了.

最后的时间复杂度是O(n^2+nlogn)

也就是说,和地图的大小一点关系都没有了,只是和障碍物的包围线段数量有关系.

filx

我觉得服务器定个搜索范围比较好,以人物为中心,一屏内做A*的搜索区域。
如果你想移动比较智能，可以扩大到2屏或者3屏,其实有些时候没必要,一屏内不能走就不走了。

月下临风

主要是用于NPC的寻路,所以是在服务器端计算的.

filx

NPC寻路的话，如果是剧情事件一般是定路点移动,怪兽移动的话超过一定距离就取消追踪了.

sanikoyes

  魔兽服务器的NPC移动范围是由策划定义的，比如不动、范围巡逻等，范围巡逻时可以定义N个坐标，然后NPC在这N个坐标间循环走动，服务器只管移动NPC，而不管这些坐标间是否有地形障碍了，也就是不做A*寻路了。
  所以策划在填写坐标点是要先确定坐标点之间是否有障碍物。

6377

〈传奇〉类僵尸代码害死人，整体架构效率奇低！混乱的想法月越想越糊涂。哈哈，看来找个好老师，真是要少走n年的弯路哦。。。

Aming

客端只要判?嗤婕易陨淼?^
只要用 zone map 系?就可以解?Q了
只要?入自身zone跟附近八??zone共9??

?然前提是你的地?D系?是zone??挝凰?O?的

像Lineage1 就是?袢 64*64 zone的?o接?做法

euclid

不错,那么a*的启发函数就是选择最靠近目标的切点了

conquerors

我曾经在一篇论文中读过类似楼主后来提出的解决方案，算法的核心思想就是利用运动物体的外接圆去扩展障碍物的面积，然后记录所有扩展后的障碍物顶点信息，接着利用a*算法搜得最短路径，当然可能还需要进行一些其他的几何计算。

    使用这个方法不需要载入整个地图，只需要障碍物的信息即可,而且计算量应该也不大,即可以在客户端也可以在服务器端实现。

如果,楼主有兴趣可以一起探讨探讨.

月下临风

谢谢楼上的一个提醒．
我做的时候其实也不容易，有两点不好办的．
一个是线段树不好实现，编程复杂度高了，而且别人也看不懂，不利于以后别人维护．
我想出了一个简单的替代方法．
确实就是做所有障碍物的外接圆，每个障碍物的外接圆，很容易求，只用找到障碍物某对顶点，这对顶点的距离最长就可以了，这样只用通过圆心到直线的距离就可以判断出这直线会不会和这个障碍物相交了．
这样实现起来很容易，以后别人看我的代码也很好理解，而且效率可以接受．

二，在扫描和寻找切点上，我感觉我那样的方法不是最快的，还有更快的方法．
我设置导航点，这个点其实就是多边形障碍物的顶点，从这些顶点到其他和自身多边形的切线，我可以事先都做好．这样我最后得到的是很多个顶点和边，构成我我所需要的图，效率也将非常快了，如果再用A*的话，效率将是非常可观的．