私はジャンプ ポイント検索を実装しようとしています。これは、オープン リスト内のノード数を平均 20 倍削減する A* の最適化であり、メモリ消費量も同様です。このアルゴリズムは、元の研究論文といくつかのオンライン チュートリアルに従って実装されましたが、プログラムは自然近傍と強制近傍を検索するときに無限再帰ループに入り、スタック オーバーフローが発生します。Pathfinding 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]);
}
}
}
}
他のすべては元のドキュメントのロジックに従いますが、これら 2 つの関数だけが不明です。作成者も多くのチュートリアルも、それらを特定する方法について詳しく説明していません。
A* の私の実装では、閉じたリストを使用する代わりに、マップと呼ばれる 2D マトリックスにワールド情報を格納します。オープン リストは、オープンするノードの単なるベクトルです。ノードには、x と y の位置、ヒューリスティック コスト、移動コスト (より一般的には与えられたコストとして知られています)、プレイヤーがタイルを踏んだときに向いていた方向が含まれます。プレイヤーは x と y 方向にのみ移動します。
テキストの壁で申し訳ありませんが、これは私の最初の投稿であり、できるだけ多くの関連情報を投稿したかった.