unity3d 改进A* 寻路C#

t40tm48m  于 2022-11-15  发布在  C#
关注(0)|答案(1)|浏览(288)

你好,我有下面的代码。在一个非常复杂和/或大的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;
    }
}

我希望看到我的问题的解决方案,请了解思考过程

vktxenjb

vktxenjb1#

要允许对角遍历,您可能只需扩展候选列表,如下所示:

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

但请注意,这将增加更多的复杂性,因为有更多的候选要检查。您没有指定Map有多大。在某个点上,算法肯定会变慢,因为有太多的瓷砖要检查。

相关问题