Как реализовать алгоритм построения линии с обходом препятствий?
В нашей компании разрабатывается программа, которая позволяет строить блок-схемы. Моей задачей является создание алгоритма построения линий, соединяющих элементы схемы и при этом необходимо минимизировать пересечение линий с другими линиями и блоками. То есть, если линия встречает на своем пути, например, блок, она должна его обойти и идти дальше.
Я попытался приспособить для этого pathfinding алгоритмы A* и волновой алгоритм Ли и принял 1 пиксель = 1 узел графа, но при большом размере схемы (например, 1000x1000 дает миллион узлов графа) алгоритмы тормозят (500x500 обрабатывается за 300-500 мс в зависимости от выбранного алгоритма).
Подскажите пожалуйста, как можно реализовать данную функциональность для линий? Подумывал об использовании более эффективных реализаций A* - HPA* или JPS, но, мне кажется, использовать pathfinding алгоритмы для этой цели нерационально и есть более простой и эффективный метод решения.
WTFAYD, И вы прям будете втискивать линию между двумя блоками, даже если они так плотно друг к другу стоят? :) Андрей Федосеев дал вам серьёзный совет, через вопрос. Не надо рассматривать схему как сетку с размером в один пиксель. Будет шаг сетки 1 пиксель или 5 - существенной роли не играет, но количество узлов сокращается в 25 раз! После такой "грубой" оптимизации уже можете думать про более тонкую. А пока всё что вы делаете - это из разряда "Я отрезал 50 кусочков от колбасы. Как мне по-быстрому снять с них со всех кожуру?".
Lander. Не могу понять, как это - нет существенной разницы между размером шага сетки. Вы имеете в виду шаг в 5 пикселей - это расстояние между ячейками (которые представляют собой 1 пиксель), или полноценные тайлы 5x5?
WTFAYD, Не путайте одно с другим. Сам "лист" может быть устроен как угодно, хоть сеткой шагом в 0,1 пиксель! А при поиске пути, можете на него "накладывать" 5-ти пиксельную сетку и помечать в ней занятые области. Таким образом снижая число вершин для алгоритма поиска пути.
Lander, Допустим. Но как определить занятую область? Если, например, с левой стороны квадрата 5х5 можно подойти к финишной точке, а с правой - нет из-за препятствий внутри большого квадрата. Это занятая или свободная область? Если занятая, то, получается, до финиша дойти невозможно (заход с левой стороны). Если свободная, то мы пройдем сквозь препятствие (заход с правой стороны).
делали что-то похожее - сетка 1000*1000,
можно выбрать область любого размера, например 20*49.
следующий выбор обрабатывается с учетом, чтобы не разрешать пересекаться с уже выбранными областями.
плюс выбор РАЗМЕРОВ, т.е. задаю размер - например, 1*4 - скрипт сам подбирает первое сверху место по вместимости среди уже выбранных областей.
там все ячейки хранились в БД, скрипт вытаскивал свободные и дальше безумные расчеты)))
если интересно, то поищу, просто так лазить в закромах нет никакого желания)))
Средний
