Алгоритм движения корабля

Question

Допустим, у нас прямоугольное море.Он довольно большой - 10000х20000.

У нас тоже есть острова.Для простоты предположим, что они также прямоугольные.Мы знаем их точные места (координаты).

Если у нас есть корабль, где-то на карте - (x1, y1), как мы можем найти кратчайший путь к другой точке на карте (x2, y2)не переходя ни один из островов?

Обновление: Пока нет никаких ограничений - ни для корабля, ни для моря.Если мы можем упростить (и ускорить) вещи, добавив несколько - это более чем приветствуется.

Путь даже не должен быть лучшим - например, он может быть на 10% дешевле - совершенно приемлемо.

Answer 1

1. Границы приближенных островов с 2D полигонами
2. соединить вершины разделенных многоугольников (и начальную и конечную точки) с ребрами (они не должны пересекать острова)
3. применить A * к результирующему графику

Такой график намного меньше сетки 10000x20000 и позволяет находить более реалистичные пути в более удобное время

Обновление : если острова невелики, вы можете просто перемещать корабль в направлении финишной точки и обходить острова на их левой или правой границе

Answer 2

Я бы попытался представить сетку в виде графика и запустить алгоритм Дейкстры.

График, вероятно, занимает 1 ГБ или даже больше, но он подходит для оперативной памяти любого современного компьютера.

Сложность алгоритма составляет O (E + V * log (V)), т. Е. O (размер сетки). Поскольку существует ~ 10 ^ 8 узлов, я думаю, это должно быть выполнимо. Допустим, у нас есть ~ 1000 тактов процессора на узел. Если у нас 4G CPU, тик равен 2,5 * 10 ^ -10 сек, то есть у нас 2,5 * 10-7 сек. на узел. Для 2 * 10 ^ 8 узлов у нас есть ~ 1 минута.

Answer 3

В связи с предложением Tiendil в книге LaValle "Алгоритмы планирования" обсуждается, какие ребра включить в графы для поиска по кратчайшему пути , если острова являются 2D-полигонами.

Answer 4

Если острова на разрезах относительно редки, вы можете использовать алгоритм, который я реализовал в прошлом году, для роботов, преследующих движущийся шар в среде с объектами, которых следует избегать.

Что я сделал, так это определил точки сеткивокруг робота, мяча и препятствий, и добавьте разреженную равномерную сетку по всей среде.Стоимость ребра между двумя точками сетки зависит от того, насколько близко препятствия находятся к этому ребру (если ребро проходит через препятствие, стоимость будет бесконечной).Затем рассчитайте лучший маршрут, используя A *.Это делается 40 раз в секунду на старом ноутбуке, запрограммированном на Java.