Генерация маршрутов

[LSA]

Добавлю и я свои 5 копеек...
Проблема прокладки маршрута красиво решается с использованием теории графов. Припоминаю, что в свое время на третьем курсе я писал курсовую работу - программу на PL/1, которая реализовывала алгоритм нахождение пути в лабиринте. Вкратце суть сводится к следующему: лабиринт описывается в виде матрицы графа, затем производится "взвешивание" этого графа относительно конечной точки маршрута, после чего берется начальная точка и маршрут получается практически сам собой, простым "подъемом" по взвешенному дереву графа (по сути при формировании пути останется решать только задачу выбора пути из двух или более вариантов).
Как я понимаю, отрезки и узловые точки дорожной сети тем или иным способом вы уже получили, т.е. налицо та самая матрица. Ребра графа в данном случае могут хранить отрезки дорог (в общем случае это ломаные линии) между перекрестками, что даст возможность прокладывать маршруты не только по критерию "самый короткий путь".
Думаю, что этот метод и реализован в редакторе

[LePage]

Сообщение от LSA

Добавлю и я свои 5 копеек...
Проблема прокладки маршрута красиво решается с использованием теории графов. Припоминаю, что в свое время на третьем курсе я писал курсовую работу - программу на PL/1, которая реализовывала алгоритм нахождение пути в лабиринте. Вкратце суть сводится к следующему: лабиринт описывается в виде матрицы графа, затем производится "взвешивание" этого графа относительно конечной точки маршрута, после чего берется начальная точка и маршрут получается практически сам собой, простым "подъемом" по взвешенному дереву графа (по сути при формировании пути останется решать только задачу выбора пути из двух или более вариантов).
Как я понимаю, отрезки и узловые точки дорожной сети тем или иным способом вы уже получили, т.е. налицо та самая матрица. Ребра графа в данном случае могут хранить отрезки дорог (в общем случае это ломаные линии) между перекрестками, что даст возможность прокладывать маршруты не только по критерию "самый короткий путь".
Думаю, что этот метод и реализован в редакторе

Это будет работать, если дороги связаны в один независимый граф, а может быть ситуация когда существует несколько независимых графов (лабиринт в лабиринте, с изолированным входом/ выходом), карты же обрезаны. Нужен еще алгоритм вычленения независимых графов из массива отрезков.
(я эту теорию уже благополучно забыл , хотя аналогичную курсовую делал, поиск всех возможных путей в графе, с исключением циклов)

з/ы/ Перечитал и подумал мож и не так все сложно. Ведь все предполагается ИМХО для проекта когда колонна движется из НАЧАЛЬНОЙ точки самой первой миссии - значит вход в лабиринт есть и он один. К остальным независимым маршрутам (если они существуют) наземка поедет по «бездорожью».
Хотя нет - все равно придется искать ближайшую дорогу.