| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск пути для полигонов |
| Автор: APXEOLOG 30.5.2013, 12:28 |
| Доброго времени суток. Много времени потратил на поиск подходящего алгоритма поиска путей, решил спросить мнения знающих людей. Задача: Необходимо найти самый короткий путь наиболее точным образом. Объект для которого ищем путь - прямоугольник (может быть разных размеров), препятствия - тоже прямоугольники (опять таки разных размеров). Пространство скорее свободно, чем занято (т.е. грубо говоря у нас есть роща деревьев, между которыми нужно найти оптимальный путь). Упрощения:
Пробовал алгоритмы на сетке в духе А* но они дают плохое качество, из-за необходимости апроксимировать препятствия на сетку размером в исходный объект. Смотрел NavMesh, но не нашел внятного описания алгоритма, да и работает он на трехмерном пространстве Самое близкое что я нашел - http://alienryderflex.com/shortest_path/, но оно опять таки ищет путь от точки до точки, не учитывая размер объекта. Подскажите наиболее подходящий алгоритм поиска пути для данных условий. |
| Автор: maxim1000 30.5.2013, 13:17 |
| никаких сеток не нужно путь будет представлять собой ломаную вершины ломаной будут какие-то углы каких-то прямоугольников, эти углы - вершины графа ребро между вершинами есть, если оно не пересекает никаких прямоугольников (можно просто проверять пересечение сторон), если есть, его вес - просто длина так что можно попробовать простой волновой алгоритм по этому графу, а там смотреть касательно неточечных областей для старта и финиша: тут всё просто, считаем всю область одной вершиной графа, но рёбра и их длину находим минимизацией по всем точкам границы области |
| Автор: AVA12 2.6.2013, 15:42 |
| Можно упростить задачу: - проводим через поле не весь объект, а только одну его контрольную точку, для определенности - верхний левый угол; - строим "виртуальные" границы препятствий; для этого продолжаем каждое препятствие влево и вверх соответственно на ширину и высоту исходного объекта. Теперь контрольная точка находится внутри "виртуального" препятствия тогда и только тогда, когда исходный объект пересекается с исходным препятствием. Соответственно, если контрольная точка лежит вне "виртуальных" границ, то пересечения нет. Таким образом задача сведена к построению пути для безразмерной точки, а готовые алгоритмы для нее уже есть. |
| Автор: beroal 3.6.2013, 12:48 |
| Я думаю, надо взять последний алгоритм и добавить учёт размеров движущегося прямоугольника. Введём множество V:={-1, 1}^2, которое служит для нумерации вершин прямоугольника. Учёт размеров: если движущийся прямоугольник имеет полудиагональ d0 и огибает вершину v1 (v1∈V) неподвижного прямоугольника с центром c1 и полудиагональю d1, то его центр проходит не через точку c1+d1·v1, как в исходном алгоритме, а через точку c1+(d1+d0)·v1, где «·» — скалярное произведение. Не забудьте выбросить вершины и рёбра графа, в которых движущийся прямоугольник пересекается с хотя бы одним неподвижным прямоугольником. |