改进A*寻径c#

Question

你好，我有以下代码。在一个非常复杂和/或大的地图上，我的Unity项目崩溃了。而且我的角色只能上下左右移动网格。没有diagnonally

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;
}
}

我想看到一个解决我的问题，请理解思维过程

Answer 1

要允许对角线遍历，您可以按如下方式扩展候选列表:

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),
new Vector2Int(bestCell.x - 1, bestCell.y - 1),
new Vector2Int(bestCell.x + 1, bestCell.y - 1),
new Vector2Int(bestCell.x - 1, bestCell.y + 1),
new Vector2Int(bestCell.x + 1, bestCell.y + 1),
};

但是请注意，这将进一步增加复杂性，因为有更多的候选对象要检查。你没有说明地图有多大。在某一点上，算法必然会变慢，因为有太多的贴图要检查。