发现现在无论是玩家还是策划，纷纷要求引擎可以实现自动寻路。虽然我对此不以为然，但其实这也不是什么难题，打算随便做一个好了。
我们现在的 engine 是用矢量线段描述场景中的障碍的。这些线段无所谓人工标记还是从场景模型中自动生成出来，又或者是用传统的打格子的方法变换出来。在这些障碍线构成的矢量场景中寻路其实不是什么难事。
我们只需要在场景中标记出若干 waypoint ，这些 waypoint 一般在大片无障碍区域的中央，以及分叉路口。游戏中故意设计迷宫为难玩家绕来绕去又没有什么玩点内容在里面是没有什么意义的。（除非是“不可思议的迷宫”这种以迷宫为重要玩法的游戏）所以，大多数游戏场景，路径的拓扑关系复杂度非常有限。 waypoint 靠人工设置就足够了。
btw, 自动生成 waypoint 也不是难事，反正这个东西不会是性能要点，机器生成 waypoint 不会比人工设置的糟糕太多。算法就不展开谈了。waypoint 的设置要点是：场景中所有可达区域都能看到至少一个 waypoint ，这个要求可以用程序检测。
我们把所有 waypoint 间可以直线连接的线路连起来，得到一张图。可以预存下这张图，以后的工作则非常简单。
每次需要得到场景中任意两点间的路径，就从起始点和目标点各取一个临近可见的 waypoint 。之后求这两个 waypoint 间在图上的最短路径。Dijkstra 算法即可。
得到路径后，角色在场景中行走时，间隙的判断是否可以直接看到路径上的下一个 waypoint ，只要可以看到，就沿直线方向朝路径上最远可见的 waypoint 移动。最终可以得到一条较为自然的运动轨迹。
嗯，没啥高深的算法，随便写写就能实现了吧。
0 Comments.