A*寻路算法总体来说还是比较简单和高效的，这里对在项目中的使用记录下，源码如下
设计一个二维数组类ArrayList.ts
/**
* Autor: Created by 李清风 on 2020-11-17.
* Desc: ArrayList
*/
export class ArrayList {
private _list: [any[]];
private _row;//矩阵行
private _colums;//矩阵列
public constructor(rows: number, colums: number, defalut: any = 0) {
this._list = [[]];
this._row = rows;
this._colums = colums;
this.initRows(rows);
this.initColumns(colums, defalut);
}
//初始化数组行
initRows(rows: number) {
if (rows < 1) {
return;
}
for (let i = 0; i < this._row; i++) {
let item:any[] = [];
this._list.push(item);
}
}
//初始化数组列
initColumns(columns: number, value: any) {
if (columns < 1) {
return;
}
for (let i = 0; i < this._list.length; i++) {
for (let j = 0; j < columns; j++) {
this._list[i].push(value)
}
}
}
getValue(rows: number, colums: number) {
if (rows < 0 || colums < 0 || rows >= this._row || colums >= this._colums) {
console.error("IndexOutOfRangeException: Index was outside the bounds of the array.")
return null;
}
return this._list[rows][colums];
}
setValue(rows: number, colums: number, value) {
if (rows < 0 || colums < 0 || rows >= this._row || colums >= this._colums) {
console.error("IndexOutOfRangeException: Index was outside the bounds of the array.")
return;
}
this._list[rows][colums] = value;
}
getArrayList(): Array<Array<any>> {
return this._list;
}
}
设计一个优先级队列PriorityQueue.ts
import { GridNode } from "./GridNode";
/**
* Autor: Created by 李清风 on 2020-11-17.
* Desc: PriorityQueue
*/
export class PriorityQueue {
private nodes: GridNode[] = [];
public Length() {
return this.nodes.length;
}
public Contains(node: GridNode) {
return this.nodes.includes(node);
}
public First(): GridNode {
if (this.nodes.length > 0) {
return this.nodes[0];
}
return null;
}
public Add(node: GridNode) {
this.nodes.push(node);
this.sort();
}
public Remove(node: GridNode) {
let index = this.nodes.indexOf(node);
if (index > -1) {
this.nodes.splice(index, 1);
}
this.sort();
}
private sort() {
let sortCallFunc = (a, b) => {
if (a.estimatedCost < b.estimatedCost) {
return -1;
}
if (a.estimatedCost > b.estimatedCost) {
return 1;
}
return 0;
}
this.nodes.sort(sortCallFunc)
}
}
设计一个节点格子类GridNode.ts
/**
* Autor: Created by 李清风 on 2020-11-17.
* Desc: GridNode
*/
export class GridNode {
public nodeTotalCost: number;
public estimatedCost: number;
public bObstacle: boolean;
public parent: GridNode;
public position: cc.Vec2; //矩阵行列式，也可代表x,y轴
public constructor() {
this.estimatedCost = 0;
this.nodeTotalCost = 1;
this.bObstacle = false;
this.parent = null;
}
public initWithPos(pos: cc.Vec2) {
this.estimatedCost = 0;
this.nodeTotalCost = 1;
this.bObstacle = false;
this.parent = null;
this.position = pos;
}
public MarkAsObstacle() {
this.bObstacle = true;
}
}
设计管理格子的管理类GridManager.ts
import { ArrayList } from "./ArrayList";
import { GridNode } from "./GridNode";
/**
* Autor: Created by 李清风 on 2020-11-17.
* Desc: 地图网格化管理器
*/
export class GridManager {
private static _instance: GridManager;
public static getInstance(): GridManager {
if (GridManager._instance == null) {
GridManager._instance = new GridManager();
}
return GridManager._instance;
}
public numOfRows: number; //行数
public numOfColumns: number;//列数
public girdCellSize: number;
public showGrid: boolean;
nodes: ArrayList;
public obstacleList: any[];
public init(row: number, column: number, mapData: any) {
if (!mapData) {
console.error('地图数据加载失败');
return;
}
this.numOfRows = row; // 53 (0,52)
this.numOfColumns = column; //45(0-44)
this.CalcuateGirdNodes(mapData);
}
/**
* 初始化网格da
* @param mapData json数据
* @param 注:网格是严格按照x，y对应来进行初始化的，但是遍历map需要额外处理下
*/
public CalcuateGirdNodes(mapData: any) {
this.nodes = new ArrayList(this.numOfRows, this.numOfColumns);
for (let i = 0; i < this.numOfColumns; i++) {
for (let j = 0; j < this.numOfRows; j++) {
let node: GridNode = new GridNode();
node.initWithPos(cc.v2(j, i))
//BlockType.disable 自己设计的标签，不可行走
//BlockType.occlusion 障碍物
//BlockType.Basket 其他
if (mapData[i][j] == BlockType.disable || mapData[i][j] == BlockType.occlusion ||
mapData[i][j] == BlockType.Basket) {
node.MarkAsObstacle();
}
this.nodes.setValue(j, i, node);
}
}
}
private GetRow(pos: cc.Vec2) {
let row = pos.x
return row;
}
private GetColumn(pos: cc.Vec2) {
let colums = pos.y;
return colums;
}
private GetGridNodeByRowColumn(row: number, column: number) {
return this.nodes.getArrayList()[row][column];
}
/**
* 取8个点
* @param node
* @param neighbors
*/
public GetNeighbours(node: GridNode, neighbors: GridNode[]) {
let neighborPos: cc.Vec2 = node.position;
let row = this.GetRow(neighborPos); // 26
let colum = this.GetColumn(neighborPos); //20
//左
let leftNodeRow = row - 2;
let leftNodeColum = colum;
this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
//右
leftNodeRow = row + 2;
leftNodeColum = colum;
this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
//上
leftNodeRow = row;
leftNodeColum = colum + 1;
this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
//下
leftNodeRow = row;
leftNodeColum = colum - 1;
this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
//左上
leftNodeRow = row - 1;
leftNodeColum = colum;
this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
//右上
leftNodeRow = row + 1;
leftNodeColum = colum;
this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
//左下
leftNodeRow = row - 1;
leftNodeColum = colum - 1;
this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
//右下
leftNodeRow = row + 1;
leftNodeColum = colum - 1;
this.AssignNeighbour(leftNodeRow, leftNodeColum, neighbors);
}
private AssignNeighbour(row: number, colum: number, neighbors: GridNode[]) {
if (row != -1 && colum != -1 && row < this.numOfRows && colum < this.numOfColumns) {
let nodeToAdd: GridNode = this.GetGridNodeByRowColumn(row, colum);
if (!nodeToAdd.bObstacle) {
neighbors.push(nodeToAdd);
}
}
}
}
设计核心的脚本AStar.ts
/**
* Autor: Created by 李清风 on 2020-11-17.
* Desc: A*
*/
import { GridManager } from "./GridManager";
import { GridNode } from "./GridNode";
import { PriorityQueue } from "./PriorityQueue";
export class AStar {
private static openList: PriorityQueue;
private static closeList: PriorityQueue;
private static NodeCost(a: GridNode, b: GridNode): number {
let vecCost: cc.Vec2 = a.position.sub(b.position);
return vecCost.mag();
}
public static FindPath(start: GridNode, goal: GridNode): any {
AStar.openList = new PriorityQueue();
AStar.openList.Add(start);
AStar.closeList = new PriorityQueue();
start.nodeTotalCost = 0;
start.estimatedCost = AStar.NodeCost(start, goal);
let node: GridNode = null;
while (AStar.openList.Length() != 0) {
node = AStar.openList.First();
if ((node.position.x == goal.position.x) && (node.position.y == goal.position.y)) {
return AStar.CalculatePath(node);
}
let neighbours: GridNode[] = [];
GridManager.getInstance().GetNeighbours(node, neighbours);
for (let i = 0; i < neighbours.length; i++) {
let neighbourNode: GridNode = neighbours[i];
if (!AStar.closeList.Contains(neighbourNode)) {
let cost: number = AStar.NodeCost(node, neighbourNode);
let totalCost = node.nodeTotalCost + cost;
let neighbourNodeEstCost = AStar.NodeCost(neighbourNode, goal);
neighbourNode.nodeTotalCost = totalCost;
neighbourNode.estimatedCost = totalCost + neighbourNodeEstCost;
neighbourNode.parent = node;
if (!AStar.openList.Contains(neighbourNode)) {
AStar.openList.Add(neighbourNode);
}
}
}
AStar.closeList.Add(node);
AStar.openList.Remove(node);
}
if ((node.position.x == goal.position.x) && (node.position.y == goal.position.y)) {
console.error("Arrived Goal Path Not Found");
return null;
}
return AStar.CalculatePath(node);
}
private static CalculatePath(node: GridNode): any {
let list: GridNode[] = [];
while (node != null) {
list.push(node);
node = node.parent;
}
list.reverse();
return list;
}
}