算法
代码算法大约 3 分钟
A-Star寻路算法
也叫做A*算法，这是一种主流的用于网格平面搜索路径的算法，不仅效率高，而且代码也很少。直接上代码：index.js文件
// 定义节点类
class Node {
constructor(x, y) {
this.x = x;
this.y = y;
this.g = 0;
this.h = 0;
this.f = 0;
this.parent = null;
this.isObstacle = false;
}
}
// 定义Gard类
export class Gard {
constructor(rows, cols, enableDiagonal = false) {
this.rows = rows;
this.cols = cols;
this.enableDiagonal = enableDiagonal;
this.grid = [];
for (let i = 0; i < rows; i++) {
this.grid[i] = [];
for (let j = 0; j < cols; j++) {
this.grid[i][j] = new Node(i, j);
}
}
}
getNode(x, y) {
if (x < 0 || x >= this.rows || y < 0 || y >= this.cols) {
return null;
}
return this.grid[x][y];
}
// 设置障碍物
setObstacle(...arr) {
for (let i = 0; i < arr.length; i++) {
const [x, y] = arr[i];
if (x >= 0 && x < this.rows && y >= 0 && y < this.cols) {
this.grid[x][y].isObstacle = true;
}
}
}
// 判断是否为障碍物
isObstacle(x, y) {
return this.grid[x][y].isObstacle;
}
// 获取相邻节点
getNeighbors(node) {
let neighbors = [];
const x = node.x;
const y = node.y;
// 上下左右
if (x > 0) neighbors.push(this.grid[x - 1][y]);
if (x < this.rows - 1) neighbors.push(this.grid[x + 1][y]);
if (y > 0) neighbors.push(this.grid[x][y - 1]);
if (y < this.cols - 1) neighbors.push(this.grid[x][y + 1]);
// 对角线
if (this.enableDiagonal) {
if (x > 0 && y > 0) neighbors.push(this.grid[x - 1][y - 1]);
if (x > 0 && y < this.cols - 1) neighbors.push(this.grid[x - 1][y + 1]);
if (x < this.rows - 1 && y > 0) neighbors.push(this.grid[x + 1][y - 1]);
if (x < this.rows - 1 && y < this.cols - 1) neighbors.push(this.grid[x + 1][y + 1]);
}
return neighbors.filter(neighbor => !neighbor.isObstacle);
}
}
/**
* 定义AStar类
* @param {Gard} grid 网格
* @param {[number, number]} start 起点
* @param {[number, number]} end 终点
*/
export class AStar {
/**
*
* @param {Gard} grid
* @param {[number, number]} start
* @param {[number, number]} end
*/
constructor(grid, start, end) {
this.grid = grid;
this.start = grid.getNode(start[0], start[1]);
this.end = grid.getNode(end[0], end[1]);
}
// 计算启发函数（这里使用曼哈顿距离）
heuristic(node, end) {
return Math.abs(node.x - end.x) + Math.abs(node.y - end.y);
}
// A*算法
findPath() {
let openSet = [this.start];
let closedSet = [];
while (openSet.length > 0) {
let current = openSet[0];
for (let i = 1; i < openSet.length; i++) {
if (openSet[i].f < current.f) {
current = openSet[i];
}
}
if (current === this.end) {
let path = [];
let temp = current;
while (temp.parent) {
path.push([temp.x, temp.y]);
temp = temp.parent;
}
return path.reverse();
}
openSet = openSet.filter(node => node !== current);
closedSet.push(current);
let neighbors = this.grid.getNeighbors(current);
for (let neighbor of neighbors) {
if (!closedSet.includes(neighbor)) {
let tempG = current.g + 1;
if (!openSet.includes(neighbor) || tempG < neighbor.g) {
neighbor.g = tempG;
neighbor.h = this.heuristic(neighbor, this.end);
neighbor.f = neighbor.g + neighbor.h;
neighbor.parent = current;
if (!openSet.includes(neighbor)) {
openSet.push(neighbor);
}
}
}
}
}
return null; // 如果没有找到路径，则返回null
}
}
index.html文件
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Document</title>
</head>
<style>
.container {
display: flex;
}
.control {
margin: 20px;
}
#grid {
width: 500px;
height: 500px;
background-color: #fff;
/* border: 1px solid #000; */
display: flex;
flex-wrap: wrap;
}
#grid div {
border: 1px solid #000;
background-color: #fff;
}
#grid div.barrier {
background-color: #000;
}
#grid div.node {
background-color: #fff;
}
#grid div.start {
background-color: #0f0;
}
#grid div.end {
background-color: #f00;
}
</style>
<body>
<div class="container">
<div id="grid"></div>
<div class="control">
<button id="start">开始</button>
<button id="clear">清除</button>
</div>
</div>
<script type="module">
import { Gard, AStar } from "./index.js";
// 表格宽高
const rows = 8;
const cols = 8;
// 开始节点
const start = [1, 2];
// 结束节点
const end = [6, 6];
// 障碍物节点
const obstacle = [
[4, 2],
// [3, 4],
[3, 2],
[2, 5],
[3, 3]
];
const grid = new Gard(rows, cols, false);
grid.setObstacle(...obstacle);
const a_star = new AStar(grid, start, end);
// ul、li绘制网格
const grid_box = document.getElementById("grid");
for (let j = 0; j < grid.rows; j++) {
for (let i = 0; i < grid.cols; i++) {
const node = grid.getNode(i, j);
const div = document.createElement("div");
if (node.isObstacle) {
div.className = "barrier";
} else if (i === start[0] && j === start[1]) {
div.className = "start";
} else if (i === end[0] && j === end[1]) {
div.className = "end";
} else {
div.className = "node";
}
div.dataset.index = `${i}-${j}`;
div.style.width = `calc(100% / ${grid.cols} - 2px)`;
div.style.height = `calc(100% / ${grid.rows} - 1px)`;
grid_box.appendChild(div);
}
}
let timer = null;
document.getElementById("start").onclick = () => {
// 开始寻路
const path = a_star.findPath();
if (path) {
console.log("最短路径:", path);
// 绘制路径, 500毫秒
for (let i = 0; i < path.length; i++) {
// 绘制路径, 500毫秒绘制一次
timer = setTimeout(() => {
const [x, y] = path[i];
const div = document.querySelector(`[data-index="${x}-${y}"]`);
// 不是最后一个节点
if (i !== path.length - 1) {
div.style.backgroundColor = "#0dc";
}
}, 800 * (i + 1));
}
} else {
window.alert("没有找到路径");
}
};
document.getElementById("clear").onclick = () => {
// 清除路径
clearTimeout(timer);
const path = a_star.findPath();
if (path) {
for (let i = 0; i < path.length; i++) {
const [x, y] = path[i];
const div = document.querySelector(`[data-index="${x}-${y}"]`);
if (i !== path.length - 1) {
div.style.backgroundColor = "#fff";
}
}
}
};
</script>
</body>
</html>