Как оптимизировать большой граф для алгоритмов поиска пути?

Question

Я разрабатываю небольшую программу, в которой пользователь может создавать простые диаграммы с абстрактными блоками, соединенными линиями, например, блок-схемы или структурные диаграммы.Одним из условий технического задания является то, что линии должны обходить другие блоки \ линии и не пересекать их во время движения.

Иллюстрация

Я пытался использовать алгоритмы поиска пути, такие как A * или алгоритм Ли для него и рассмотрим рабочее пространство (окно с элементами диаграммы) как график - один пиксель является одним узлом графика.Однако перемещение блоков \ линий вызывает значительную задержку по времени (например, поиск пути в рабочей области размером 500x500 занимает около 320-360 мс ).Кажется, что график слишком велик для этих алгоритмов.

Не могли бы вы сказать мне, как уменьшить количество узлов в этом случае?Может быть, есть способ ускорить эти алгоритмы или использовать для этого что-то другое?!

Answer 1

Не думайте об этом как о проблеме теории графов, думайте об этом как о проблеме физики.

Визуализируйте это следующим образом.У каждого блока есть определенная сила, тянущая его к последнему месту, где он был помещен.Сегменты линий, блоки и края графика отталкиваются друг от друга по закону обратных квадратов (за исключением того, что конец рисуемой линии не отталкивает блоки перед ним).При достаточном напряжении линейный сегмент может быть разбит на более мелкие линейные сегменты, которые стремятся вернуться в прямую линию.

Динамика сложная, но количество объектов - это количество объектов, которые вы видите наэкран, а не количество пикселей, на которых он нарисован.Поэтому вы сможете делать обновления относительно быстро.

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