Цитата:
Сообщение от LSA
Добавлю и я свои 5 копеек... 
Проблема прокладки маршрута красиво решается с использованием теории графов. Припоминаю, что в свое время на третьем курсе я писал курсовую работу - программу на PL/1, которая реализовывала алгоритм нахождение пути в лабиринте. Вкратце суть сводится к следующему: лабиринт описывается в виде матрицы графа, затем производится "взвешивание" этого графа относительно конечной точки маршрута, после чего берется начальная точка и маршрут получается практически сам собой, простым "подъемом" по взвешенному дереву графа (по сути при формировании пути останется решать только задачу выбора пути из двух или более вариантов).
Как я понимаю, отрезки и узловые точки дорожной сети тем или иным способом вы уже получили, т.е. налицо та самая матрица. Ребра графа в данном случае могут хранить отрезки дорог (в общем случае это ломаные линии) между перекрестками, что даст возможность прокладывать маршруты не только по критерию "самый короткий путь".
Думаю, что этот метод и реализован в редакторе |
Это будет работать, если дороги связаны в один независимый граф, а может быть ситуация когда существует несколько независимых графов (лабиринт в лабиринте, с изолированным входом/ выходом), карты же обрезаны. Нужен еще алгоритм вычленения независимых графов из массива отрезков.
(я эту теорию уже благополучно забыл
, хотя аналогичную курсовую делал, поиск всех возможных путей в графе, с исключением циклов)
з/ы/ Перечитал и подумал мож и не так все сложно. Ведь все предполагается ИМХО для проекта когда колонна движется из НАЧАЛЬНОЙ точки самой первой миссии - значит вход в лабиринт есть и он один. К остальным независимым маршрутам (если они существуют) наземка поедет по «бездорожью».
Хотя нет - все равно придется искать ближайшую дорогу.