一个简单的寻路算法
周末跟同事聊天，问了一下最近公司新项目的一些需求。发现现在无论是玩家还是策划，纷纷要求引擎可以实现自动寻路。虽然我对此不以为然，但其实这也不是什么难题，打算随便做一个好了。
我们现在的 engine 是用矢量线段描述场景中的障碍的。这些线段无所谓人工标记还是从场景模型中自动生成出来，又或者是用传统的打格子的方法变换出来。在这些障碍线构成的矢量场景中寻路其实不是什么难事。
我们只需要在场景中标记出若干 waypoint ，这些 waypoint 一般在大片无障碍区域的中央，以及分叉路口。游戏中故意设计迷宫为难玩家绕来绕去又没有什么玩点内容在里面是没有什么意义的。（除非是“不可思议的迷宫”这种以迷宫为重要玩法的游戏）所以，大多数游戏场景，路径的拓扑关系复杂度非常有限。 waypoint 靠人工设置就足够了。
btw, 自动生成 waypoint 也不是难事，反正这个东西不会是性能要点，机器生成 waypoint 不会比人工设置的糟糕太多。算法就不展开谈了。waypoint 的设置要点是：场景中所有可达区域都能看到至少一个 waypoint ，这个要求可以用程序检测。
我们把所有 waypoint 间可以直线连接的线路连起来，得到一张图。可以预存下这张图，以后的工作则非常简单。
每次需要得到场景中任意两点间的路径，就从起始点和目标点各取一个临近可见的 waypoint 。之后求这两个 waypoint 间在图上的最短路径。Dijkstra 算法即可。
得到路径后，角色在场景中行走时，间隙的判断是否可以直接看到路径上的下一个 waypoint ，只要可以看到，就沿直线方向朝路径上最远可见的 waypoint 移动。最终可以得到一条较为自然的运动轨迹。
嗯，没啥高深的算法，随便写写就能实现了吧。
最近在公司附近的一个小区会所办了张健身年卡。几年没动了，体力和力量都下降了不少。关键是平时精神不太好，感觉没前几年有活力。是应该每天流点汗，吃好睡好，这样脑子更好使。
已经坚持去了三次了，重量大了会有点头晕，得控制一下。刚开始恢复，浑身肌肉酸痛。昨天做了几组深蹲，今天走路都有点痛。不过这几天居然有了不小的食欲。白切牛肉可以吃一大盘，冰箱里的鸡蛋一扫而光。是个好兆头。
Comments
" 自动生成 waypoint 也不是难事",能说下这个用是什么算法吗？然后能不能解决室内自动布点
Posted by: 886 | (17) August 19, 2020 07:19 PM
把大地图根据障碍变成小一号的地图然后根据这些格子使用寻路算法是挺不错的，但是Dijkstra 算法好像不如a*算法性能高
Posted by: daliniu | (16) October 17, 2016 05:42 PM
7楼和13楼说的大概是一样的东西吧。WayArea。
WayArea可以细化分成更小块，分阶段细化路径运算，并且不易遗漏，易维护更新。
或许云风这次百密一疏了。:)
Posted by: Tone | (15) March 24, 2010 01:02 AM
自动寻路给了玩家更多的空间和便利,只是梦幻现在还不支持鼠标滚轮操作,是不是涉及到游戏底层支持硬件引擎的部分?目前梦幻NPC下拉选项够多,只有通过单点或是将选项横排实现,不知道这个是否方便解决呢?
Posted by: MicroOnion![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (14)
August 7, 2008 11:21 AM
《天龙八部》中的阻挡区数据也是用矢量多边形编辑的，寻路算法也和云风说的类似，中间有个数据处理过程，使用了CGAL数学库把可行走区域拆分成三角形，但整个过程并不像云风说的那么简单，还是费了一番功夫得。
Posted by: Jean | (13) July 27, 2008 04:25 PM
我感觉云风想的太简单了，先说云风提到的手动标记waypoint算法，据说所知tencent的一款3d游戏就是美术手动标记，但这个工作量非常大，而且容易遗漏，一旦遗漏或者因为场景修改没有相应变动waypoint就会失效，而在一个复杂的3D环境中，waypoint也是非常复杂的，比如桥的结构，美术场景的修改需要同步waypoint，这样工作量极其巨大和痛苦，不能认为人工可以标记就认为这是人工可以解决的。另外这里waypoint不可能仅仅是点-点连接的直线，很有可能寻路的目的地是waypoint路径外的点，这应该是一个凸多边形的wayarea。
其次，即便都标记正确了，还涉及一个问题，就是很有可能waypoint信息已经膨胀到现有内存无法加载（比如我们的天下贰），就需要考虑分层寻路，先使用低精度的大概搜索，再使用高精度的仔细搜索。同时这又涉及线程加载路径数据等问题。
自动寻路的算法是简单的（仅体现在有向图的搜索而已），但实际做到游戏里，对于大型3D游戏，还有许多需要考虑的问题。
Posted by: Siney | (12) July 25, 2008 04:00 PM
行动真快， tx2今天的版本就有自动寻路了
Posted by: lbaby | (11) July 23, 2008 09:33 AM
服务器上有N多的怪一起寻路可不是即时算能解决的。
不同的场合使用不同的方案。
Posted by: Leon![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (10)
July 22, 2008 10:04 PM
A*算法不是很久以前就解决了这个问题么。
Posted by: hillin | (9) July 22, 2008 12:42 AM
有兴趣的朋友可以到这寻一下自己的路,http://search.51job.com/jobsearch/show_job_detail.php?id=(38044224)
云风的deepcold团队已经满员了,或者我们的团体会适合你!
Posted by: tigerdx8 | (8) July 21, 2008 01:48 PM
嗯。吃得多可以，就怕吃得多不运动
Posted by: nothanks | (7) July 21, 2008 12:02 PM
最近也在研究这个问题，实际上似乎与区域分割同属一个问题。考虑二维BSP树做的工作，就是把所有的空间分割成为了Convex空间，且一定具有连通性。从一个Convex到另一个Convex一定存在一条路径。将所有这些连通性可能存在的路径保存起来（这似乎就是PVS干的事情）可以得到一个巨大的表，想要知道从某指定Convex到某指定Convex只要查这张表即可，O(1)时间的算法。Convex空间内的寻路，只要直线即可，因为凸空间内没有障碍。
Posted by: Leon![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (6)
July 21, 2008 11:46 AM
呵呵，今年的icfp比赛正好考的寻路：http://icfpcontest.org/
Posted by: roy_hu | (5) July 21, 2008 09:49 AM
恢复健身，是件好事
Posted by: skillzero | (4) July 21, 2008 09:37 AM
夏练三伏，冬练三九；前不久不是说有一个大牛数学上证明了什么地图路径问题，好象是无目标的那一种，没有特别关注记不清楚了；要是那样路由器上到可以用用；
Posted by: Anonymous | (3) July 20, 2008 08:59 PM
这个功能让梦幻的玩家可以四开跑镖了。高手甚至可以多开跑商
Posted by: Anonymous | (2) July 20, 2008 08:51 PM
自动寻路让游戏变得不真实。
Posted by: gameroger![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (1)
July 20, 2008 08:20 PM