Двухсторонний поиск путевых точек: комбинации WP для перехода от curLocation к targetLocation

Question

Пожалуйста, найдите время, чтобы понять мою ситуацию.Если это не понятно, пожалуйста, сообщите мне в комментарии.

У меня есть ArrayList of Waypoints.Эти путевые точки расположены не в любом порядке.Путевая точка имеет следующие свойства:
{int type, float z, float y, float x, float rotation}

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

• В этом двумерном мире, х представляет ось X, а Z представляет ось Y.
• Если х увеличивается, объектв мире движется на восток.Если x уменьшается, объект в мире перемещается на запад.
• Если z увеличивается, объект в мире перемещается на север.Если z уменьшается, объект в мире перемещается на юг.

Таким образом, эти "новые" путевые точки могут быть упрощены до: waypoint = {float x, float y}.

Теперь эти путевые точки представляют Xоси (x) и оси Y (z) местоположения объекта.Кроме того, есть текущее местоположение: curLocation = {float x, float y} и целевое местоположение: tarLocation = {float x, float y}.

Вот что я хочу получить:
Все комбинации путевых точек (иначе: пути или маршруты), который приведет от curLocation до tarLocation при следующих строгих условиях:

1. Расстояние между каждой путевой точкой не должно превышать (float) maxInbetweenDistance.Это включает начальное расстояние от curLocation до первой путевой точки и расстояние от последней путевой точки до tarLocation.Если такая комбинация путевых точек невозможна, следует вернуть значение null.
2. Если в пределах maxInbetweenDistance найдено несколько путевых точек от путевой точки, ведущей к целевой путевой точке, следует выбрать ближайшую путевую точку (еще лучшеесли альтернативная путевая точка, которая находится немного дальше, приведет к появлению нового пути с более длинным расстоянием, которое также будет возвращено).
3. Порядок возвращаемых комбинаций путевых точек (путей) должен быть от кратчайшего маршрута (минимального расстояния) досамый длинный маршрут (максимальное расстояние)

Наконец, пожалуйста, обратите внимание на следующие моменты:

1. Это единственное, что мне нужно, чтобы делать AI / поиск пути, поэтому я и делаюне хочу использовать полноценную систему поиска пути или искусственного интеллекта.Я полагаю, что одна функция должна быть в состоянии справиться с вышеперечисленным.
2. Если возврат всех возможных комбинаций путевых точек приводит к слишком большим накладным расходам, было бы также хорошо, если бы можно было указать максимальное количество комбинаций (но все же заказано изближайший к дальнему).Например.5 ближайших путей.

Как бы мне этого добиться?Любые отзывы приветствуются.

Answer 1

Если ваши путевые точки обладают связностью, вам следует взглянуть на алгоритм кратчайшего пути Дейкстры.Первая пара хитов Google даже перечисляет реализацию в Java.(Я не могу сказать, известна ли связь из поста, но она действительно содержит тег «graph-алгоритма», так что я предполагаю, что так).Как следует из названия, этот метод дает вам кратчайший путь между двумя узлами.

Ваши ограничения являются сложными, как и необходимость всех возможных комбинаций путей в соответствии с этими ограничениями.Опять же - при условии наличия соединения - ваша матрица смежности узлов может применять ваше правило maxInbetweenDistance.Аналогично, вы можете использовать эту матрицу для получения «следующих лучших» решений.Как только оптимальный путь известен, вы можете пометить этот путь (или его элементы) как недоступный, а затем повторно запустить алгоритм Дейкстры.Повторяя этот процесс, вы можете получить набор все более неоптимальных путей.

Как правило: в большинстве задач вычислительной геометрии Z - это высота, а горизонтальная плоскость образована осями XY..

Answer 2

Я думаю, что ваше решение - начать с Алгоритма Дейкстры , чтобы сначала найти кратчайший путь. Вы можете считать свои путевые точки связным графом, где узлы соединены, если они достаточно близки в плоскости xy, а затем примените Dijkstra (есть много примеров листингов кода онлайн).

Теперь у вас есть кратчайший путь через ваш график от начала до конца, который будет состоять из N ребер графика.

Затем вам нужно будет создать N новых графиков, каждый точно так же, как первый, но с одним сегментом вашего кратчайшего маршрута, не подключенным. Найдите кратчайшие маршруты от начала до конца на этих модифицированных графиках. Теперь у вас есть N + 1 маршрутов, которые вы можете отсортировать по длине.

Повторяйте это до тех пор, пока вы не найдете достаточно путей для своих нужд, или пока не останется не назначенных путей.

Я не нашел названия для этой техники, но она описана как модификация Dijkstra здесь .

Answer 3

Что ж, проще всего реализовать, вероятно, создание ArrayList путей, который, в свою очередь, будет ArrayList путевых точек, который содержит ВСЕ возможные пути, с последующим использованием рекурсивной функции для возврата, является ли каждый путь действительным или нет с учетом начальногои значения конечной точки, и максимальное расстояние, и, если путь недопустим, удалите его из списка.Следующим шагом будет прохождение каждого из оставшихся путей и упорядочение их от кратчайшего общего расстояния до кратчайшего.Это будет метод грубой силы, чтобы получить то, что вы хотите, поэтому наименее эффективный из возможных.Когда я вернусь домой сегодня вечером, я сделаю репост, если у кого-то уже нет более эффективного способа сделать это в Java.

Редактировать: если метод грубой силы слишком велик, список путевых точек должен будетбыть отсортированными как, лучший способ, вероятно, сортировать их первоначально на основе расстояния от начальной точки.