你好,我有下面的代码。在一个非常复杂和/或大的Map上,我的Unity项目崩溃了。而且我的角色只能穿过网格向上,向下,向左和向右。没有对角线
public static List<Vector2Int> FindRoute(Vector2Int start, Vector2Int end)
{
if (!GameState.IsFree(end))
return null; // Principially not possible to reach the end.
HashSet<Vector2Int> pool = new(); // Open cells.
HashSet<Vector2Int> visited = new(); // Visited cells.
Dictionary<Vector2Int, Vector2Int> parents = new(); // Tracks where did we reach a given cell from.
// 1. Traverse the grid until you find the end.
pool.Add(start);
while (pool.Count > 0)
{
var bestCell = pool
.OrderBy(c => (c - start).sqrMagnitude + (end - c).sqrMagnitude) // A* heuristics.
.First();
visited.Add(bestCell);
pool.Remove(bestCell);
var candidates = new List<Vector2Int> {
new Vector2Int(bestCell.x + 1, bestCell.y),
new Vector2Int(bestCell.x - 1, bestCell.y),
new Vector2Int(bestCell.x, bestCell.y + 1),
new Vector2Int(bestCell.x, bestCell.y - 1),
};
foreach (var candidate in candidates)
{
if (visited.Contains(candidate) || !GameState.IsFree(candidate))
continue;
parents[candidate] = bestCell;
if (candidate == end)
break;
pool.Add(candidate);
}
if (parents.ContainsKey(end))
break;
}
// 2. Assemble the route.
if (!parents.ContainsKey(end))
return null;
var route = new List<Vector2Int>();
var cell = end;
while (cell != start)
{
route.Insert(0, cell);
cell = parents[cell];
}
return route;
}
}
我希望看到我的问题的解决方案,请了解思考过程
1条答案
按热度按时间vktxenjb1#
要允许对角遍历,您可能只需扩展候选列表,如下所示:
但请注意,这将增加更多的复杂性,因为有更多的候选要检查。您没有指定Map有多大。在某个点上,算法肯定会变慢,因为有太多的瓷砖要检查。