Основное условие, линии должны быть по максимуму "горизонтально-вертикальными", никаких диагональных или кривых линий.
Мой модифицированный алгоритм прокладывает путь, как показано красным цветом на рисунке.

А как сделать эвристику такой, чтобы он шёл, как показано синей линий? Что мне учесть и в какой последовательности? Этот путь визуально лучше и, возможно, оптимальнее.

Спасибо за ответы.

Спасибо за ответы.

Я забыл написать кратко описание задачи. Есть два прямоугольника + препятсвия. Каждый из них имеет 4 точки соединения: левую, верхнюю, правую, нижнюю. Нужно соединить прямоугольники "горизонтально-вертикальными" линиями от одной точки к другой, обходя препятсвия.

Aleksandr Sharahov:
Практически Ваши предложения включены в функции вычисления веса точки. Только вот посленее (не ломать путь, если есть путь той же длины в прежнем направлении) пока не уверен, что знаю как реализовать.

Пётр Седов:
1. Ну графа нет, но есть инкапсулированный двумерный масив точек, Открытый и Закрытый списки, как в описании алгоритма. Считайте левую содинительную точку прямоугольника началом и нижнюю правого - концом.
2. Синий путь, конечно же, не кратчайший. Но так и A* ищет кратчайший путь зависимо от заданной эвристики. Потому и он и есть относительно кратчайшим.

Edd.Dragon:
Как-то так, красочно Вы описали принцим работы искомого алгоритма. )
Но да.

Edd.DragonModAStarEdd.Dragon:
Как-то так, красочно Вы описали принцим работы искомого алгоритма. )
Но да.

Ну я вижу его реализацию примерно так:

1. Сначала надо таки добиться, чтобы линия не ломалась, когда в этом нет смысла (т.е. не стремилась подобраться к конечной координате как можно раньше).

2. После этого обрамляем исходные прямоугольники желаемым "паддингом" (делаем их больше) и уже от них строим линию.
3. Паддинги убираются, добавляются 2 недостающих сегмента и вуаля:



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

Спасибо за идею, рациональное зерно здесь есть.

Пётр Седов2 ModAStar:

ModAStarЕсть два прямоугольника + препятсвия.
Какую форму имеют препятствия -- прямоугольники (выровненные по осям), выпуклые многоугольники, произвольные многоугольники? Препятствие может пересекаться со стартовым/финишным прямоугольником? С другими препятствиями? Можно идти прямо по краю препятствия (вплотную), или лучше держаться поодаль?

ModAStarНу графа нет, но есть инкапсулированный двумерный масив точек,
Множество точек жёстко задано условием задачи, или введено искусственно, просто чтобы был граф для алгоритма A*? (который всегда работает на графе, даже если у вас в программе отсутствует класс Graph) Когда поворачиваем на 90 градусов, можно это делать в местах с произвольными вещественными координатами x, y? (если да, то получается поиск пути в непрерывном пространстве, и можно подумать об алгоритме, который не будет искусственно сводить его к дискретному пространству)

Препятствие может быть практически любой формы.

Множество точек сгенерировано искуственно под A*. Посему, если поделитесь каким-то более походящим алгоритмом, буду безмерно благодарен.

Пётр Седов2 ModAStar:

Может быть не колдовать с эвристикой алгоритма A*, а преобразовать полученный путь, чтобы в нём было как можно меньше поворотов на 90 градусов? (см. приложенную картинку)

ModAStarПрепятствие может быть практически любой формы.

Множество точек сгенерировано искуственно под A*. Посему, если поделитесь каким-то более походящим алгоритмом, буду безмерно благодарен.
Раз вам нужен путь, состоящий из строго горизонтальных/вертикальных отрезков, то дискретный способ (граф точек на регулярной сетке) может быть даже лучше, чем возиться с непрерывным пространством, где препятствия произвольной формы.
Да, я генерирую дискретное множество, с ним и работаю.
За идею упрощения отрезков, используя количество поворотов, спасибо, использовал в А*, работает отлично. ;)

Всем спасибо за обсуждение. Алгоритм практически готов на 95%, эвристику подобрал, результатом и скоростью доволен.
Кстати, тормоза в скорости работы алгоритма были из-за неоптимизированной логики вычисления пересечений отрезка с объектами.
Но, слава Богу, глаза узрели и разум осилил сие. :)

Ещё раз всем спасибо! Вы все мне очень помогли.