游戏算法（1）：实现AStar寻路算法
本文从项目从2D项目寻路需求做介绍。实现了Astar的带权宽搜算法。
本文链接 游戏算法（1）：实现2D寻路算法
相关文章 游戏算法（2）：查找优化之四叉树的应用
一、寻路算法简介
寻路有很多种。主要有以下几种
1、预置路径点寻路
比如常见的Astar算法，常用于2d或平面寻路。
优点是简便，缺点是当路径点数量增多后，运算复杂度会几何级增长。不支持有体积物体寻路、不支持高度方向的寻路机制、不支持重叠地图寻路（比如2楼）。且移动时会出现路径不平滑、身体抖动现象。
2、网格寻路
常用于没有预置路径点的范围寻路，效率比较高。3D MMORPG中常用到，支持x、y、z个维度方向的寻路，支持带体积物体寻路，支持山洞、上楼梯等寻路机制。
3、多目标群体寻路
这个在星际争霸、魔兽争霸等策略型游戏中常见到，算法也更为复杂。有兴趣的可以查看相关资料。
二、理解AStar算法
1、Astar算法是一种宽度搜索优先的图遍历算法，区别是Astar给每个节点增加了权重值。
在搜索过程中，不断调整当前节点的最优前驱节点（开放列表节点），该前驱节点满足，使当前位置节点的评估值 F 更小。
假设起始点为S，当前位置节点是C，其开放节点列表为 P = 【P1、P2、...、Pn】，终点为E。
起始点到当前点的代价评估值 F = G + H，其中 G = G0 + Cost
F：起始点S到终点E的代价评估值
G：起始点S到当前点C的代价评估值
H：当前点C到终点E的代价评估值
G0：起始点到当前点C的前驱节点（开放列表节点P1、P2等）的代价评估值
Cost：当前点C的前驱节点（开放列表节点P1、P2等）到当前点C的代价值。一般是预设好的。
（1）遍历开放列表P，计算当前节点C的新G值，然后通过F = G + H计算其F值，每当如果Pi计算出的F值更小，则修改当前节点的前驱节点指向Pi。
（2）采用一定的算法（比如曼哈顿距离）来评估当前位置到终点间的距离H。对同一个节点，一般情况下H值是固定的。
2、图示
F = G + H
当然这里的G、Cost、H可以时固定的，也可以是变化的。
在2d寻路中，Cost一般时固定的，比如左右行走一个是1，斜着走就是1.5。而H采用了曼哈顿距离函数
扩展到通用状态时，他们分别是由评估函数G()、cost()、和H()函数来决定的。
最终，计算到终点后，则从终点E开始，反向递归查找最优前驱节点，组成的链表，就是我们要找的最佳寻路路径。
二、 实现AStar算法
以下以typescript代码实现为例，展示实现过程。
1、路径点对象类
export class MapPathItemObject {
pos: { x: number, y: number} = {x: 0, y: 0}; // 坐标
linkItems: MapPathItemObject[] = []; // 邻接点列表
}
2、实现图对象类
/**
* 数据结构-图
* 2020-11-18
* (c) copyright 2018 - 2035
* All Rights Reserved.
*/
export class Graph<T> {
/** 对象合集 */
protected objList: HashTable<GraphNode<T>> = new HashTable<GraphNode<T>>();
/** 与对象相邻的其他对象合集 */
protected linkObjList: HashTable<GraphNode<T>[]> = new HashTable<GraphNode<T>[]>();
constructor() {
}
/** 对象是否注册 */
public addLinkObject(ownObj: T, obj: T): void {
let ownId = getFunctionId(ownObj);
if (!this.isObjAdd(ownObj)) {
this.addObject(ownObj);
}
let linkList = this.linkObjList.get(ownId);
if (!linkList) {
linkList = [];
this.linkObjList.insert(ownId, linkList);
}
if (!this.isObjAdd(obj)) {
this.addObject(obj);
}
let id = getFunctionId(obj);
let gNode = this.objList.get(id);
linkList.push(gNode);
}
/** 添加对象 */
public addObject(obj: T): void {
let id = getFunctionId(obj);
if (this.objList.get(id)) {
return;
}
this.objList.insert(id, new GraphNode<T>(obj));
}
/** 对象是否已添加 */
public isObjAdd(obj: T): boolean {
let id = getFunctionId(obj);
return !!this.objList.get(id);
}
/** 获取图节点对象 */
public getGraphNode(obj: T): GraphNode<T> {
let id = getFunctionId(obj);
return this.objList.get(id);
}
/** 获取图节点的邻接列表对象 */
public getNodeLinkList(obj: T): GraphNode<T>[] {
let id = getFunctionId(obj);
return this.linkObjList.get(id);
}
/** 获取图节点的邻接列表对象 */
public getGraphNodeLinkList(graphNode: GraphNode<T>): GraphNode<T>[] {
let id = graphNode.getId();
return this.linkObjList.get(id);
}
/** 是否相邻 */
public isGraphNodeLink(obj1: T, obj2: T): boolean {
let linkList = this.getNodeLinkList(obj1);
if (linkList) {
let graphNode = this.getGraphNode(obj2);
return graphNode && linkList.indexOf(graphNode) >= 0;
}
return false;
}
}
export class GraphNode<T> implements GraphNodeInterface {
obj: T = null;
id: number | string;
constructor(obj: T) {
this.obj = obj;
this.id = this.getId();
}
getId() {
return this.id || getFunctionId(this.obj);
}
}
export interface GraphNodeInterface {
getId();
}
3、实现Astar算法类
/**
* Astar寻路算法
* (1) 以图、邻接对象为原型
* (2) 宽度优先搜索
* (3) 支持自定义评估函数
* 2020-11-18
* (c) copyright 2018 - 2035
* All Rights Reserved.
*/
export class PathFind<T> {
/** 图信息 */
protected _graph: Graph<T> = null;
/** 评估函数G */
protected _evalGFunc: (obj1: T, obj2: T) => number = null;
/** 评估函数H */
protected _evalHFunc: (obj1: T, obj2: T) => number = null;
/** 开放列表哈希表缓存 */
protected _openHashList: HashTable<GraphNode<T>> = new HashTable<GraphNode<T>>();
/** 开放列表缓存 排序、头节点F值最小 */
protected _openSortList: GraphNode<T>[] = [];
/** 关闭列表缓存 */
protected _closeList: HashTable<GraphNode<T>> = new HashTable<GraphNode<T>>();
/** 评估值G列表缓存 */
protected _gScoreList: HashTable<number> = new HashTable<number>();
/** 评估值F列表缓存 */
protected _fScoreList: HashTable<number> = new HashTable<number>();
/** 节点的最优父节点缓存 */
protected _parentNodeHashList: HashTable<GraphNode<T>> = new HashTable<GraphNode<T>>();
constructor(graph?: Graph<T>) {
this._graph = graph;
if (!this._evalGFunc) {
this._evalGFunc = (obj1: T, obj2: T) => {
return 1;
};
}
if (!this._evalHFunc) {
this._evalHFunc = (obj1: T, obj2: T) => {
return 1;
};
}
}
/**
* 查找路径
* @return 路径对象数组。不包含起始点
*/
public find(fromObj: T, toObj: T): T[] {
if (this._graph.isGraphNodeLink(fromObj, toObj)) {
return [toObj];
}
let linkList = this._graph.getNodeLinkList(fromObj);
if (!linkList) {
return [];
}
let graphNode = this._graph.getGraphNode(fromObj);
let gScore = this._evalGFunc(fromObj, fromObj);
let hScore = this._evalHFunc(fromObj, toObj);
this.openGraphNode(graphNode, gScore, hScore, null); // 将起始点放入开放列表
let parentNode: GraphNode<T> = null;
let isFind: boolean = false;
while (this._openSortList.length > 0) { // 带权广搜开放列表节点
parentNode = this._openSortList.shift();
if (!parentNode) {
continue;
}
if (parentNode.obj == toObj) {
isFind = true;
break;
}
this.closeGraphNode(parentNode); // 放入关闭列表
let linkList = this._graph.getGraphNodeLinkList(parentNode);
if (!linkList) {
continue;
}
for (let i = 0; i < linkList.length; i++) {
const gNode = linkList[i];
if (this.isInCloseList(gNode)) {
continue;
}
let preGScore = this._gScoreList.get(parentNode.getId());
gScore = preGScore + this._evalGFunc(parentNode.obj, gNode.obj);
hScore = this._evalHFunc(gNode.obj, toObj);
if (this.isInOpenList(gNode)) {
let oldGScore = this._gScoreList.get(gNode.getId());
if (gScore < oldGScore) {
this.updateOpenGraphNode(gNode, gScore, parentNode);
}
}else {
this.openGraphNode(gNode, gScore, hScore, parentNode);
}
}
}
let toGNode = this._graph.getGraphNode(toObj);
let pathList = this.getPathList(toGNode);
this.clearCache();
return pathList;
}
/** 节点放入开放列表 */
protected openGraphNode(graphNode: GraphNode<T>, gScore: number, hScore: number, parentNode: GraphNode<T>): void {
let id = graphNode.getId();
this._openHashList.insert(id, graphNode);
this._gScoreList.insert(id, gScore);
this._fScoreList.insert(id, gScore + hScore);
this._parentNodeHashList.insert(graphNode.getId(), parentNode);
this._openSortList = [graphNode].concat(this._openSortList);
this._openSortList = BaseTool.quickSort(this._openSortList, (node1: GraphNode<T>, node2: GraphNode<T>) => {
return this._gScoreList.get(node1.getId()) < this._gScoreList.get(node2.getId());
});
}
/** 更新开放节点信息 */
protected updateOpenGraphNode(graphNode: GraphNode<T>, gScore: number, parentNode: GraphNode<T>): void {
let id = graphNode.getId();
let oldGScore = this._gScoreList.get(id);
let oldFScore = this._fScoreList.get(id);
this._gScoreList.update(id, gScore);
this._fScoreList.update(id, gScore + oldFScore - oldGScore);
this._parentNodeHashList.update(graphNode.getId(), parentNode);
this._openSortList = BaseTool.quickSort(this._openSortList, (node1: GraphNode<T>, node2: GraphNode<T>) => {
return this._gScoreList.get(node1.getId()) < this._gScoreList.get(node2.getId());
});
}
/** 节点放入关闭列表 */
protected closeGraphNode(graphNode: GraphNode<T>): void {
let id = graphNode.getId();
this._closeList.insert(id, graphNode);
}
/** 是否在开放列表中 */
protected isInOpenList(graphNode: GraphNode<T>): boolean {
return !!this._openHashList.get(graphNode.getId());
}
/** 是否在关闭列表中 */
protected isInCloseList(graphNode: GraphNode<T>): boolean {
return !!this._closeList.get(graphNode.getId());
}
/**
* 根据父节点关系获取路径列表
*/
protected getPathList(endNode: GraphNode<T>): T[] {
if (!endNode) {
return [];
}
let result: T[] = [endNode.obj];
let pNode = this._parentNodeHashList.get(endNode.getId());
while (pNode) {
result.push(pNode.obj);
pNode = this._parentNodeHashList.get(pNode.getId());
}
return result.reverse();
}
/** 清理缓存 */
protected clearCache(): void {
this._openHashList.clear();
this._openSortList = [];
this._closeList.clear();
this._gScoreList.clear();
this._fScoreList.clear();
this._parentNodeHashList.clear();
}
set graph(graph: Graph<T>) {
this._graph = graph;
}
set evalGFunc(evalGFunc: (obj1: T, obj2: T) => number) {
this._evalGFunc = evalGFunc;
}
set evalHFunc(evalHFunc: (obj1: T, obj2: T) => number) {
this._evalHFunc = evalHFunc;
}
}
本文链接 游戏算法（1）：实现2D寻路算法
相关文章 游戏算法（2）：查找优化之四叉树的应用
