Без обхода "препятствий" и прочих заморочек с допустимостью прокладывания маршрута задача действительно тривиальная. Общее решение - это "черепашка", движущаяся по кратчайшему маршруту по сетке между двумя удаленными QPointF. Я решил хранить только QList<ConnectionSegment>, где ConnectionSegment это QGraphicsLineItem с будущими дополнительными возможностями (реакцией на события). Черепашка перед каждым шагом вычисляет наиболее выгодное направление следующего шага, одно из четырех возможных. Это просто - берем 4 соседние точки, и находим ту, расстояние от которой до целевой минимальное (таких 2, но одна найдется первой, и в моем случае это будет вариант по горизонтали). После чего рекурсивно делает шаг в этом направлении, то есть, переходит на соответствующую точку. При выполнении шага передается предыдущее направление (в виде целого числа от 0 до 3), и если при вычислении следующего шага оно не совпало с предыдущим - значит это поворот, его точка сохранятся в локальной переменной и взводится локальный флаг поворота. Если достигли конечной точки пути, то возврат из рекурсии и возвращаются координаты точки, от которой произошел возврат. Вызывающая функция получает их, и если у неё есть флаг поворота, то рисует отрезок от сохраненной точки поворота, до полученной, после чего возвращает свою точку поворота. Если флага поворота нет, то просто возвращает полученную из рекурсивного вызова точку (движение по прямой).

Таким образом, алгоритм рекурсивно проходит от начала к концу, находит точки поворота, и потом на возврате рисует отрезки. Поскольку у меня по задаче входы и выходы объектов всегда расположены слева и справа графических айтемов (никогда внизу или наверху), то без учета препятствий алгоритм будет рисовать линии только из 1-го, или 2-х отрезков. Но, как я уже сказал, это по задаче не нужно.

Гораздо сложнее, когда есть разнообразные препятствия. Характер этих препятствий разный, и отдельная проблема их правильно определять. Пока я учитываю только 2 типа препятствий - область на 1 шаг сетки больше границ каждого объекта, и недопустимость наложения линий на уже проложенные (допустимо только пересекать их под прямым углом). Основа алгоритма черепашки остается почти такой же, но в него вводится проверка допустимости шага и исключения недопустимых направлений. А также, если алгоритм заехал в тупик, то появляется дополнительный выход из рекурсии, с установкой флага запрещенного направления, и после каждого возврата алгоритм пытается заново определить выгодное направление, но то, в котором он побывал, становится запрещенным. Это всё значительно сложнее, поэтому я сейчас решаю именно эту задачу, и она не решается отдельно. Запрет пройденного направления "встроен" в простой алгоритм черепашки.

Мой алгоритм в данном случае пойдет по синей линии. Хотя, конечно, могут быть случаи, когда оптимизация не повредила бы. Но за это заказчик должен будет дополнительно заплатить... 

Тут сетки нет, не видно, где можно пройти, где нет.

По идее, алгоритм "черепашки" с учетом препятствий - это почти тот же PacMan. В конце 90-х я его сам написал, у меня была своя версия PacMan для любого лабиринта, работал идеально, произвольные лабиринты можно было в текстовом редакторе рисовать. 4 "призрака" ловили ПакМана со 100% гарантией. То есть, алгоритм, который точно "найдет" целевую точку, я уже делал. Вот я по аналогии пытаюсь сейчас сделать, естественно, с использованием Qt. И рекурсивно, тот алгоритм был одноуровневым циклом.

Я не видел ни одной 100% оптимальной реализации подобного роутинга в каком-либо софте, который его имеет. Хорошую детальную теорию по этому вопросу я не нашел даже на английском. Достаточно спросить у любого конструктора, которые пользуются Altium Designer (ex P-CAD), где это проработано лучше всего - все конструктора и радио-инженеры предпочитают рисовать схемы наполовину вручную, не говоря уже о разводке плат (я знаю их ответ, потому что работал с ними на соседнем этаже). Автоматические средства используют только для того, чтобы немного сэкономить время, не таскать все провода изначально. То есть, даже в этом дорогом коммерческом пакете автоматика не идеальна. Некая простая автоматическая оптимизация постфактум возможна, но наиболее эффективным будет возможностью пользователю редактировать сделанную автоматически разводку вручную. То есть, когда пользователь что-то соединяет, оно автоматом прокладывает линии, но если не понравилось, можно их поменять, создавая новые изгибы и двигая отрезки. Это тоже планируется. Увы, придётся еще колбасить сохранение и загрузку схем, чтобы детально все линии сохранялись.

Ну это банально. Разумеется, именно так и сделано. Если роутинг вернулся в начальную точку с ошибкой "тупик", ругается, что не смог провести линию, надо переместить объект. На будущее можно еще подумать над автоматическим перемещением объектов, если роутинг не выполнился.


я же сказал  - если я знаю, что могу в один

Всё там прозвучало, повторять не буду. Дальше на возврате из рекурсии он рисуется. И всё. Каждый сегмент будет ловить события мыши и путь будет позволять себя модифицировать. Больше пока ничего не надо.