Структура данных графика поиска Astar (A *) в C #

Question

Как вы структурируете свои графы / узлы в классе поиска графов?Я в основном создаю NavMesh и мне нужно сгенерировать узлы из одного многоугольника в другой.Ребро, соединяющее оба полигона, будет узлом.

Затем я выполню A * на этих узлах, чтобы вычислить кратчайший путь.Мне просто нужно знать, как структурировать мои классы и их свойства?

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

Answer 1

Все, что вам нужно для A *, - это возможность взять узел и эффективно извлечь из него список соседних узлов.Если у вас уже есть какая-то структура данных, которая отслеживает, какие ребра есть в каких полигонах, то это кажется простым;просто напишите функцию, которая принимает Edge и возвращает IEnumerable<Edge>, извлекая эти данные из существующей структуры данных.

Answer 2

Ознакомьтесь с этой серией об алгоритме A * в блоге Эрика Липперта. Он объясняет, среди прочего, какие структуры данных вам нужны