Chapter 4 Pathfinding

游戏中的角色需要在关卡中移动,有时他们的移动路径是预先设定的,例如巡逻路线等等。那些更复杂的角色则无法预先知道其将要去哪里。那么我就要为这一部分AI计算一条合适的路径抵达他们的目的地,同时还需要考虑关卡内的地形等各种因素。此外我们还希望这条路径是合理的,并且花费的时间越短越好。

这就是所谓的pathfinding(寻路),有时我们也将其称为pathplanning。

大多数的游戏会使用基于A星的寻路算法。虽然这个算法非常容易实现,但是A*不能直接用于游戏的关卡数据。其需要我们将游戏关卡的地形等数据转换为特定的数据结构:一个带有方向且大于零的权重图标。

本章节我们首先会学习这一数据结构,之后则会学习A星的好兄弟,Dijkstra算法。虽然Dijkstra更多的用在战术决策而不是pathfinding,但是其比A星更容易理解,所以我们会学习它,之后才是A星。

之后我们将学习如何将关卡的几何数据转换为寻路算法所需要的数据。最后则是学习基本A星算法的一些衍生算法。

4.1 寻路图表

A星也好Dijkstra也好,他们都不能直接使用关卡内的一些几何数据。他们需要一种更简化的数据结构。而我们的寻路算法所使用的图标则被称为directed non-negtive weighted graph(带有方向的非负权重图表)。

4.1.1 图表

我们所说的图标由两种元素组成:节点以及节点与节点之间的连接。如下图所示。

对于寻路系统,每一个节点可能表示关卡中的某个区域,例如房间,通道,平台或者室外的一小部分区域等等。如果一个房间紧挨着通道,那么代表房间的节点与代表通道的节点将会互相连接。所以,游戏的整个关卡将被分割成各个互相连接的区域。

为了从关卡内的一个位置抵达另一个位置,我们需要使用连接。如果我们所在的节点与目标节点是直接相连的,那么哦们只需要使用连接即可。否则,我们需要使用多个连接,穿过多个中间节点才能抵达目的地。

4.1.2 权重图表

权重图表与上文的图表相比,只是在节点之间的连线上添加了一个数值。这个数值就是所谓的权重,在寻路算法中,我们更习惯将他称为cost(成本)。如下图所示。

在寻路图表中,cost会代表时间或者距离。如果从当前节点到达另一个节点的距离较长,那么相应的,这两个节点的cost会更大。相应的,如果两个节点之间的地形比较复杂,通行所花费的时间更长,那么cost也会更大。除此之外,cost还能表示战略意义上的风险或者某处的搜刮效益等等。

在权重图表上,从起始节点到目标节点,整条路径上所有连接的cost总和就是该路径的总体cost。以上图为例,如果我们从A通过B到达C,那么总的cost就是4+5=9。

点表示区域

你可能会想到,如果两个区域紧挨着,那么他们之间的距离应该是0。如果一个人站在房间的门口,那么其移动到门外的通道,只需要迈出一步即可。所以说,所有的连接都需要一个零cost吗?

一般来说,我们会在两个区域内各自选取一个代表点来确定这两个区域连接的距离与时间。对于上述例子,我们会分别选择房间与通道的中心点。如果房间较大,通道又比较长,那么他们中心点之间的距离也会比较长,所以cost会比较高。

然而这种测算方法到底好不好,我们会在之后的小节中学习。

非负限制

将cost设为负数?这显然没有太大的意义,因为两地之间的距离不可能为负数,从一地到达另一地所需要的时间也不可能是负数。

虽然在数学意义上,我们可以将权重图标的cost设为负数,但在游戏中我们不会这么做。而且,当cost为负数时,寻路算法的复杂程度也会更高。

在本书中,当作者提到cost,那么我们默认这是一个非负的值。

4.1.3 带有方向的权重图表

大多数情况下,权重图表已经足够应付我们的游戏关卡。但是,我们还可以更进一步。大多数寻路算法都支持带有方向的权重图表,其对于开发者而言也更有用。如下图所示。

到现在为止,我们的假设都简历在,节点A与节点B互相连通。也就是说,如果能通过A到达B,那么从B也能到达A,且两个方向的cost也是相同。对于带有方向的权重图表,那么上述情况下,A与B存在着两条连接。

节点之间的方向概念,在某些情况下非常有用。假设,A表示一个处于低位的台阶,B表示一个处于高位的台阶。那么一个角色能从A点掉至B点,但是无法从B点跳到A点。

此外,两个节点之间存在两个连接,意味着我们可以设置两个cost。例如,向上可以表示花费较多的时间,也就是说cost更大。向下,花费时间更少,那么cost也更少。

4.1.5 实现

现在我们需要将上述图表转换为A星算法,或则Dijkstra能够使用的数据结构。

class Graph:
    function getConnections(fromNode: Node) -> Connection[]

class Connection:
    fromNode: Node

    toNode: Node

    function getCost() -> float

Graph类只是简单地返回了Connection数组。需要注意的是,我们并没有在上述代码中定义Node,这是因为很多时候,只需要使用一个整型数就能定义一个node,其不需要包含其他信息。

留下评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据