В C# также* осуществление поиска путей, с акцентом на повторное использование и эффективность


Я писал на C#, а* поиск пути (правда, это достаточно универсальный, что он может быть использован для других целей поиска) осуществление. Я начал это, когда я обнаружил, что существующие реализации часто не поддерживают 3D средах, хотя это только требует изменения neighbours функция. Поэтому я постарался сделать эту реализацию очень универсальный, такой, что он может быть использован для любого числа измерений. Многие реализации также необходимы для расширения базовых классов с классом плитки, которые я предпочел бы избежать. Наконец я положил много усилий в эффективности, итерации и тестирование нескольких образцов, прежде чем остановиться на одном, который, кажется, работают хорошо (хотя я только по сравнению с другими версиями себя до сих пор).

Он использует BlueRaja по High-Speed-Priority-Queue-for-C-Sharp. Есть два класса, Node что расширяет BlueRaja по FastPriorityQueueNode и PathFinder которая требует heuristic, neighbours и indexMap параметризацию функции. В плитку или установки представляет собой абсолютно универсальный тип T что эти функции могут действовать произвольно. Двое других, надеюсь, не требует пояснений, но indexMap это функция, которая возвращает уникальный целочисленный идентификатор T. Например, это простой 3D реализации: tile => (tile.x * SizeX * SizeY) + (tile.y * SizeY) + tile.z;. Наконец, PathFinder также требует size переменная, которая является самым большим значением, что indexMap могут производить.

Любая обратная связь приветствуется. Я особенно любопытно про эффективность, и сколько использование универсальных типов могут повлиять на эффективность. Код в репо , включая некоторые тесты, которые также работают в качестве примеров, но я буду включать две соответствующие классы и примеры реализации типовых функций ниже:

Node.cs

using Priority_Queue;

namespace Jansk.Pathfinding
{
    public class Node<T> : FastPriorityQueueNode
    {
        public T Position;
        public int Previous;
        public int Cost;
        public int Heuristic;
        public int Index;

        public Node(T position)
        {
            Position = position;
        }
    }
}

Pathfinder.cs

using System;
using System.Collections.Generic;
using Priority_Queue;

namespace Jansk.Pathfinding
{
    public class PathFinder<T>
    {
        private FastPriorityQueue<Node<T>> frontier;
        public Node<T>[] Graph;
        private Func<T, T, int> heuristic;
        private Func<T, IEnumerable<T>> neighbours;
        private Func<T, int> indexMap;
        private int size;

        public const int MaximumPathLength = 650;

        public PathFinder(Func<T, T, int> heuristic, int size)
        {
            this.heuristic = heuristic;
            this.size = size;
        }

        public T[] Path(T startPosition, T goalPosition, Func<T, int> indexMap, Func<T, IEnumerable<T>> neighbours)
        {
            Node<T> goalNode = null;
            this.indexMap = indexMap;
            this.neighbours = neighbours;

            BuildGraph(startPosition, delegate(Node<T> current)
            {
                if (current.Position.Equals(goalPosition))
                {
                    goalNode = current;
                    return true;
                }
                return false;
            }, position => heuristic(position, goalPosition));

            return GeneratePathFromGraph(startPosition, goalNode);
        }

        public void BuildGraph(T startPosition, Func<Node<T>, bool> goalTest, Func<T, int> heuristic,
            Func<T, IEnumerable<T>> neighbours, Func<T, int> indexMap)
        {
            this.neighbours = neighbours;
            this.indexMap = indexMap;
            BuildGraph(startPosition, goalTest, heuristic);
        }

        public void BuildGraph(T startPosition, Func<Node<T>, bool> goalTest, Func<T, int> heuristic)
        {
            frontier = new FastPriorityQueue<Node<T>>(150);
            Graph = new Node<T>[size];

            var initial = new Node<T>(startPosition) {Index = indexMap(startPosition) };
            frontier.Enqueue(initial, 0);
            Graph[initial.Index] = initial;

            while (frontier.Count > 0 && frontier.Count < MaximumPathLength)
            {
                var current = frontier.Dequeue();

                if (goalTest(current))
                {
                    break;
                }

                AddNeighbours(current, heuristic);
            }
        }

