Доброго времени суток.

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

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

Упрощения: 

• Все вычисления проводятся на двухмерной плоскости
• Объект и препятствия всегда прямоугольники, не вращаются (стороны параллельны осям)
• Не требуется сверх быстрая производительность

Пробовал алгоритмы на сетке в духе А* но они дают плохое качество, из-за необходимости апроксимировать препятствия на сетку размером в исходный объект.
Смотрел NavMesh, но не нашел внятного описания алгоритма, да и работает он на трехмерном пространстве
Самое близкое что я нашел - http://alienryderflex.com/shortest_path/, но оно опять таки ищет путь от точки до точки, не учитывая размер объекта.

Подскажите наиболее подходящий алгоритм поиска пути для данных условий.

никаких сеток не нужно

путь будет представлять собой ломаную

вершины ломаной будут какие-то углы каких-то прямоугольников, эти углы - вершины графа

ребро между вершинами есть, если оно не пересекает никаких прямоугольников (можно просто проверять пересечение сторон), если есть, его вес - просто длина

так что можно попробовать простой волновой алгоритм по этому графу, а там смотреть

касательно неточечных областей для старта и финиша: тут всё просто, считаем всю область одной вершиной графа, но рёбра и их длину находим минимизацией по всем точкам границы области

Можно упростить задачу:
 - проводим через поле не весь объект, а только одну его контрольную точку, для определенности - верхний левый угол;
 - строим "виртуальные" границы препятствий; для этого продолжаем каждое препятствие влево и вверх соответственно на ширину и высоту исходного объекта.

Теперь контрольная точка находится внутри "виртуального" препятствия тогда и только тогда, когда исходный объект пересекается с исходным препятствием. Соответственно, если контрольная точка лежит вне "виртуальных" границ, то пересечения нет.

Таким образом задача сведена к построению пути для безразмерной точки, а готовые алгоритмы для нее уже есть.

Я думаю, надо взять последний алгоритм и добавить учёт размеров движущегося прямоугольника. Введём множество V:={-1, 1}^2, которое служит для нумерации вершин прямоугольника. Учёт размеров: если движущийся прямоугольник имеет полудиагональ d0 и огибает вершину v1 (v1∈V) неподвижного прямоугольника с центром c1 и полудиагональю d1, то его центр проходит не через точку c1+d1·v1, как в исходном алгоритме, а через точку c1+(d1+d0)·v1, где «·» — скалярное произведение. Не забудьте выбросить вершины и рёбра графа, в которых движущийся прямоугольник пересекается с хотя бы одним неподвижным прямоугольником.