Справка по алгоритму A * (A-Star)

Question

Ну, это мой обновленный код.Не замедляется, но путь не появляется.

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

Answer 1

Рядом с тем, что упоминает Крис, есть еще что-то не так с вашим использованием MapNodes.Он должен быть отсортирован и содержать все элементы, включая все узлы, которые вы помещаете в список addNodes.Кэширование всех узлов, которые необходимо добавить в MapNodes, не является допустимой реализацией A *.Когда вы добавляете узел к addNodes, он фактически должен быть добавлен к MapNodes, а затем MapNodes должен быть отсортирован по F, который является числом, связанным с узлом, который является суммой общей стоимости от начального узлак этому узлу и значение эвристической функции оценивается для этого узла.В Интернете есть множество описаний эвристических функций, я предлагаю вам прочитать об этом.

И, кстати, где же эвристика в вашем коде?Алгоритм A * - это просто медленный алгоритм Дейкстры без эвристики.Боюсь, то, что вы реализовали, больше напоминает Дейкстру, чем A *.

И чтобы ответить на ваш настоящий вопрос: алгоритм, вероятно, не дает пути, потому что есть ошибки, мешающие алгоритму поиска фактически достигатьузел назначения.

Answer 2

Есть несколько проблем с кодом.Во-первых, ваши проверки X + 1 и Y + 1 имеют сравнение неверно (больше чем вместо меньше).Я подозреваю, что именно это приводит к сбою алгоритма.

Во-вторых, хотя я не знаком с алгоритмом, я подозреваю, что вам нужно что-то сделать, чтобы убедиться, что уже проверенные вами узлы не проверяются сноваитераций.Также вам необходимо убедиться, что вы не добавляете узлы к MapNodes, которые уже присутствуют.Сочетание этих факторов, вероятно, является причиной медлительности, которую вы видите, потому что это приведет к экспоненциальному росту MapNodes со многими избыточными узлами.