Russian Qt Forum

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

А почему вдруг AStar не подходит? Даже если у тебя шахматная доска, это все-равно граф. Область из ячеек - тем более граф. А для обхода графов очень мало алгоритмов и AStar один из лучших. AStar'ом анализируют кратчайшие пути на геокартах. Не думаю, что твой граф сложнее геокарт.

И что еще не совсем понятно. Какие точки должны быть соеденины? Это должны быть только прямые или ломаные отрезки?

Вообще, задача описана очень плохо. Приципи картинку со своими точками.

Привет. Спасибо за ответ. Вот уже неделю мучаюсь. Какое-то решение уже есть, но очень кривое и пока не работающее  :(


Блок у меня - это квадрат. У него есть входа и выход. Соединяют выход одного блока и вход другого блока.

Это ломанные отрезки с прямыми углами.

Все проблемма в том, что я немного не понимаю. У меня не шахматная доска, а просто плоскость.

И все-таки тут бинго. Попробую разбить плоскость, как шаматную доску и действительно применить AStar. Ведь если геокарты так делают, то значит дурак тут точно я, а не моя проблема. Есть еще предположение двигать блоки не произвольно по плоскости, а по клеточкам. Это решит очень сильно проблему.
 
Спасибо за наводку буду работать в этом направлении.

У каждого твоего блока есть центр с определенными координатами. Нужно создать структуру данных описывающую граф соостоящий из координат *(пары x,y) этих блоков. Таким образом отпадет необходимость разбивать все на клетки. Геокарты тоже не на клетки разбиты, а используют градусы, минуты и секунды для определения положения. Правда это уже тоже не самая актуальная фишка.
Таким образом при перемещении блоков, сам граф меняться не будет, так как количество узлов в графе будет оставаться постоянным (или пусть даже будет меняться - все равно), а значения координат для узлов будут менятья.
Обходя граф алгоритмом можно находить кратчайший путь от входа к выходу. Хотя, скажу честно, я  так и не понял - нужно искать кратчайший путь от заданного выхода до ближайшего входа? Если да, то при инициализации графа можно сразу сделать его взвешеным и потом алгоритм будет пролетать пару миллионов узлов за доли секунды. (в зависимости от процессора и серды исполнения, конечно). При этом только важно учитывать динамическое изменине положения узлов и оптимально реинициализировать веса графа во врмея смены положения узлов.

Была тут недавно эпопея с прокладкой таких путей, товарищ "летел через овраг" (ну не знаю долетел ли). Мне тоже предстоит задача где есть соединение выходов со входами. Просмотрев десяток подобных приложений увидел что никто из них "прокладкой" не занимается. Просто соединяют кривой (эрмитный переход), иногда на кривой одна точка чтобы юзер мог рулить. Пересеклось так пересеклось - юзер руками поправит. Думается это правильно. Возни с "автоматом" много, а толку чуть. Тот же AStar будет искать кратчайший по диагонали и выдаст "лесенку". Или вообще пересечение неизбежно.

Да, графы без пересечений могут только в трехмерности существовать, да и то не все.