请用js实现双向astar
时间: 2023-03-02 22:16:04 浏览: 50
双向A*算法是一种基于启发式搜索的路径规划算法,它从起点和终点同时开始搜索,直到它们相遇或者找到了一条最短路径。下面是一个使用 JavaScript 实现双向 A* 算法的示例代码:
```javascript
class PriorityQueue {
constructor() {
this.items = [];
}
enqueue(element, priority) {
let queueElement = { element, priority };
let added = false;
for (let i = 0; i < this.items.length; i++) {
if (queueElement.priority < this.items[i].priority) {
this.items.splice(i, 0, queueElement);
added = true;
break;
}
}
if (!added) {
this.items.push(queueElement);
}
}
dequeue() {
return this.items.shift();
}
isEmpty() {
return this.items.length === 0;
}
}
class Graph {
constructor() {
this.nodes = new Map();
}
addNode(id, x, y) {
this.nodes.set(id, { x, y, neighbors: new Map() });
}
addEdge(src, dest, weight) {
this.nodes.get(src).neighbors.set(dest, weight);
this.nodes.get(dest).neighbors.set(src, weight);
}
heuristic(a, b) {
return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}
astar(startId, endId) {
let startNode = this.nodes.get(startId);
let endNode = this.nodes.get(endId);
let openSetStart = new PriorityQueue();
let openSetEnd = new PriorityQueue();
let closedSetStart = new Set();
let closedSetEnd = new Set();
let cameFromStart = new Map();
let cameFromEnd = new Map();
let gScoreStart = new Map();
let gScoreEnd = new Map();
let fScoreStart = new Map();
let fScoreEnd = new Map();
gScoreStart.set(startNode, 0);
fScoreStart.set(startNode, this.heuristic(startNode, endNode));
openSetStart.enqueue(startNode, fScoreStart.get(startNode));
gScoreEnd.set(endNode, 0);
fScoreEnd.set(endNode, this.heuristic(startNode, endNode));
openSetEnd.enqueue(endNode, fScoreEnd.get(endNode));
while (!openSetStart.isEmpty() && !openSetEnd.isEmpty()) {
let currentStart = openSetStart.dequeue().element;
closedSetStart.add(currentStart);
let currentEnd = openSetEnd.dequeue().element;
closedSetEnd.add(currentEnd);
if (closedSetEnd.has(currentStart) || closedSetStart.has(currentEnd)) {
return this.reconstructPath(cameFromStart, cameFromEnd, currentStart, currentEnd);
}
for (let [neighborId, weight] of currentStart.neighbors) {
let neighbor = this.nodes.get(neighborId);
if (closedSetStart.has(neighbor)) {
continue;
}
let tentativeGScore = gScoreStart.get(currentStart) + weight;
if (!openSetStart.items.some((item) => item.element === neighbor)) {
openSetStart.enqueue(neighbor, Infinity);
}
if (tentativeGScore >= gScoreStart.get(neighbor)) {
continue;
}
cameFromStart.set(neighbor, currentStart);
gScoreStart.set(neighbor, tentativeG