unity 自动寻路算法

在Unity开发中，自动寻路算法是实现角色或物体自主移动到目标位置的关键技术。本文将介绍两种基于A*算法的JavaScript实现，一种是使用列表的基础实现，另一种是使用二进制堆的优化实现。

基础实现：使用列表

以下是一个使用列表的A*算法基础实现代码：

var astar = {
init: function(grid) {
for (var x = 0; x < grid.length; x++) {
for (var y = 0; y < grid[x].length; y++) {
grid[x][y].f = 0;
grid[x][y].g = 0;
grid[x][y].h = 0;
grid[x][y].debug = "";
grid[x][y].parent = null;
}
}
},
search: function(grid, start, end) {
astar.init(grid);
var openList = [];
var closedList = [];
openList.push(start);

while (openList.length > 0) {
// 选择f值最小的节点进行处理
var lowInd = 0;
for (var i = 0; i < openList.length; i++) {
if (openList[i].f < openList[lowInd].f) {
lowInd = i;
}
}
var currentNode = openList[lowInd];

// 找到目标节点，返回路径
if (currentNode.pos == end.pos) {
var curr = currentNode;
var ret = [];
while (curr.parent) {
ret.push(curr);
curr = curr.parent;
}
return ret.reverse();
}

// 将当前节点从开放列表移到关闭列表，并处理其邻居节点
openList.splice(openList.indexOf(currentNode), 1);
closedList.push(currentNode);
var neighbors = astar.neighbors(grid, currentNode);

for (var i = 0; i < neighbors.length; i++) {
var neighbor = neighbors[i];
if (closedList.includes(neighbor) || neighbor.isWall()) {
// 无效节点，跳过
continue;
}

// 计算g值，即从起点到当前节点的最短距离
var gScore = currentNode.g + 1;
var gScoreIsBest = false;

if (!openList.includes(neighbor)) {
// 首次到达该节点，认为是最佳路径
gScoreIsBest = true;
neighbor.h = astar.heuristic(neighbor.pos, end.pos);
openList.push(neighbor);
} else if (gScore < neighbor.g) {
// 之前已访问过，但此次路径更优
gScoreIsBest = true;
}

if (gScoreIsBest) {
// 更新节点信息
neighbor.parent = currentNode;
neighbor.g = gScore;
neighbor.f = neighbor.g + neighbor.h;
neighbor.debug = "F: " + neighbor.f + "<br />G: " + neighbor.g + "<br />H: " + neighbor.h;
}
}
}

// 未找到路径，返回空数组
return [];
},
heuristic: function(pos0, pos1) {
// 曼哈顿距离
var d1 = Math.abs(pos1.x - pos0.x);
var d2 = Math.abs(pos1.y - pos0.y);
return d1 + d2;
},
neighbors: function(grid, node) {
var ret = [];
var x = node.pos.x;
var y = node.pos.y;

if (grid[x - 1] && grid[x - 1][y]) {
ret.push(grid[x - 1][y]);
}
if (grid[x + 1] && grid[x + 1][y]) {
ret.push(grid[x + 1][y]);
}
if (grid[x][y - 1]) {
ret.push(grid[x][y - 1]);
}
if (grid[x][y + 1]) {
ret.push(grid[x][y + 1]);
}
return ret;
}
};

代码解释

1. init函数：初始化网格中每个节点的f、g、h值，debug信息和parent节点。
2. search函数：实现A*算法的核心逻辑，包括开放列表和关闭列表的管理，节点的选择和路径的回溯。
3. heuristic函数：计算两个节点之间的曼哈顿距离，作为启发式函数。
4. neighbors函数：获取当前节点的相邻节点。

优化实现：使用二进制堆

以下是一个使用二进制堆的A*算法优化实现代码，该实现速度更快，并且支持对角搜索（8方向运动）：