        private T[] GeneratePathFromGraph(T startPosition, Node<T> goalNode)
        {
            var path = new List<T>();

            if (goalNode != null)
            {
                var node = goalNode;
                while (true)
                {
                    if (node.Position.Equals(startPosition)) break;
                    path.Add(node.Position);
                    node = Graph[node.Previous];
                }
            }

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

        private void AddNeighbours(Node<T> node, Func<T,int> heuristic)
        {
            foreach (var neighbour in neighbours(node.Position))
            {
                var newCost = node.Cost + 1;
                var index = indexMap(neighbour);
                if (index >= 0 && index < size)
                {
                    var existingNeighbour = Graph[index];

                    if (existingNeighbour == null || newCost < existingNeighbour.Cost)
                    {
                        var next = new Node<T>(neighbour) {Cost = newCost, Index = index};
                        Graph[next.Index] = next;
                        if (next.Heuristic < 0 && heuristic != null) next.Heuristic = heuristic(neighbour);
                        frontier.Enqueue(next, next.Cost + next.Heuristic);

                        next.Previous = node.Index;
                    }
                }
            }
        }
    }
}

Пример 3D neighbours функции:

delegate(Tile tile)
    {
        var neighbours = new List<Tile>();
        if (tile.x - 1 >= 0 && !Tiles[tile.x - 1, tile.y, tile.z].IsBlocking)
            neighbours.Add(Tiles[tile.x - 1, tile.y, tile.z]);
        if (tile.x + 1 < SizeX && !Tiles[tile.x + 1, tile.y, tile.z].IsBlocking)
            neighbours.Add(Tiles[tile.x + 1, tile.y, tile.z]);
        if (tile.y + 1 < SizeY && !Tiles[tile.x, tile.y + 1, tile.z].IsBlocking)
            neighbours.Add(Tiles[tile.x, tile.y + 1, tile.z]);
        if (tile.y - 1 >= 0 && !Tiles[tile.x, tile.y - 1, tile.z].IsBlocking)
            neighbours.Add(Tiles[tile.x, tile.y - 1, tile.z]);
        if (tile.z - 1 >= 0 && Tiles[tile.x, tile.y, tile.z - 1].IsStairs)
            neighbours.Add(Tiles[tile.x, tile.y, tile.z - 1]);
        if (tile.z + 1 < SizeZ && Tiles[tile.x, tile.y, tile.z + 1].IsStairs)
            neighbours.Add(Tiles[tile.x, tile.y, tile.z + 1]);

        return neighbours.ToArray();
    };

Пример 3D heuristic функции:

delegate (Tile from, Tile to)
    {
        return Math.Abs(from.x - to.x) + Math.Abs(from.y + to.y) + Math.Abs(from.z + to.z);
    };


378
3
задан 10 марта 2018 в 11:03 Источник Поделиться
Комментарии
2 ответа

Я писал длинный ответ, но меня толкало на то, что вы зависите от потребителя предоставления сопоставление индекса, так что я буду держать этот короткий и оставить ответ кого-то другого.


Этот код будет гораздо легче использовать, если вы не пройти size в конструктор: он должен быть обеспечен с индексом карте.

Не сумев обеспечить "правильную" size результаты AddNeighbours бесшумно опуская любой узел, индекс является слишком высокой, что бы быть достаточно близко, невозможно отладить без кода доступа: это должно быть задокументировано. Я бы также рассмотреть возможность бросать исключение, если индекс при условии, что слишком высоко, так что потребитель знает, что это произошло: есть случай, где это silenty отказ ценен?


public const int MaximumPathLength = 650;

Что это? Почему это постоянно? Это серьезно ограничивает возможность повторного использования кода. Если этот лимит превышен (или нет Путь), Path просто возвращает пустой массив, что не очень полезно (я должен предпочесть nullили действительно явно bool вернуться к "успеху" с out параметр, содержащий путь). Если должна быть отсечка, то я хотел бы, чтобы это было настраиваемым.

Я также не нравится, что GeneratePathFromGraph(T, Node<T>) отвечает за обработку null goalNodeЯ бы снять goalNode != null проверить. Эта проверка должна быть выполнена в Path. (Если GeneratePathFromGraph был открытым, я бы вместо этого предлагаю вам сделать чек, но бросить внимательный исключение вместо того, чтобы придумывать бессмысленный результат).


BuildGraph - это немного странно. Я бы предложил переименовать его в FindPath и возвращая goalNode, а не требовать ужасное задание в лямбде, предусмотренных в Path.


Node<T> можно (и думаю нужно) быть неизменным (т. е. только для чтения поля/свойства), с 2 конструктора: один для "пуск" узла и для "реальных" узлов. Связано это строки из AddNeighbours...

if (next.Heuristic < 0 && heuristic != null) next.Heuristic = heuristic(neighbour);

...я уверена, что не работает (next.Heuristic всегда будет 0). Я не понимаю смысл этой проверки... и эта ошибка не закралась, если бы Вы были вынуждены вычислить эвристический перед сборкой узла.

2
ответ дан 10 марта 2018 в 12:03 Источник Поделиться

На беглый взгляд, похоже, ты никогда не звонишь UpdatePriority(). Это означает, что ваш навигатор не будет работать с не-последовательной эвристики. Это нормально (это общее предположение в*, поскольку позволяет пропустить проверку), но это должно быть задокументировано.

Я бы рекомендовал вернуть IList<T> или IEnumerable<T> вместо T[]. Это гораздо более гибкая, и позволяет пропустить звонок ToArray().

PriorityQueue использует float приоритетов. Для инт GenericPriorityQueue<int> может быть быстрее, вы бы в профиль.

2
ответ дан 10 марта 2018 в 08:03 Источник Поделиться