3
爲了幫助這個問題成爲應答者的觀衆，我會注意到這個問題似乎是在跳躍的對角線情況。這種方法在遞歸運行時會導致放緩嗎？
編輯結束。
在我開發的XNA遊戲中，我使用A * + JPS算法在每個幀的均勻方格上導航。我瞭解了JPS here和here。但是，當我運行遊戲時，幀速率下降。幀頻非常低，使得遊戲無法播放。刪除對跳轉點的搜索「跳轉」，然後使用常規A *進行修改，以解決足夠大的方形尺寸問題。根據文章，JPS應該比普通的A *更有效率。減速的原因似乎是在「對角線案例」（跳轉方法的第15-29行）中對Jump的兩個要求。
顯然，在我的實現中一定有什麼錯誤/效率低下。但是它是什麼？
代碼：
跳轉方法是JPS遞歸跳轉功能的實現。
public Vector2? Jump(Vector2 current, Vector2 direction, Vector2 start, Vector2 end)
{
// Position of new node we are going to consider:
Vector2 next = current + direction * SquareSize;
// If it's blocked we can't jump here
if (IsBlocked(next))
return null;
// If the node is the goal return it
if (next.X == end.X && next.Y == end.Y)
return next;
// Diagonal Case
if (direction.X != 0 && direction.Y != 0)
{
Vector2 horizontalBehind = current - new Vector2(direction.X * SquareSize, 0);
Vector2 verticalBehind = current - new Vector2(0, direction.Y * SquareSize);
if (IsBlocked(horizontalBehind) || IsBlocked(verticalBehind))
{
return current;
}
// Check in horizontal and vertical directions for forced neighbors
// This is a special case for diagonal direction
if (Jump(next, new Vector2(direction.X, 0), start, end) != null || Jump(next, new Vector2(0, direction.Y), start, end) != null)
{
return current;
}
}
else
{
// Horizontal case
if (direction.X != 0)
{
Vector2 topBehind = current - new Vector2(direction.X * SquareSize, SquareSize);
Vector2 above = current - new Vector2(0, SquareSize);
Vector2 bottomBehind = current + new Vector2(-direction.X * SquareSize, SquareSize);
Vector2 below = current + new Vector2(0, SquareSize);
if (IsBlocked(topBehind) || IsBlocked(above) || IsBlocked(bottomBehind) || IsBlocked(below))
{
return current;
}
}
else
{
Vector2 leftBehind = current - new Vector2(SquareSize, direction.Y * SquareSize);
Vector2 left = current - new Vector2(SquareSize, 0);
Vector2 rightBehind = current + new Vector2(-SquareSize, direction.Y * SquareSize);
Vector2 right = current - new Vector2(SquareSize, 0);
if (IsBlocked(leftBehind) || IsBlocked(left) || IsBlocked(rightBehind) || IsBlocked(right))
{
return current;
}
}
}
// If forced neighbor was not found try next jump point
return Jump(next, direction, start, end);
}
#endregion
}
Navigate是實現A *的方法，從'start'參數到'end'參數。
PriorityQueue是基於this article的通用實現。它的Enqueue和Dequeue方法具有O（log2（n））複雜性。
public Vector2? Navigate(Vector2 start, Vector2 end)
{
PriorityQueue<float, Vector2> openSet = new PriorityQueue<float, Vector2>();
List<Vector2> closedSet = new List<Vector2>(10);
Dictionary<Vector2, Vector2> cameFrom = new Dictionary<Vector2, Vector2>(10);
Dictionary<Vector2, float> gScores = new Dictionary<Vector2, float>(10);
gScores[start] = 0;
openSet.Enqueue(H(start, end), start);
while (openSet.Count != 0)
{
Vector2 current = openSet.Dequeue().Value;
if (WorldMap.InSquare(current) == WorldMap.InSquare(end))
return ReconstructPath(cameFrom, current, start);
List<Vector2> neighbours = WorldMap.GetNeighbours(current, start, end);
closedSet.Add(current);
foreach(Vector2 neighbour in neighbours)
{
if (closedSet.Contains(neighbour))
continue;
float tenativeGScore = gScores[current] + Vector2.Distance(current, neighbour);
if(!gScores.ContainsKey(neighbour) || gScores[neighbour] > tenativeGScore)//Discover a new node || Find a better path to a node
{
cameFrom[neighbour] = current;
gScores[neighbour] = tenativeGScore;
float fScore = tenativeGScore + H(neighbour, end);//Calculate F.
openSet.Enqueue(fScore, neighbour);
}
}
}
return null;
}
GetNeighbours是一種返回節點'向量'的鄰居的方法。 A *版本：
public List<Vector2> GetNeighbours(Vector2 point, Vector2 start, Vector2 end)
{
Vector2[] directions = new Vector2[8];
List<Vector2> neighbours = new List<Vector2>(8);
directions[0] = Vector2.UnitX;//right
directions[1] = -Vector2.UnitX;//left
directions[2] = Vector2.UnitY;//down
directions[3] = -Vector2.UnitY;//up
directions[4] = Vector2.UnitX + Vector2.UnitY;//down right
directions[5] = -Vector2.UnitX + Vector2.UnitY;//down left
directions[6] = Vector2.UnitX - Vector2.UnitY;//up right
directions[7] = -Vector2.UnitX - Vector2.UnitY;//up left
foreach(Vector2 direction in directions)
{
Vector2 neighbour = point + direction * SquareSize;
if (!IsBlocked(neighbour))
neighbours.Add(neighbour);
}
return neighbours;
}
跳轉點搜索版本：
public List<Vector2> GetNeighbours(Vector2 point, Vector2 start, Vector2 end)
{
Vector2[] directions = new Vector2[8];
List<Vector2> neighbours = new List<Vector2>(8);
directions[0] = Vector2.UnitX;//right
directions[1] = -Vector2.UnitX;//left
directions[2] = Vector2.UnitY;//down
directions[3] = -Vector2.UnitY;//up
directions[4] = Vector2.UnitX + Vector2.UnitY;//down right
directions[5] = -Vector2.UnitX + Vector2.UnitY;//down left
directions[6] = Vector2.UnitX - Vector2.UnitY;//up right
directions[7] = -Vector2.UnitX - Vector2.UnitY;//up left
foreach(Vector2 direction in directions)
{
//The only difference between this GetNeighbours and the other one
//is that this one calls Jump here.
Vector2? jp = Jump(point + direction * SquareSize, direction, start, end);
if (jp != null)
neighbours.Add((Vector2)jp);
}
return neighbours;
}
InSqaure是返回表示正方形一個Vector2處於Vector2的方法，具有O（1）的複雜性。
IsBlocked是一個檢查Vector2是否在地圖內部的方法，也是一個被阻擋的方塊（「阻塞」表示一個有障礙的方塊）。它具有O（log2（n））的複雜性。
附加信息：
- 我目前只在有目標和起點之間沒有障礙物的情況下選中此。這意味着JPS算法只擴展1平方。同時，當找到（100,100）到（-800，-580）之間的距離時，規則A *擴展8以找到從（100,100）到（0,0）但是2325個方塊的路徑。在最後一種情況下，有一個明顯的幀率下降，使遊戲幾乎無法播放。
- 幀率被解鎖。
- 沒有在電網沒有明顯的口吃少於約1200平方，遊戲中有輕微的，可接受的幀速率，如果有需要任何更多的信息，我公司將提供它高興地降幅達約1600
，
在此先感謝！
中找到所有項目，您可以添加示例代碼以便更好地理解 –