上找到所有项目
编辑：
为了帮助这个问题的观众成为答案者，我会注意到问题似乎是在跳跃的对角线情况下。在该方法中，当递归运行时，可能会导致放缓？
编辑结束。
在我开发的XNA游戏中，我使用* JPS算法在每个帧中浏览均匀的方形网格。我在这里和这里了解了JPS。但是，当我运行游戏时，帧速率下降。帧速率太低，以至于使游戏无法玩。将呼叫呼叫"跳跃"跳跃"，然后使用常规a*，将问题修复到足够大的正方形尺寸的情况下。根据文章，JPS应该比常规A*更有效。放缓的原因似乎是两个呼吁跳入" Diegonal Case"的呼吁。（跳跃方法的第15-29行）。
显然，我的实施一定有一些错误/效率低下。但是是什么？
代码：
跳跃方法是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
}
导航是实现A*的方法，从"开始"参数到'end'参数。
PriorityQueue是基于本文的通用实现。它的临界和脱水方法具有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是一种返回节点"向量"的邻居的方法。一个*版本：
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的方法。
iSblocked是一种检查vector2是否在地图内部的方法，并且它也位于封锁的正方形中（"阻止"是指具有障碍物的正方形）。它具有O（log2（n））复杂性。
其他信息：
- 我目前仅在目标和起点之间没有障碍的情况下检查了这一点。这意味着JPS算法仅扩展1平方。同时，常规a*扩展8，以找到（100，100）到（0，0）的路径，但是在找到（100，100）到（-800，-580）之间的距离时2325正方形。在最后一个情况下，有一个明显的帧速率下降，使游戏几乎无法玩。
- 帧速率已解锁。
- 网格中的口吃少于1200个正方形，该游戏的帧速率略有下降到约1600。
如果需要更多信息，我将愉快地提供它，
预先感谢！
在我的游戏中，我使用a*来进行三维路径。这需要更多的处理时间，但是实施的构建方式几乎是看不见的。
public void FixedUpdate()
{
if (calculating && openSet.Count > 0 && calculatingStep < 240)
PathfindingStep(navDestination, navAccurancyFactor);
else calculating = false;//...
}
固定通话每秒50次。
private void PathfindingBegin(Vector3 destination)
{
navAccurancyFactor = (1 + (Vector3.Distance(walkerTransform.position, destination) / (accurancy * 5)));
navDestination = destination;
calculatingStep = 0;
calculating = true;
closedSet = new List<PathNode>();
openSet = new List<PathNode>();
Vector3 startPos;
if (path.Count > 0)
startPos = path.Last();
else
startPos = walkerTransform.position;
// Шаг 2.
PathNode startNode = new PathNode()
{
Position = startPos,
CameFrom = null,
PathLengthFromStart = 0,
HeuristicEstimatePathLength = GetHeuristicPathLength(walkerTransform.position, destination)
};
openSet.Add(startNode);
}
呼叫pathfindingbegin以启动和下一个调用pathfindingstep onse每帧以构建路径。
private void PathfindingStep(Vector3 destination, float accuracyFactor)
{
calculatingStep++;
PathNode currentNode;
// Шаг 3.
currentNode = openSet.OrderBy(node => node.EstimateFullPathLength).First();
// Шаг 4.
if (Vector3.Distance(currentNode.Position, destination) <= accurancy * accuracyFactor)
{
PathfindingComplete(CollapsePath(GetPathForNode(currentNode)).ToArray());
return;
}
// Шаг 5.
openSet.Remove(currentNode);
closedSet.Add(currentNode);
// Шаг 6.
List<PathNode> neighbours = GetNeighbours(currentNode, destination, accuracyFactor);
foreach (PathNode neighbourNode in neighbours)
{
// Шаг 7.
if (closedSet.Count(node => node.Position == neighbourNode.Position) > 0)
continue;
PathNode openNode = openSet.Find(node => node.Position == neighbourNode.Position);
// Шаг 8.
if (openNode == null)
openSet.Add(neighbourNode);
else if (openNode.PathLengthFromStart > neighbourNode.PathLengthFromStart)
{
// Шаг 9.
openNode.CameFrom = currentNode;
openNode.PathLengthFromStart = neighbourNode.PathLengthFromStart;
}
}
}
在末端呼叫pathfindingComplete应用路径。如果目的地不可释放。
private void PathfindingComplete(Vector3[] pathPoints)
{
if (pathPoints != null)
{
status = DriverStatus.Navigating;
foreach (Vector3 x in pathPoints)
{
//Debug.Log(x);
path.Enqueue(x);
}
BuildPathArrows();
}
calculating = false;
}
P.S。我们可以在https://github.com/daniilchikish/spacecomander
尝试不是在一个帧中，而是在几个帧中进行迭代。并使用深度分析来查找性能泄漏。