A * для поиска кратчайшего пути и обхода линий в качестве препятствий

Question

Я должен получить (самое короткое) / (оптимальное) расстояние между двумя точками в 2D. Я должен избегать форм, которые являются линиями, которые могут быть связаны вместе. Любое предложение о том, как изобразить узлы, по которым я могу путешествовать? Я думал о создании сетки, но это звучит не очень точно или элегантно. Я бы посчитал узел неприступным, если любая точка линии находится внутри квадрата (при этом узел является центром квадрата).

Примером будет переход из точки А в В.

Является ли сетка рекомендуемым способом решения этой проблемы? Большое спасибо заранее!

Answer 1

Я думаю, что по сути это ответ Ларсмана, сделанный немного более алгоритмическим:

Узлы графа являются вершинами препятствий. Каждая внутренняя вершина фактически представляет собой два узла: вогнутую и выпуклую стороны.

1. Вставить начальный узел в очередь приоритетов с эвклидовым эвристическим расстоянием.
2. Извлечь верхний узел из очереди приоритетов.
3. Выполните тест пересечения линии от узла к цели (возможно, с использованием методов структуры данных с трассировкой лучей для ускорения). Если не получится,
4. Рассмотрим луч от текущего узла ко всем остальным вершинам. Если между текущим узлом и рассматриваемой вершиной нет пересечений, а вершина является выпуклой с точки зрения текущего узла, добавьте вершину в очередь с приоритетами, отсортированную по накопленному расстоянию в текущем узле плюс расстояние от текущего узел к вершине плюс эвристическое расстояние.
5. Возврат к 2.

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

Итак, в вашем примере, после первой попытки A, B , вы нажмете A, 8 , A, 5 , A, 1 , A, 11 и A, 2 . Первыми узлами рассмотрения будут A, 8 , A, 1 и A, 5 , но они не могут выйти, а узлы могут вылет уже выдвинут в очередь с меньшим накопленным расстоянием. A, 2 и A, 11 будут рассмотрены, и дела пойдут оттуда.

Answer 2

Я думаю, что вы можете решить это с помощью поиска A * на графике, определенном как:

• Вершины: начало, место назначения и все конечные точки ребер препятствия.
• Края (функция преемника): любая пара из предыдущих, где соответствующая линия не пересекает края какого-либо препятствия. Наивная реализация будет просто проверять пересечение между потенциальным ребром и всеми ребрами препятствия. Более быстрая реализация могла бы использовать некоторый алгоритм 2-d tracing .

Т.е. нет необходимости дискретизировать плоскость в сетку, но без нее определение функции-преемника становится затруднительным.

Answer 3

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

РЕДАКТИРОВАТЬ: я просто помню стратегическую игру, которая использует Flow-Field. Но это не основной поток.

Кстати: чтобы понять, как рулевое поведение влияет на ваши объекты, взгляните на многие видео-ролики на YouTube об этом. Некоторые из них используют термин «поиск пути» в более общем смысле: включая глобальный алгоритм (A *), а также предотвращение столкновений, сглаживание пути и инерцию объекта, связанные с поведением рулевого управления.