四月一日对寻路部分代码修

寻路规则概述

A*算法应用应该是很广泛,不仅仅只在游戏寻路中。所以有通用性,就有一定的相似点,这就是规则。

A* 可以抽象出4个规则,即:连通性判断,节点扩展,G值计算,H值计算。

下面基于使用到A* 的地方简单介绍几个规则的实现,用以理解,也便于之后各章的理解。

BaseNodeRule

因为地图节点使用比较规则的矩形来表示,可以谁用坐标来代表某个节点,所以某些规则上就可以很容易的理解。

首先是连通性规则,只要两个节点的横或纵坐标只相差一(4节点扩展)或横纵坐标同时相差一(8节点扩展),并且两个节点都是可以到达的(非障碍),则就说明这两个节点是联通的。

节点扩展,4节点扩展即是该节点的上下左右节点,8节点是在4节点基础上再加上四个对角的节点,只要这些节点在地图中计算扩展节点。当然也可以在此处加上判断该节点是否是障碍的判断。

G值计算,横纵计算每深一步加10,对角计算每深一步增加14;

H值计算,计算当前点与目标点的曼哈顿距离。

LinkAreaRule

因为联通块形状是不规则的,无法使用坐标来进行表示,所以会有点抽象。

连通性规则,只要两个联通块间有入口相连,即具有连通性。

节点扩展,只要是与当前联通块有入口相连的所有联通块都属于其扩展节点

G值计算,计算两个联通块所在的Cluster的距离,然后类似计算BaseNode的G值计算。

H值计算:计算当前联通块所在的Cluster与终点联通块所在的Cluster的曼哈顿距离。

worldPathRule

跨地图寻路规则,应该是更具抽象意义。

连通性规则:通过读取的配置数据,如果两个地图可达,则局有连通性

扩展规则:通过读取的配置,将该地图所能到达的其他地图全部获取即可

G值计算:每计算一次,则加深一步,使用固定值

H值计算:意义不大,可以忽略。

G值修改

G值可以理解为当前扩展到的节点距起点的距离,也就是寻路到当前阶段的深度。所以当扩展到当前节点时,要在其父节点的基础上进行增加。

本人的理解偏差在以为G值是当前节点据父节点的距离。

实际的代码是使用了固定值。所以基本寻路时估算值F基本上是由H值决定的了。以至很多时候寻到的路并不是最近路径。

优化大改

储存结构修改

1. 路径储存

主要针对的是SimpleList。

这其实就是个链表,每次增加一个元素,都会被new一次储存,尤其在效率敏感区,会严重影响寻路效率。而且其中元素的查找也是会很慢,这也将是寻路中一个限制寻路速率的原因之一。

因为当时设计了SimpleList,感觉也是很方便的使用,所以其应用泛滥成灾,如果将这一部分优化掉,将会很大的提高寻路效率。

对寻路效率影响比较大的应用是:寻路节点扩展规则返回的扩展出的节点储存,寻路最终路径储存,关闭列表。

这里只讲下路径的存储,其他在下面将讲到。

现在摒弃SimpleList储存最终路径,而是用节点自身的父节点指针进行连接。每次寻路完毕后,保留其寻路数据,只对不相关数据进行重置。最终路径返回目标节点的指针,然后外部根据该节点的pParent指针一步一步往上找,直到为空,也即直到找到开始节点为止,此即为最终路径。

clip_image002

如图所示,绿点为起点,红点为目标点。

寻路完成后,根据红点的父指针的指向,即蓝色箭头所指,不断地迭代上找,直到找到绿点位置。所有蓝色箭头即为路径。

2. 关闭列表储存

A*寻路中两个储存列表,打开列表与关闭列表。因为两个列表的侧重点不同,所以用于进行储存的结构也应有所差别。

打开列表侧重快速有序的插入与删除,而关闭列表需要能够快速遍历。

之前关闭列表使用的是SimpleList,因为每次寻路并不能确定关闭列表实际能够保存节点的数量。

现修改为使用数组保存。

对于基础节点寻路,因为如果使用基础节点寻路,则说明两个点是在同一联通块内部的,而联通块又是属于某个Cluster,所以可以将节点内寻路限制在某个Cluster内部,一个Cluster最多有512个节点,所以Cluster内部寻路关闭列表的大小最大也只512而已,因此使用512作为数组大小将非常合适。

对于联通块寻路,因为对于较长将复杂的路径寻路做了扩展限制,即如果当扩展了n个联通块后如果还未找到路径,则返回路径为找到。所以以此限制作为数组大小也将非常合适。

3. 寻路数据

这里的寻路数据指通用寻路数据。即指A* 寻路中不能缺少的数据。

struct sPathFindingInfo

{

sPathFindingInfo(COORDTYPE x = 0, COORDTYPE y =0):nF(0),nG(0),nH(0),nBPos(-2){kCoordinate.x = x; kCoordinate.y = y;};

sCoordinate kCoordinate; // 坐标

short nF,nG,nH; // nF = nG + nH;

int nBPos; // == -2默认值,表示正常状态。== -1 表示处于关闭列表中;否则就表示在打开列表中的位置

};

其中该结构中的”坐标”并不是必要数据,这是当时考虑到内存优化时放入的。

其余数据都将在A*中使用到。

原来寻路时,每个节点的寻路数据在每次寻路完成后即在内存池中删除,下次寻路时再重新在内存池中new出来。

现在的做法是如果被new一次就不在下次new了,寻路完成后只对数据进行重置即可。

规则修改

1. 扩展规则
BaseNode

原来扩展出来的节点是保存在SimpleList中的,为了优化速率,现改为使用数组存储。因为基础节点的特殊性,所以使用了一个大小为8的sCoordinate数组。扩展规则函数原型修改为:

clip_image004

nOutSpreadNum返回实际扩展的节点数量

BaseNode的Spread函数的内部实现也做了优化修改。

发表评论

邮箱地址不会被公开。 必填项已用*标注

* Copy This Password *

* Type Or Paste Password Here *