分享AI寻径设计的射线追踪法

　　寻径的方法主要有两种，一是动态的，二是静态的。二者的区别在于，路径是即时生成的还是预设的。无论是哪种情况，路径都可以由客户端或服务器生成。一般来说，动态路径是在客户端生成的，然后根据自服务器的更新而变化。然而，静态路径既可以由客户端也可以由服务器生成。静态路径通常是服务器生成的，因为这样开发者就可以修改要点并同时改变所有客户端。

　　在开放或封闭空间中的寻径有一个共同形式，那就是使用射线追踪法。其原理就是B-Line，即在最短的距离之间使用最少数量的节点生成最短的路径。射线追踪法最常见的使用情况是用它制作静态地图。这通常是用于游戏中的小镇或城市，玩家通常有几个经常访问的静态点。图1是一张城市地图，彩色点表示目标点。

　　一个点代表一个玩家经常访问的点。绿色点是玩家进入城市的点，红色点是玩家离开城市必经的点。我们的玩家希望在不走重复路线的情况下游览城市的每一个地点。作为人类，我们想象出达到所有目标的最快路径。逻辑上说，玩家会从绿色点依次移动到黄色点、灰色点、紫色点、棕色点和红色点。但计算机怎么知道人类的这种逻辑，又怎么找到这种达到所有目标的路径？为此，系统要依靠寻径方法。这时可以使用B-Line逻辑，尽管产生相同结果所需的时间比射击追踪法要更长一些。两种方法的区别在于，在B-Line中，系统一个点一个点地追踪最佳路径。而在射线追踪法中，各个点都发射出预设的方向射线，标记着和射线之是的交点。当把玩家角色从一个地点移动到另一个地点时，系统就利用这些交点形成的节点。首先，最好使用简单的算法，所以最好的办法是从各个点移动，在八个基本方向上发出射线。这些射线应该从所有节点同时发出。图2显示了节点发出射线的结果：

　　所有射线发出后，系统必须找到它们之间的交点。这些点有两个功能：一是角色移动的停止点；二是作为射线发射的新节点。这样节点就可以覆盖整张地图，使玩家具有多条移动路径。这些不同的点是必须的，因为玩家可以选择手动寻径或系统自动寻径。然而，在我们的案例中，系统将把静态地点与动态移动系统的概念—-允许玩家随心所欲地移动相结合，使玩家不受预设路径的限制。在图3中，用圆圈圈出来的点是静态移动中唯一可以使用的点，而其他点则是后来生成的。

　　如图所示，灰色点、紫色点和棕色点之间有许多交点。但绿色点和黄色点只有一个交点。为了直观，图4移除了不产生交点的线；还移除了交点与墙体之间的交点。这样我们就能比较清楚地看到计算机可以生成的最佳路径。

　　正如之前所说的，寻径是为了找到不重复的路线。为了达到这个目标，必须先定义单一的路径。当评估不同的可用路径时，可能使用到许多不同的节点。但为了简单，图5没有显示所有交点。这不是最短的路径，但是可能被选择的路径。

　　在图5的例子中，顺序与原来所说的是不同的。那是因为有时候系统可能选择不同于玩家的路径。所以计算机系统如何运作这个方法？几乎没有什么引擎能够一次性搜索所有可能的射线。然而，许多引擎能够在2D网格上放出射线，然后在移除它们以前使它们保持有效的状态，以用于交点检测。最好的做法是，让系统计算所有点出发的射线，在绘制各条射线之时检测所有可能的交点。当找到交点，就生成一个节点。找到所有可能的节点后，系统可以利用这些节点生成玩家一般情况下会选择的动态路径。在静态系统中，当玩家选择自动寻径时，系统就会利用这些被储存起来的节点。但正如之前的案例表明，并非所有节点和路径都产生了。

　　为此，系统必须使用节点生成剩下的路径。在开头时提到，这生成更有深度的地图，但仍然不完整。如果我们看看图2，会发现节点路径内仍然有空隙。为了完善地图，我们还要做一件事。算法必须使用那些节点发出更多射线。在图6中，可能的新射线用黑线标出。

　　仍然有空隙。在地图的左半边，显然有空隙。为了解决这个问题，可以使用新的节点来完善地图。结果表现在图7中。然而，左下角的地方还是有很大的空隙。

　　最后一步可以使用的是B线概念。B线的基础就是做一个三角形，以生成路径。一般情况下，这个三角形是用于寻找直角的斜边的。然而，在这个案例中，算法被颠倒了。我们知道，绿色点和红色点会在有空隙的地图区域内形成三角。图8显示了使用已知路径和最后节点产生的B线三角形：

　　使用了这个三角形后，生成了两个新节点。那两个节点像其他结点一样，用来完善地图路径。左下方的节点不是很有用，但直角三角形斜边的右上方的节点特别有用。这种方法和算法的结合经常用于制作游戏世界中的静态地图，但在动态变化中的环境中，实际执行比本文所说的要复杂得多。因此，还要使用其他方法，但如果正确使用射线追踪法，也是非常有效的。然而，射线追踪法可以作为其他方法的补充，比如用于寻找两条路径的交点。这普遍使用于武器交火和碰撞检测。任何问题都没有唯一正确的解决方案，但这个概念可以使逻辑更加人性化。