用javaScript实现A*算法
时间: 2023-07-10 19:23:35 浏览: 51
好的,以下是用JavaScript实现A*算法的代码:
```javascript
// 定义一个节点类
class Node {
constructor(x, y) {
this.x = x;
this.y = y;
this.f = 0;
this.g = 0;
this.h = 0;
this.parent = null;
}
}
// 创建地图
let map = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]
];
// 定义起点和终点
let start = new Node(0, 0);
let end = new Node(9, 8);
// 定义open列表和close列表
let openList = [];
let closeList = [];
// 判断节点是否在close列表中
function isInCloseList(x, y) {
for (let i = 0; i < closeList.length; i++) {
if (closeList[i].x == x && closeList[i].y == y) {
return true;
}
}
return false;
}
// 判断节点是否在open列表中
function isInOpenList(x, y) {
for (let i = 0; i < openList.length; i++) {
if (openList[i].x == x && openList[i].y == y) {
return true;
}
}
return false;
}
// 计算节点的f, g, h值
function countFGH(node, parent, end) {
node.g = parent.g + 1;
node.h = Math.abs(end.x - node.x) + Math.abs(end.y - node.y);
node.f = node.g + node.h;
node.parent = parent;
}
// 查找open列表中f值最小的节点
function findMinNode() {
let minF = openList[0].f;
let minIndex = 0;
for (let i = 1; i < openList.length; i++) {
if (openList[i].f < minF) {
minF = openList[i].f;
minIndex = i;
}
}
return minIndex;
}
// 查找路径
function findPath() {
openList.push(start);
while (openList.length > 0) {
let minIndex = findMinNode();
let currNode = openList[minIndex];
if (currNode.x == end.x && currNode.y == end.y) {
let path = [];
while (currNode) {
path.push(currNode);
currNode = currNode.parent;
}
return path.reverse();
}
openList.splice(minIndex, 1);
closeList.push(currNode);
// 寻找当前节点的邻居
let neighbors = [];
if (currNode.x > 0) {
neighbors.push(new Node(currNode.x - 1, currNode.y));
}
if (currNode.y > 0) {
neighbors.push(new Node(currNode.x, currNode.y - 1));
}
if (currNode.x < map.length - 1) {
neighbors.push(new Node(currNode.x + 1, currNode.y));
}
if (currNode.y < map[0].length - 1) {
neighbors.push(new Node(currNode.x, currNode.y + 1));
}
for (let i = 0; i < neighbors.length; i++) {
let neighbor = neighbors[i];
if (!isInCloseList(neighbor.x, neighbor.y)) {
if (isInOpenList(neighbor.x, neighbor.y)) {
let index = openList.findIndex((item) => item.x == neighbor.x && item.y == neighbor.y);
let node = openList[index];
if (node.g > currNode.g + 1) {
countFGH(node, currNode, end);
}
} else {
countFGH(neighbor, currNode, end);
openList.push(neighbor);
}
}
}
}
return null;
}
// 测试
let path = findPath();
console.log(path);
```
上面的代码实现了一个简单的寻路算法,通过传入地图、起点和终点,返回一条从起点到终点的最短路径。