A*寻路算法 根据png图片透明区域与障碍物区域寻路算法

由 夕空 撰写于  2024年5月14日
<!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 } ));




声明:星耀夕空|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - A*寻路算法 根据png图片透明区域与障碍物区域寻路算法


欢迎光顾我的小站!