我正在尝试实现 Jump Point Search，这是对 A* 的优化，可将打开列表中的节点数量平均减少 20 倍，以及内存消耗。该算法是根据原始研究论文和一些在线教程实现的，但是程序在搜索自然邻居和强制邻居时进入了无限递归循环，导致堆栈溢出。寻路 A* 已经在工作，我只是在其中添加 JPS 函数。
以下是这些功能的代码：
void Movement::GetNaturalNeighbors(std::vector<Node>& output, Node& currentNode)
{
int nextX = currentNode.pos.x + currentNode.direction.x;
int nextY = currentNode.pos.y + currentNode.direction.y;
// Straight line pruning excludes all neighbors except the one directly in front of currentNode
if(!g_terrain.IsWall(nextX, nextY))
{
Map[nextX][nextY].parent = &Map[currentNode.pos.x][currentNode.pos.y];
Map[nextX][nextY].direction.x = Map[nextX][nextY].parent->direction.x;
Map[nextX][nextY].direction.y = Map[nextX][nextY].parent->direction.y;
Map[nextX][nextY].heurCost = GetHeuristicCost(nextX, nextY);
// Movement cost for diagonals is square root of 2
Map[nextX][nextY].movCost = currentNode.movCost + 1.0f;
Map[nextX][nextY].pos.x = nextX;
Map[nextX][nextY].pos.y = nextY;
if ((Map[nextX][nextY].movCost + Map[nextX][nextY].heurCost) < (currentNode.movCost + currentNode.heurCost))
{
output.push_back(Map[nextX][nextY]);
}
}
int dirX = currentNode.direction.x;
int dirY = currentNode.direction.y;
// If we are moving diagonally, add the adjacent nodes in the same direction
if(dirX!= 0 && dirY!=0)
{
if((dirY == +1) &&(!g_terrain.IsWall(currentNode.pos.x+ neighborX[TOP], currentNode.pos.y+ neighborY[TOP])))
{
int naturalNeighborX = currentNode.pos.x+ neighborX[TOP];
int naturalNeighborY = currentNode.pos.y+ neighborY[TOP];
Map[naturalNeighborX][naturalNeighborY].direction.x = neighborX[TOP];
Map[naturalNeighborX][naturalNeighborY].direction.y = neighborY[TOP];
Map[naturalNeighborX][naturalNeighborY].parent = &Map[currentNode.pos.x][currentNode.pos.y];
Map[naturalNeighborX][naturalNeighborY].heurCost = GetHeuristicCost(nextX, nextY);
// Movement cost for diagonals is square root of 2
Map[naturalNeighborX][naturalNeighborY].movCost = currentNode.movCost + 1.41421f;
Map[naturalNeighborX][naturalNeighborY].pos.x = naturalNeighborX;
Map[naturalNeighborX][naturalNeighborY].pos.y = naturalNeighborY;
if ((Map[naturalNeighborX][naturalNeighborY].movCost + Map[naturalNeighborX][naturalNeighborY].heurCost) < (currentNode.movCost + currentNode.heurCost))
{
output.push_back(Map[naturalNeighborX][naturalNeighborY]);
}
}
else if(!g_terrain.IsWall(currentNode.pos.x+ neighborX[BOTTOM], currentNode.pos.y+ neighborY[BOTTOM]))
{
int naturalNeighborX = currentNode.pos.x+ neighborX[BOTTOM];
int naturalNeighborY = currentNode.pos.y+ neighborY[BOTTOM];
Map[naturalNeighborX][naturalNeighborY].direction.x = neighborX[BOTTOM];
Map[naturalNeighborX][naturalNeighborY].direction.y = neighborY[BOTTOM];
Map[naturalNeighborX][naturalNeighborY].parent = &Map[currentNode.pos.x][currentNode.pos.y];
Map[naturalNeighborX][naturalNeighborY].heurCost = GetHeuristicCost(nextX, nextY);
// Movement cost for diagonals is square root of 2m
Map[naturalNeighborX][naturalNeighborY].movCost = currentNode.movCost + 1.41421f;
Map[naturalNeighborX][naturalNeighborY].pos.x = nextX;
Map[naturalNeighborX][naturalNeighborY].pos.y = nextY;
if ((Map[naturalNeighborX][naturalNeighborY].movCost + Map[naturalNeighborX][naturalNeighborY].heurCost) < (currentNode.movCost + currentNode.heurCost))
{
output.push_back(Map[naturalNeighborX][naturalNeighborY]);
}
}
if((dirX == +1) && (!g_terrain.IsWall(currentNode.pos.x+ neighborX[RIGHT], currentNode.pos.y+ neighborY[RIGHT])))
{
int naturalNeighborX = currentNode.pos.x+ neighborX[RIGHT];
int naturalNeighborY = currentNode.pos.y+ neighborY[RIGHT];
Map[naturalNeighborX][naturalNeighborY].direction.x = neighborX[RIGHT];
Map[naturalNeighborX][naturalNeighborY].direction.y = neighborY[RIGHT];
Map[naturalNeighborX][naturalNeighborY].parent = &Map[currentNode.pos.x][currentNode.pos.y];
Map[naturalNeighborX][naturalNeighborY].heurCost = GetHeuristicCost(nextX, nextY);
// Movement cost for diagonals is square root of 2
Map[naturalNeighborX][naturalNeighborY].movCost = currentNode.movCost + 1.41421f;
Map[naturalNeighborX][naturalNeighborY].pos.x = naturalNeighborX;
Map[naturalNeighborX][naturalNeighborY].pos.y = naturalNeighborY;
if ((Map[naturalNeighborX][naturalNeighborY].movCost + Map[naturalNeighborX][naturalNeighborY].heurCost) < (currentNode.movCost + currentNode.heurCost))
{
output.push_back(Map[naturalNeighborX][naturalNeighborY]);
}
}
else if(!g_terrain.IsWall(currentNode.pos.x+ neighborX[LEFT], currentNode.pos.y+ neighborY[LEFT]))
{
int naturalNeighborX = currentNode.pos.x+ neighborX[LEFT];
int naturalNeighborY = currentNode.pos.y+ neighborY[LEFT];
Map[naturalNeighborX][naturalNeighborX].direction.x = neighborX[LEFT];
Map[naturalNeighborX][naturalNeighborX].direction.y = neighborX[LEFT];
Map[naturalNeighborX][naturalNeighborX].parent = &Map[currentNode.pos.x][currentNode.pos.y];
Map[naturalNeighborX][naturalNeighborX].heurCost = GetHeuristicCost(nextX, nextY);
// Movement cost for diagonals is square root of 2
Map[naturalNeighborX][naturalNeighborY].movCost = currentNode.movCost + 1.41421f;
Map[naturalNeighborX][naturalNeighborY].pos.x = nextX;
Map[naturalNeighborX][naturalNeighborY].pos.y = nextY;
if ((Map[naturalNeighborX][naturalNeighborY].movCost + Map[naturalNeighborX][naturalNeighborY].heurCost) < (currentNode.movCost + currentNode.heurCost))
{
output.push_back(Map[naturalNeighborX][naturalNeighborY]);
}
}
}
}
void Movement::GetForcedNeighbors(std::vector<Node>& output, Node& currentNode)
{
int dir_x = currentNode.direction.x;
int dir_y = currentNode.direction.y;
int nextNodeX = currentNode.pos.x + dir_x;
int nextNodeY = currentNode.pos.y + dir_y;
// Forced neighbors only exist for diagonal moves
if((dir_x != 0) && (dir_y != 0))
{
// Check for diagonal forced neighbors
if(dir_x == +1)
{
// Does the top right diagonal have any forced neighbors ?
if(g_terrain.IsWall(nextNodeX + neighborX[TOP_RIGHT], nextNodeY + neighborY[TOP_RIGHT]) && !g_terrain.IsWall(nextNodeX + neighborX[TOP], nextNodeY + neighborY[TOP]))
{
Map[nextNodeX][nextNodeY].direction.x = neighborX[TOP];
Map[nextNodeX][nextNodeY].direction.y = neighborY[TOP];
Map[nextNodeX][nextNodeY].parent = &Map[currentNode.pos.x][currentNode.pos.y];
Map[nextNodeX][nextNodeY].heurCost = GetHeuristicCost(nextNodeX, nextNodeY);
// Movement cost for diagonals is square root of 2
Map[nextNodeX][nextNodeY].movCost = currentNode.movCost + 1.41421f;
Map[nextNodeX][nextNodeY].pos.x = nextNodeX;
Map[nextNodeX][nextNodeY].pos.y = nextNodeY;
if ((Map[nextNodeX][nextNodeY].movCost + Map[nextNodeX][nextNodeY].heurCost) < (currentNode.movCost + currentNode.heurCost))
{
output.push_back(Map[nextNodeX][nextNodeY]);
}
}
// Does the bottom right diagonal have any forced neighbors ?
if(g_terrain.IsWall(nextNodeX + neighborX[BOTTOM_RIGHT], nextNodeY + neighborY[BOTTOM_RIGHT]) && !g_terrain.IsWall(nextNodeX + neighborX[BOTTOM], nextNodeY + neighborY[BOTTOM]))
{
Map[nextNodeX][nextNodeY].direction.x = neighborX[BOTTOM];
Map[nextNodeX][nextNodeY].direction.y = neighborY[BOTTOM];
Map[nextNodeX][nextNodeY].parent = &Map[currentNode.pos.x][currentNode.pos.y];
Map[nextNodeX][nextNodeY].heurCost = GetHeuristicCost(nextNodeX, nextNodeY);
// Movement cost for diagonals is square root of 2
Map[nextNodeX][nextNodeY].movCost = currentNode.movCost + 1.41421f;
Map[nextNodeX][nextNodeY].pos.x = nextNodeX;
Map[nextNodeX][nextNodeY].pos.y = nextNodeY;
output.push_back(Map[nextNodeX][nextNodeY]);
}
}
if(dir_x == -1)
{
// Does the top left diagonal have any forced neighbors ?
if(g_terrain.IsWall(nextNodeX + neighborX[TOP_LEFT], nextNodeY + neighborY[TOP_LEFT]) && !g_terrain.IsWall(nextNodeX + neighborX[TOP], nextNodeY + neighborY[TOP]))
{
Map[nextNodeX][nextNodeY].direction.x = neighborX[TOP];
Map[nextNodeX][nextNodeY].direction.y = neighborY[TOP];
Map[nextNodeX][nextNodeY].parent = &Map[currentNode.pos.x][currentNode.pos.y];
Map[nextNodeX][nextNodeY].heurCost = GetHeuristicCost(nextNodeX, nextNodeY);
// Movement cost for diagonals is square root of 2
Map[nextNodeX][nextNodeY].movCost = ((dir_x == 0) || (dir_y == 0))? currentNode.movCost + 1.0f: currentNode.movCost + 1.41421f;
Map[nextNodeX][nextNodeY].pos.x = nextNodeX;
Map[nextNodeX][nextNodeY].pos.y = nextNodeY;
output.push_back(Map[nextNodeX][nextNodeY]);
}
// Does the bottom left diagonal have any forced neighbors ?
if(g_terrain.IsWall(nextNodeX + neighborX[BOTTOM_LEFT], nextNodeY + neighborY[BOTTOM_LEFT]) && !g_terrain.IsWall(nextNodeX + neighborX[BOTTOM], nextNodeY + neighborY[BOTTOM]))
{
Map[nextNodeX][nextNodeY].direction.x = neighborX[BOTTOM];
Map[nextNodeX][nextNodeY].direction.y = neighborY[BOTTOM];
Map[nextNodeX][nextNodeY].parent = &Map[currentNode.pos.x][currentNode.pos.y];
Map[nextNodeX][nextNodeY].heurCost = GetHeuristicCost(nextNodeX, nextNodeY);
// Movement cost for diagonals is square root of 2
Map[nextNodeX][nextNodeY].movCost = ((dir_x == 0) || (dir_y == 0))? currentNode.movCost + 1.0f: currentNode.movCost + 1.41421f;
Map[nextNodeX][nextNodeY].pos.x = nextNodeX;
Map[nextNodeX][nextNodeY].pos.y = nextNodeY;
output.push_back(Map[nextNodeX][nextNodeY]);
}
}
}
}
其他一切都遵循原始文档的逻辑，但这两个功能是我不确定的唯一两个。创建者和许多教程都没有深入解释如何识别它们。
我的 A* 实现将世界信息存储在称为 Map 的 2D 矩阵中，而不是使用封闭列表。打开列表只是要打开哪些节点的向量。节点包含它们的 x 和 y 位置、启发式成本和移动成本（通常称为给定成本）以及玩家踩到瓷砖时所面对的方向。玩家只在 x 和 y 上移动。
我为文字墙道歉，但这是我的第一篇文章，我想发布尽可能多的相关信息。