<!DOCTYPE html>
<html lang="zh-cn">
<head>
<meta name="viewport" content="user-scalable=no, width=device-width, initial-scale=1.0">
<meta name="apple-mobile-web-app-capable" content="yes" />
<meta charset="UTF-8">
<title>A*寻路算法</title>
<style>
.map{position: relative;}
canvas{position: absolute;left: 0;top: 0;}
</style>
</head>
<body>
A*寻路算法 根据png图片透明区域与障碍物区域寻路算法
<div class="map">
<canvas id="map"></canvas>
<canvas id="canvas"></canvas>
</div>
<script>
// A*寻路算法实现
function AStarFinder(map, start, end) {
// 开放列表
let openList = [];
// 关闭列表
let closeList = [];
// 地图行列数
let row = map[0].length;
let col = map.length;
// 方向数组，用于上下左右搜索
// let dir = [[0, 1], [1, 0], [0, -1], [-1, 0]];
// 八方向数组，上下左右以及四个对角线搜索
let dir = [[0,1],[1,0],[0,-1],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]];
// 初始化起始节点
let startNode = {
x: start[0],
y: start[1],
g: 0, // 从起点走到当前格子的成本
h: Math.abs(start[0] - end[0]) + Math.abs(start[1] - end[1]), // 当前格子到终点的预估成本
f: 0, // g + h
parent: null
};
// 将起始节点加入开放列表
openList.push(startNode);
// A*主循环
while (openList.length > 0) {
// 获取开放列表中F值最小的节点
let currentNode = openList[0];
for (let i = 1; i < openList.length; i++) {
if (openList[i].f < currentNode.f) {
currentNode = openList[i];
}
}
// 将当前节点从开放列表移除，加入关闭列表
let index = openList.indexOf(currentNode);
openList.splice(index, 1);
closeList.push(currentNode);
// 如果找到终点，返回路径
if (currentNode.x === end[0] && currentNode.y === end[1]) {
let path = [];
while (currentNode.parent) {
path.push(currentNode);
currentNode = currentNode.parent;
}
return path.reverse();
}
// 查找相邻节点
for (let i = 0; i < dir.length; i++) {
let newX = currentNode.x + dir[i][0];
let newY = currentNode.y + dir[i][1];
// 越界检查
if (newX < 0 || newX >= row || newY < 0 || newY >= col) {
continue;
}
// 如果是障碍物或已在关闭列表中，则跳过
if (map[newY][newX] === 1 || isInCloseList(newX, newY, closeList)) {
continue;
}
// 创建新节点
let newNode = {
x: newX,
y: newY,
g: currentNode.g + 1,
h: Math.abs(newX - end[0]) + Math.abs(newY - end[1]),
f: currentNode.g + currentNode.h,
parent: currentNode
};
// 如果新节点已在开放列表中，则更新F值
if (isInOpenList(newNode, openList)) {
continue;
} else {
openList.push(newNode);
}
}
}
// 如果没有找到路径，返回空数组
return [];
}
// 辅助函数：检查节点是否在关闭列表中
function isInCloseList(x, y, list) {
for (let i = 0; i < list.length; i++) {
if (list[i].x === x && list[i].y === y) {
return true;
}
}
return false;
}
// 辅助函数：检查节点是否在开放列表中
function isInOpenList(node, list) {
for (let i = 0; i < list.length; i++) {
if (list[i].x === node.x && list[i].y === node.y) {
return true;
}
}
return false;
}
// 加载图片并解析为地图数组，透明区域为可通过的区域值0，其他区域为障碍物值1
function loadAndParseImage(url) {
return new Promise((resolve, reject) => {
const image = new Image();
image.onload = () => {
const canvas = document.getElementById('map') || document.createElement('canvas');
const context = canvas.getContext('2d');
canvas.width = image.width;
canvas.height = image.height;
context.drawImage(image, 0, 0);
const imageData = context.getImageData(0, 0, image.width, image.height);
const map = [];
for (let y = 0; y < image.height; y++) {
map[y] = [];
for (let x = 0; x < image.width; x++) {
const index = (y * imageData.width + x) * 4;
const alpha = imageData.data[index + 3]; // 获取alpha通道的值
map[y][x] = alpha === 0 ? 0 : 1; // 如果alpha为0，表示透明，即可以通过
}
}
resolve(map);
};
image.onerror = reject;
image.src = url;
});
}
loadAndParseImage('map.png').then(map => {
const start = [0, 0]; // 起始点
const end = [map[0].length - 1, map.length - 1]; // 终点
let path = AStarFinder(map, start, end);
console.log("路径数据：", path);
// 在canvas上绘制路径
const canvas = document.getElementById('canvas');
canvas.width = map[0].length;
canvas.height = map.length;
const ctx = canvas.getContext('2d');
var _map = document.querySelector('.map');
_map.style.width = canvas.width + 'px';
_map.style.height = canvas.height + 'px';
for (let i = 0; i < path.length; i++) {
const x = path[i].x;
const y = path[i].y;
ctx.fillStyle = 'red';
ctx.fillRect(x, y, 1, 1);
}
});
</script>
</body>
</html>需要读取一张map.png图片，透明区域为可通过区域
有改变角色朝向的可参考此代码：
// 计算角度，预备会出现寻路目标的朝向需求
function toDegrees(a, b) {
let dx = b.x - a.x;
let dy = b.y - a.y;
// 计算角度，从正x轴到点B的角度，单位是弧度
let radians = Math.atan2(dy, dx);
// 将弧度转换为0到360度的角度
let deg = (radians * 180) / Math.PI;
// deg:如果需要角度在0到360之间，可以处理负数的情况
return { degrees: deg, deg: deg<0?deg+360:deg, radians }
}
console.log(toDegrees( { x: 0, y: 0 }, { x: 1, y: 1 } ));
Comments | NOTHING