var astar = {
init: function(grid) {
for (var x = 0, xl = grid.length; x < xl; x++) {
for (var y = 0, yl = grid[x].length; y < yl; y++) {
var node = grid[x][y];
node.f = 0;
node.g = 0;
node.h = 0;
node.cost = 1;
node.visited = false;
node.closed = false;
node.parent = null;
}
}
},
heap: function() {
return new BinaryHeap(function(node) {
return node.f;
});
},
search: function(grid, start, end, diagonal, heuristic) {
astar.init(grid);
heuristic = heuristic || astar.manhattan;
diagonal = !!diagonal;

var openHeap = astar.heap();
openHeap.push(start);

while (openHeap.size() > 0) {
// 选择f值最小的节点进行处理
var currentNode = openHeap.pop();

// 找到目标节点，返回路径
if (currentNode === end) {
var curr = currentNode;
var ret = [];
while (curr.parent) {
ret.push(curr);
curr = curr.parent;
}
return ret.reverse();
}

// 将当前节点标记为已关闭
currentNode.closed = true;

// 获取当前节点的邻居节点
var neighbors = astar.neighbors(grid, currentNode, diagonal);

for (var i = 0, il = neighbors.length; i < il; i++) {
var neighbor = neighbors[i];

if (neighbor.closed || neighbor.isWall()) {
// 无效节点，跳过
continue;
}

// 计算g值，即从起点到当前节点的最短距离
var gScore = currentNode.g + neighbor.cost;
var beenVisited = neighbor.visited;

if (!beenVisited || gScore < neighbor.g) {
// 找到更优路径，更新节点信息
neighbor.visited = true;
neighbor.parent = currentNode;
neighbor.h = neighbor.h || heuristic(neighbor.pos, end.pos);
neighbor.g = gScore;
neighbor.f = neighbor.g + neighbor.h;

if (!beenVisited) {
// 首次访问该节点，加入开放堆
openHeap.push(neighbor);
} else {
// 已访问过，重新排序堆
openHeap.rescoreElement(neighbor);
}
}
}
}

// 未找到路径，返回空数组
return [];
},
manhattan: function(pos0, pos1) {
// 曼哈顿距离
var d1 = Math.abs(pos1.x - pos0.x);
var d2 = Math.abs(pos1.y - pos0.y);
return d1 + d2;
},
neighbors: function(grid, node, diagonals) {
var ret = [];
var x = node.x;
var y = node.y;

// 水平和垂直方向的邻居节点
if (grid[x - 1] && grid[x - 1][y]) {
ret.push(grid[x - 1][y]);
}
if (grid[x + 1] && grid[x + 1][y]) {
ret.push(grid[x + 1][y]);
}
if (grid[x][y - 1]) {
ret.push(grid[x][y - 1]);
}
if (grid[x][y + 1]) {
ret.push(grid[x][y + 1]);
}

if (diagonals) {
// 对角方向的邻居节点
if (grid[x - 1] && grid[x - 1][y - 1]) {
ret.push(grid[x - 1][y - 1]);
}
if (grid[x + 1] && grid[x + 1][y - 1]) {
ret.push(grid[x + 1][y - 1]);
}
if (grid[x - 1] && grid[x - 1][y + 1]) {
ret.push(grid[x - 1][y + 1]);
}
if (grid[x + 1] && grid[x + 1][y + 1]) {
ret.push(grid[x + 1][y + 1]);
}
}

return ret;
}
};

代码解释

1. init函数：初始化网格中每个节点的f、g、h值，cost、visited、closed状态和parent节点。
2. heap函数：创建一个二进制堆，用于管理开放列表。
3. search函数：使用二进制堆优化节点选择过程，提高算法效率。支持对角搜索，可以通过diagonal参数控制。
4. manhattan函数：计算两个节点之间的曼哈顿距离，作为启发式函数。
5. neighbors函数：获取当前节点的相邻节点，支持对角搜索。

总结

使用二进制堆的优化实现可以显著提高A*算法的性能，尤其是在处理大规模网格时。同时，支持对角搜索可以让角色或物体在地图上进行更灵活的移动。你可以访问图搜索项目页面获取最新的代码版本。