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

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

введите здесь описание изображения

Примером может быть поездка из пункта А в пункт Б.

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


algorithm a-star
person Clash    schedule 22.07.2011    source источник
comment
Сетка - почти единственный способ решить эту проблему. У вас должны быть ориентиры на карте, между которыми вы можете или не можете перемещаться. Именно плотность сетки определяет вашу точность. Извините, это не более полезно, но это может подтолкнуть вас в правильном направлении.   -  person Paystey    schedule 22.07.2011
comment
Линии обозначают места, куда вы не можете попасть. Есть ли какие-либо другие затраты, кроме расстояния? Например, местность наклонная, и подниматься в гору труднее?   -  person JCooper    schedule 22.07.2011
comment
@JCooper: Хороший комментарий, но ОП сказал 2D, поэтому я бы понял, что высота не влияет на стоимость.   -  person Yuck    schedule 22.07.2011
comment
Почему это должен быть поиск A*, если расстояние — единственное, что имеет значение?   -  person Razor Storm    schedule 22.07.2011
comment
@JCooper, нет, уклона нет, единственным препятствием являются линии   -  person Clash    schedule 23.07.2011
comment
@Razor, кажется, я тебя не понял. Мне нужен путь, а не только расстояние   -  person Clash    schedule 23.07.2011

Ответы (3)


arrow_upward
5
arrow_downward

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

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

  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, и дальше все пойдет.

Измененное изображение.

person JCooper    schedule 22.07.2011
comment
Да, это то, что я имел в виду. +1 за красивую картинку. - person Fred Foo; 22.07.2011
comment
спасибо за отличный ответ! Однако у меня есть сомнения, как я узнаю, нахожусь ли я внутри или вне линии? Например, вы соединили А с 11, а затем с 10, но провели линию снаружи. У меня такое же сомнение по А8, откуда мне знать, что я не могу выбраться (это значит, что я внутри, а не за линией)? Например, я не знаю, как определить, что я не могу подключить 9 к 4 (внутри могу, а снаружи нет). Может я что-то не так понял. Еще раз спасибо заранее! - person Clash; 23.07.2011
comment
@Clash Вы правы, с этим сложно справиться, но не невозможно. Линия от 11 до 10 должна быть снаружи, потому что вы рассматриваете только выпуклую сторону. Находясь внутри фигуры, вы не должны рассматривать 9 или 4, потому что вы не можете добраться до выпуклой стороны. Вы можете посетить только выпуклую сторону вершины, и если путь к следующему узлу находится за пределами тупого угла, образованного в этой вершине, то это недопустимый путь. Это кажется разумным? - person JCooper; 23.07.2011
comment
это звучит разумно, я проверю вас как принятый ответ. Однако сначала я попробую сеточное решение, чтобы убедиться, что оно достаточно быстрое. спасибо за вашу помощь и хорошие идеи! - person Clash; 24.07.2011

arrow_upward
4
arrow_downward

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

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

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

person Fred Foo    schedule 22.07.2011
comment
Другой подход к созданию ребер графа в этом случае может заключаться в создании триангуляции Делоне вершин с ограничениями (ограничениями будут ребра-препятствия). Хорошим алгоритмом для этого является O(nlog(n)), и он должен привести к графу с низким количеством ребер. - person Darren Engwirda; 22.07.2011

arrow_upward
2
arrow_downward

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

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

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

person Bernd Elkemann    schedule 22.07.2011