2

好吧，这是我更新的代码。它没有减速，但没有路径出现。

public static IntPosition[] GetPath(BlockType[,] blocks, IntPosition start, IntPosition end, int threshhold)
    {
        List<Node> MapNodes = new List<Node>();
        MapNodes.Add(new Node() { Position = start });

        bool[,] explored = new bool[blocks.GetLength(0), blocks.GetLength(1)];

        explored[start.X, start.Y] = true;

        int? endNode = null;

        int index = 0;
        while (endNode == null && index < threshhold)
        {
            List<Node> addNodes = new List<Node>();


            foreach (Node n in MapNodes)
            {
                //left
                if (n.Position.X - 1 >= 0)
                    if (explored[n.Position.X - 1, n.Position.Y] == false)
                        if (blocks[n.Position.X - 1, n.Position.Y] == BlockType.Open)
                        {
                            int i = addNodes.Count;
                            addNodes.Add(new Node() { Position = new IntPosition(n.Position.X - 1, n.Position.Y), ParentNode = n });

                            explored[n.Position.X - 1, n.Position.Y] = true;

                            if (addNodes[i].Position == end)
                                endNode = i;
                        }

                //right
                if (n.Position.X + 1 <= blocks.GetLength(0) - 1)
                    if (explored[n.Position.X + 1, n.Position.Y] == false)
                        if (blocks[n.Position.X + 1, n.Position.Y] == BlockType.Open)
                        {
                            int i = addNodes.Count;
                            addNodes.Add(new Node() { Position = new IntPosition(n.Position.X + 1, n.Position.Y), ParentNode = n });

                            explored[n.Position.X + 1, n.Position.Y] = true;

                            if (addNodes[i].Position == end)
                                endNode = i;
                        }

                //up
                if (n.Position.Y - 1 >= 0)
                    if (explored[n.Position.X, n.Position.Y - 1] == false)
                        if (blocks[n.Position.X, n.Position.Y - 1] == BlockType.Open)
                        {
                            int i = addNodes.Count;
                            addNodes.Add(new Node() { Position = new IntPosition(n.Position.X, n.Position.Y - 1), ParentNode = n });

                            explored[n.Position.X, n.Position.Y - 1] = true;

                            if (addNodes[i].Position == end)
                                endNode = i;
                        }

                //down
                if (n.Position.Y + 1 <= blocks.GetLength(1))
                    if (explored[n.Position.X, n.Position.Y + 1] == false)
                        if (blocks[n.Position.X, n.Position.Y + 1] == BlockType.Open)
                        {
                            int i = addNodes.Count;
                            addNodes.Add(new Node() { Position = new IntPosition(n.Position.X, n.Position.Y + 1), ParentNode = n });

                            explored[n.Position.X, n.Position.Y + 1] = true;

                            if (addNodes[i].Position == end)
                                endNode = i;
                        }
            }

            MapNodes.AddRange(addNodes);

            index++;
        }

        if (endNode == null)
            return new IntPosition[] { };
        else
        {
            List<IntPosition> path = new List<IntPosition>();

            path.Add(end);

            Node CurrentNode = (MapNodes[(int)endNode].ParentNode);
            bool endReached = false;

            while (endReached == false)
            {
                path.Add(CurrentNode.Position);

                if (CurrentNode.Position == start)
                    endReached = true;
                else
                    CurrentNode = CurrentNode.ParentNode;
            }


            path.Reverse();
            return path.ToArray();
        }
    }



public class IntPosition
{
    public int X;
    public int Y;

    public IntPosition(int x, int y)
    {
        X = x;
        Y = y;
    }

    public IntPosition() { X = 0; Y = 0; }

    public override bool Equals(object obj)
    {
        return ((IntPosition)obj).X == X && ((IntPosition)obj).Y == Y;
    }
}
4

2 回答 2

0

除了 Chris 提到的内容之外，您对MapNodes. 它需要排序，并包含所有成员，包括您放在列表中的所有节点addNodes。缓存所有需要添加的节点MapNodes不是有效的 A* 实现。当你将一个节点添加到 时addNodes，它实际上应该被添加到MapNodes然后MapNodes应该按 F 排序，这是一个与节点相关的数字，它是从 startnode 到该节点的总成本与启发式值的总和为该节点评估的函数。互联网上有多种关于启发式函数的描述，我建议您尝试阅读相关内容。

顺便说一句，你的代码中的启发式在哪里？A* 算法只是一个没有启发式的慢速 Dijkstra 算法。恐怕你所实现的更像 Dijkstra 而不是 A*。

并回答您的实际问题：该算法可能不会产生路径，因为存在错误，从而阻止搜索算法实际到达目标节点。

于 2011-06-05T09:10:50.083 回答
0

代码有几个问题。首先，您的 X + 1 和 Y + 1 检查有错误的比较方式（大于而不是小于）。我怀疑这就是导致算法失败的原因。

其次，虽然我不熟悉该算法，但我怀疑您需要做一些事情来确保您已经检查过的节点不会在后续迭代中再次检查。此外，您需要确保不向MapNodes已经存在的节点添加节点。这些组合很可能是您看到的缓慢的原因，因为它会导致MapNodes许多冗余节点呈指数增长。

于 2011-06-05T08:10:09.887 回答