487c68994d
feat: add cocos-service configuration file feat: add device configuration file feat: add engine configuration file feat: add information configuration file feat: add program configuration file feat: add project configuration file feat: add TypeScript configuration file
428 lines
16 KiB
TypeScript
428 lines
16 KiB
TypeScript
type index = {
|
||
x: number,
|
||
y: number
|
||
}
|
||
|
||
/**
|
||
* AStar类用于实现A*寻路算法。
|
||
*/
|
||
export class AStar {
|
||
private map: any[][] = []; // 地图数组
|
||
private weightMap: number[][] = null; // 权重地图数组
|
||
private openlist: index[] = []; // 开放列表，存储待评估的节点
|
||
private closelist: index[] = []; // 封闭列表，存储已评估的节点
|
||
private parentMap: Map<index, index>; // 父节点映射，用于回溯路径
|
||
private gcostMap: Map<index, number>; // g成本映射，记录从起点到当前节点的成本
|
||
private hcostMap: Map<index, number>; // h成本映射，记录从当前节点到终点的估算成本
|
||
private startValue: number = 0;
|
||
private endValue: number = 0;
|
||
private pathValue: number = 0;
|
||
private isEightDirections: boolean = false;
|
||
private neighborMap: Map<index, index[]>;
|
||
|
||
constructor() {
|
||
this.openlist = [];
|
||
this.closelist = [];
|
||
this.parentMap = new Map();
|
||
this.gcostMap = new Map();
|
||
this.hcostMap = new Map();
|
||
}
|
||
|
||
/**
|
||
* 设置地图。
|
||
* @param map 二维数组表示的地图
|
||
*/
|
||
setMap(map: number[][]) {
|
||
this.map = map;
|
||
}
|
||
|
||
/**
|
||
* 设置权重地图。
|
||
* @param weightMap 二维数组表示的权重地图
|
||
*/
|
||
setWeightMap(weightMap: number[][]) {
|
||
this.weightMap = weightMap;
|
||
}
|
||
|
||
setValue(startValue: number, endValue: number, pathValue: number) {
|
||
this.startValue = startValue;
|
||
this.endValue = endValue;
|
||
this.pathValue = pathValue;
|
||
}
|
||
|
||
setEightDirections(isEightDirections: boolean) {
|
||
this.isEightDirections = isEightDirections;
|
||
}
|
||
|
||
setNeighborMap(neighborMap: Map<index, index[]>) {
|
||
this.neighborMap = neighborMap;
|
||
}
|
||
|
||
/**
|
||
* 在给定范围内根据指定类型搜索从起点到终点的路径。
|
||
* @param start 起点索引
|
||
* @param end 终点索引
|
||
* @param type 搜索类型（可能影响启发式函数的选择）
|
||
* @returns 返回找到的路径数组，如果无路径则返回空数组
|
||
*/
|
||
search(start: index, end: index, type: number) {
|
||
this.init(); // 初始化搜索环境
|
||
|
||
if (this.map[start.y][start.x] !== this.startValue ||
|
||
this.map[end.y][end.x] !== this.endValue) {
|
||
console.log("Invalid start or end point");
|
||
return [];
|
||
}
|
||
|
||
// 初始化起点信息，并将其加入开放列表
|
||
this.openlist.push(start);
|
||
this.gcostMap.set(start, 0); // 起点到起点的距离为0
|
||
this.hcostMap.set(start, this.getHeuristicCost(start, end, type)); // 起点到终点的启发式成本
|
||
this.parentMap.set(start, null); // 起点的父节点设置为null
|
||
|
||
// 循环直到开放列表为空，即所有可能的路径都被考虑
|
||
while (this.openlist.length > 0) {
|
||
const current = this.getMinCostNode(this.openlist); // 从开放列表中选择成本最小的节点
|
||
|
||
if (!current) {
|
||
this.openlist.splice(this.openlist.indexOf(current), 1);
|
||
continue;
|
||
}
|
||
|
||
// 判断是否到达终点
|
||
if (this.isArrived(current, end)) {
|
||
return this.reconstructPath(end); // 如果到达终点，返回路径重构的结果
|
||
} else {
|
||
// 从开放列表移除当前节点，将其加入封闭列表
|
||
this.openlist.splice(this.openlist.indexOf(current), 1);
|
||
this.closelist.push(current);
|
||
|
||
// 遍历当前节点的所有邻居节点
|
||
const neighbors = this.getNeighbors(current);
|
||
for (const neighbor of neighbors) {
|
||
const hCost = this.getHeuristicCost(neighbor, end, type); // 计算邻居节点到终点的启发式成本
|
||
const gCost = this.gcostMap.get(current) + this.getGCost(current, neighbor, type); // 计算当前节点到邻居节点的实际成本
|
||
const totalCost = gCost + hCost; // 计算总成本
|
||
|
||
// 根据邻居节点的状态进行处理
|
||
if (!this.isInClosedList(neighbor)) {
|
||
if (!this.isInOpenList(neighbor)) {
|
||
this.openlist.push(neighbor); // 如果邻居未在开放列表中，将其加入
|
||
this.updateCost(neighbor, gCost, hCost); // 更新邻居节点的成本信息
|
||
this.updateParent(neighbor, current); // 更新邻居节点的父节点信息
|
||
} else {
|
||
// 如果邻居已在开放列表中，但通过当前节点发现更优路径
|
||
if (totalCost < this.getCost(neighbor)) {
|
||
this.updateCost(neighbor, gCost, hCost); // 更新成本信息
|
||
this.updateParent(neighbor, current); // 更新父节点信息
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
console.log("No path found.");
|
||
return []; // 如果无法找到路径，返回空数组
|
||
}
|
||
|
||
/**
|
||
* 初始化算法状态。
|
||
*/
|
||
private init() {
|
||
// 重置所有列表和映射
|
||
this.openlist = [];
|
||
this.closelist = [];
|
||
this.parentMap = new Map();
|
||
this.gcostMap = new Map();
|
||
this.hcostMap = new Map();
|
||
}
|
||
|
||
/**
|
||
* 获取当前节点的邻居。
|
||
* @param current 当前节点坐标
|
||
* @returns 邻居节点数组
|
||
*/
|
||
private getNeighbors(current: index) {
|
||
if (this.neighborMap.size === 0) {
|
||
const neighbors: index[] = [];
|
||
|
||
// 尝试获取四个方向的邻居节点
|
||
const upindex = { x: current.x, y: current.y + 1 };
|
||
const downindex = { x: current.x, y: current.y - 1 };
|
||
const leftindex = { x: current.x - 1, y: current.y };
|
||
const rightindex = { x: current.x + 1, y: current.y };
|
||
|
||
const upleftindex = { x: current.x - 1, y: current.y + 1 };
|
||
const uprightindex = { x: current.x + 1, y: current.y + 1 };
|
||
const downleftindex = { x: current.x - 1, y: current.y - 1 };
|
||
const downrightindex = { x: current.x + 1, y: current.y - 1 };
|
||
|
||
// 如果合法则加入邻居列表
|
||
if (this.isValidIndex(upindex) && (this.map[upindex.y][upindex.x] == this.pathValue ||
|
||
this.map[upindex.y][upindex.x] == this.endValue)) {
|
||
neighbors.push(upindex);
|
||
}
|
||
if (this.isValidIndex(downindex) && (this.map[downindex.y][downindex.x] == this.pathValue ||
|
||
this.map[downindex.y][downindex.x] == this.endValue)) {
|
||
neighbors.push(downindex);
|
||
}
|
||
if (this.isValidIndex(leftindex) && (this.map[leftindex.y][leftindex.x] == this.pathValue ||
|
||
this.map[leftindex.y][leftindex.x] == this.endValue)) {
|
||
neighbors.push(leftindex);
|
||
}
|
||
if (this.isValidIndex(rightindex) && (this.map[rightindex.y][rightindex.x] == this.pathValue ||
|
||
this.map[rightindex.y][rightindex.x] == this.endValue)) {
|
||
neighbors.push(rightindex);
|
||
}
|
||
|
||
if (this.isEightDirections) {
|
||
if (this.isValidIndex(upleftindex) && (this.map[upleftindex.y][upleftindex.x] == this.pathValue ||
|
||
this.map[upleftindex.y][upleftindex.x] == this.endValue)) {
|
||
neighbors.push(upleftindex);
|
||
}
|
||
if (this.isValidIndex(downleftindex) && (this.map[downleftindex.y][downleftindex.x] == this.pathValue ||
|
||
this.map[downleftindex.y][downleftindex.x] == this.endValue)) {
|
||
neighbors.push(downleftindex);
|
||
}
|
||
if (this.isValidIndex(downrightindex) && (this.map[downrightindex.y][downrightindex.x] == this.pathValue ||
|
||
this.map[downrightindex.y][downrightindex.x] == this.endValue)) {
|
||
neighbors.push(downrightindex);
|
||
}
|
||
if (this.isValidIndex(uprightindex) && (this.map[uprightindex.y][uprightindex.x] == this.pathValue ||
|
||
this.map[uprightindex.y][uprightindex.x] == this.endValue)) {
|
||
neighbors.push(uprightindex);
|
||
}
|
||
}
|
||
|
||
return neighbors;
|
||
} else {
|
||
const _neighbors = this.neighborMap.get(current);
|
||
const neighbors: index[] = [];
|
||
for (const neighbor of _neighbors) {
|
||
if (this.map[neighbor.y][neighbor.x] == this.pathValue ||
|
||
this.map[neighbor.y][neighbor.x] == this.endValue) {
|
||
neighbors.push(neighbor);
|
||
}
|
||
}
|
||
return neighbors;
|
||
}
|
||
}
|
||
|
||
/**
|
||
* 计算从当前节点到邻居节点的实际成本
|
||
* @param current 当前节点
|
||
* @param neighbor 邻居节点
|
||
* @param type 距离计算类型
|
||
* @returns 返回从当前节点到邻居节点的成本
|
||
*/
|
||
private getGCost(current: index, neighbor: index, type: number = 0) {
|
||
let baseCost = 0;
|
||
|
||
// 计算基础距离成本
|
||
switch (type) {
|
||
case 0: {
|
||
// 计算曼哈顿距离
|
||
baseCost = Math.abs(current.x - neighbor.x) + Math.abs(current.y - neighbor.y);
|
||
break;
|
||
}
|
||
case 1: {
|
||
// 计算欧几里得距离
|
||
baseCost = Math.sqrt(Math.pow(current.x - neighbor.x, 2) + Math.pow(current.y - neighbor.y, 2));
|
||
break;
|
||
}
|
||
case 2: {
|
||
// 计算切比雪夫距离
|
||
const x = Math.abs(current.x - neighbor.x);
|
||
const y = Math.abs(current.y - neighbor.y);
|
||
const minxy = Math.min(x, y);
|
||
baseCost = x + y + (Math.sqrt(2) - 2) * minxy;
|
||
break;
|
||
}
|
||
}
|
||
|
||
// 如果存在权重地图，应用权重
|
||
if (this.weightMap && this.isValidIndex(neighbor)) {
|
||
const weight = this.weightMap[neighbor.y][neighbor.x];
|
||
return baseCost * weight;
|
||
}
|
||
|
||
return baseCost;
|
||
}
|
||
|
||
/**
|
||
* 根据给定的起始点和目标点，以及类型参数，计算启发式成本。
|
||
* @param start 起始点的索引，包含 x 和 y 坐标。
|
||
* @param end 目标点的索引，包含 x 和 y 坐标。
|
||
* @param type 计算成本的类型，0 表示曼哈顿距离，1 表示欧几里得距离，2 表示切比雪夫距离，默认为 0。
|
||
* @returns 返回根据指定类型计算出的启发式成本。
|
||
*/
|
||
private getHeuristicCost(start: index, end: index, type: number = 0) {
|
||
switch (type) {
|
||
case 0: {
|
||
// 计算曼哈顿距离
|
||
return Math.abs(start.x - end.x) + Math.abs(start.y - end.y);
|
||
}
|
||
case 1: {
|
||
// 计算欧几里得距离
|
||
return Math.sqrt(Math.pow(start.x - end.x, 2) + Math.pow(start.y - end.y, 2));
|
||
}
|
||
case 2: {
|
||
// 计算切比雪夫距离
|
||
const x = Math.abs(start.x - end.x);
|
||
const y = Math.abs(start.y - end.y);
|
||
const minxy = Math.min(x, y);
|
||
return x + y + (Math.sqrt(2) - 2) * minxy;
|
||
}
|
||
}
|
||
}
|
||
|
||
/**
|
||
* 检查节点是否在封闭列表中。
|
||
* @param node 节点坐标
|
||
* @returns {boolean} 如果节点在封闭列表中返回true，否则返回false
|
||
*/
|
||
private isInClosedList(node: index): boolean {
|
||
// 遍历封闭列表查找节点
|
||
let _index = -1;
|
||
for (let i = 0; i < this.closelist.length; i++) {
|
||
if (this.closelist[i].x == node.x && this.closelist[i].y == node.y) {
|
||
_index = i;
|
||
break;
|
||
}
|
||
}
|
||
return _index != -1;
|
||
}
|
||
|
||
/**
|
||
* 检查节点是否在开放列表中。
|
||
* @param node 节点坐标
|
||
* @returns {boolean} 如果节点在开放列表中返回true，否则返回false
|
||
*/
|
||
private isInOpenList(node: index): boolean {
|
||
// 遍历开放列表查找节点
|
||
let _index = -1;
|
||
for (let i = 0; i < this.openlist.length; i++) {
|
||
if (this.openlist[i].x == node.x && this.openlist[i].y == node.y) {
|
||
_index = i;
|
||
break;
|
||
}
|
||
}
|
||
return _index != -1;
|
||
}
|
||
|
||
/**
|
||
* 获取节点的成本。
|
||
* @param node 节点坐标
|
||
* @returns 节点的总成本
|
||
*/
|
||
private getCost(node: index): number {
|
||
let gcost = 0;
|
||
let hcost = 0;
|
||
this.gcostMap.forEach((value, key) => {
|
||
if (key.x == node.x && key.y == node.y) {
|
||
gcost = value;
|
||
}
|
||
});
|
||
this.hcostMap.forEach((value, key) => {
|
||
if (key.x == node.x && key.y == node.y) {
|
||
hcost = value;
|
||
}
|
||
});
|
||
return gcost + hcost;
|
||
}
|
||
|
||
/**
|
||
* 获取开放列表中成本最小的节点。
|
||
* @param list 开放列表
|
||
* @returns 成本最小的节点
|
||
*/
|
||
private getMinCostNode(list: index[]): index {
|
||
let _minindex = -1;
|
||
let _mincost = Number.MAX_SAFE_INTEGER;
|
||
// 寻找成本最小的节点
|
||
for (let i = 0; i < list.length; i++) {
|
||
const cost = this.getCost(list[i]);
|
||
if (cost < _mincost) {
|
||
_minindex = i;
|
||
_mincost = cost;
|
||
}
|
||
}
|
||
return list[_minindex];
|
||
}
|
||
|
||
/**
|
||
* 更新节点的成本和父节点信息。
|
||
* @param node 节点坐标
|
||
* @param gcost 从起点到当前节点的实际成本
|
||
* @param hcost 从当前节点到终点的估算成本
|
||
*/
|
||
private updateCost(node: index, gcost: number, hcost: number) {
|
||
this.gcostMap.set(node, gcost);
|
||
this.hcostMap.set(node, hcost);
|
||
}
|
||
|
||
/**
|
||
* 更新节点的父节点。
|
||
* @param node 节点坐标
|
||
* @param parent 父节点坐标
|
||
*/
|
||
private updateParent(node: index, parent: index) {
|
||
const existingparent = this.parentMap.get(node);
|
||
// 仅当新的父节点成本更低时更新
|
||
if (!existingparent || this.getCost(parent) < this.getCost(existingparent)) {
|
||
this.parentMap.set(node, parent);
|
||
}
|
||
}
|
||
|
||
/**
|
||
* 根据父节点映射重构路径。
|
||
* @param endPoint 终点坐标
|
||
* @returns 从起点到终点的路径
|
||
*/
|
||
private reconstructPath(endPoint: index) {
|
||
const path = [endPoint];
|
||
let currentnode = endPoint;
|
||
|
||
// 逆向回溯路径
|
||
while (currentnode) {
|
||
let parent = null;
|
||
this.parentMap.forEach((value, key) => {
|
||
if (currentnode.x == key.x && currentnode.y == key.y) {
|
||
parent = value;
|
||
}
|
||
})
|
||
if (parent) {
|
||
path.unshift(parent);
|
||
currentnode = parent;
|
||
} else {
|
||
currentnode = null;
|
||
}
|
||
}
|
||
|
||
return path;
|
||
}
|
||
|
||
|
||
/**
|
||
* 检查给定的索引是否为有效索引。
|
||
* @param index 一个包含x和y属性的对象，代表要检查的索引位置。
|
||
* @returns 返回一个布尔值，如果索引位置有效，则为true；否则为false。
|
||
*/
|
||
private isValidIndex(index: index): boolean {
|
||
return index.x >= 0 && index.x < this.map[0].length && index.y >= 0 && index.y < this.map.length;
|
||
}
|
||
|
||
/**
|
||
* 判断当前节点是否到达了目标节点。
|
||
* @param node 一个包含x和y属性的对象，代表当前节点的位置。
|
||
* @param end 一个包含x和y属性的对象，代表目标节点的位置。
|
||
* @returns 返回一个布尔值，如果当前节点已到达目标节点，则为true；否则为false。
|
||
*/
|
||
private isArrived(node: index, end: index) {
|
||
// 比较当前节点和目标节点的坐标，判断是否已经到达目标位置
|
||
return node.x == end.x && node.y == end.y;
|
||
}
|
||
}
|
||
|