обход препятствий

Здравствуйте, передо мной стоит следующая задача. Есть алгоритм муравья, реализованный на Visual C++ 6.0. Алгоритм находит кратчайшее расстояние между n объектами на плоскости. Нужно добавить возможность обхода алгоритмом препятствий. В частности, препятствий в виде квадратного, треугольного и восмьугольного графа.
Для начала я решил решить упрощенную задачу из 2 городов и 3 препятсвий, которая представлена на вложенном рисунке.

Координаты каждой точки задаются на плоскости 100 на 100. Муравью нужно перейти из точки 1 в точку 17, передвигаться он может только по узлам графов. Теперь вопрос: как запретить муравью передвигаться внутри препятствий? То есть из точки он может перейти в точки 6 и 8, но не может перейти в точки 7, 10, 9, 16 и т.д. Как запретить ему это сделать?
На ум приходит только простой перебор всех разрешенных и запрещенных вариантов для каждой точки, но препятствия могут появляться на пути муравья уже в процессе работы алгоритма, поэтому нужно придумать какую-нибудь универсальную функцию, которая бы определяла, пересек муравей границу препятствия или нет.
Как это можно реализовать?

Миниатюры

 

0

Вижу на картинке пять графов и не понимаю, как ты между их узам ходить собрался.
И не понимаю, что за стрелочки внутри препятствий...

0

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

Как я собрался ходить по узлам графа: от точки 1 до точки 17 можно пройти так:
1-6-7-16-15-14-17
или
1-4-11-12-17

0

Из 1 в 16 будет короче путь.
Говорю же, не понятно задание ни фига.

0

Найти кратчайшее расстояние между двумя объектами на плоскости.

0