最短路径算法Dijkstra和A*

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

在设计基于地图的游戏,特别是isometric斜45度视角游戏时,几乎必须要用到最短路径算法.
Dijkstra算法是寻找当前最优路径(距离原点最近),如果遇到更短的路径,则修改路径(边松弛).
Astar算法基于Dijkstra算法, 可以理解成, 优先寻找离终点的直线距离最近的路径.(距离原点近且距离终点也近)

1. 地图建模
首先要对地图建模,把地图抽象成图,图由点和有向边表示.
对45度瓦块地图建模,以每个瓦块的中心是一个点,每个瓦块有8条边,指向相邻的8个瓦块.
(由于边可以由节点算出来,所以为了节省内存,可以不保存边的数据结构)

2. 基础数据结构
实现Dijkstra算法,要用到以下3个数据结构

vector<const Edge*> _shortestPathTree; // 最短路径树
最短路径树SPT的key是节点id,value是该节点的一条入边.由入边可以找到该节点的上一个节点.
SPT表示图上起点到任意点的最短路径.

vector<const Edge*> _searchFrontier; // 当前的搜索边界
搜索边界SF的key是节点id,value是该节点的一条入边.
SF表示当前需要考虑的边(节点),由于Dijkstra是贪心算法,所以需要把范围限定在SF寻找局部最优解.

优先队列PQ
PQ作为SF的辅助数据结构,放入(修改)SF中的点也放入(修改)PQ,
PQ为这些点排序(距原点的代价从小到大). 当边松弛时,调整PQ里的排序.
优先队列的数据结构以后写日志介绍.

vector<double> _costs; // 到每个节点的cost
代价COSTS的key是节点id, value是从原点到该点的代价.

3. 算法步骤
(1) 原点O放入SPT,然后O的所有出边(点)都放入SF
(2) 找到SF上距离O最近的点N(通过PQ)
(3) 遍历N的每条出边E指向的点P
(4) 如果P不在SF上,则把<P,E>加入SF
(5) 如果P在SF上且OP新的代价小于老的代价,则修改SF(边松弛)
(6) 重复(2)-(5)直到把目标放入SPT.

4. A*
A*算法完全基于Dijkstra算法.
只是PQ的排序不是按照当前节点到原点的实际代价_costs
而是按照当前节点到原点的启发式代价_fCosts
假设点N到原点的实际代价是_costs[N]
则有4种常用方法计算_fCosts
(1) 直线距离启发因子
_fCosts[N] = _costs[N] + distance(N, O)
(2) 有噪声的直线距离启发因子
_fCosts[N] = _costs[N] + distance(N, O) * random()
(3) 退化成Dijkstra算法的启发因子

_fCosts[N] = _costs[N] + 0
(4) Manhattan启发因子(在瓦块地图游戏中效果最好)
_fCosts[N] = _costs[N] + |position(N-O).x| + |position(N-O).y|