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

Тут вроде наиболее близкая тема для моего вопроса:

Имеем мод Zuti
Стоит задача в генераторе миссий сгенерировать маршрут для транспорта, чтоб он шел по дороге.
Есть уже проверенные способы или какие идеи для этого?
На дороге используются только точки поворотов.
Самый простой способ, это нарисовать в ПР несколько маршрутов и затем вставлять их.. но это прокатит для статичных карт. Для динамичных же, для разнообразия маршрутов, необходимо рисовать много десятков маршрутов, на некоторых - за сотню. Трудоемко.
Без привязки к дорогам можно делать, но не айс. То по лесам, то по полям, то по воде поедут. Дополнительная проблема - привязка к мостам.

Повторяю - задача для автоматической генерации точек, имея начало и конец.

Это который? :I'm_thinking:

Который по движущейся наземке для догфайта.
Да не в нем суть. А в том что появилась возможность запустить колонны ехать, но не по заранее нарисованным в ПР маршрутам, а чтоб софт генерил маршруты в файл mis. По двум точкам - начало и конец.
Вопрос не совсем в тему форума, но именно тут тусуются креативщики. Не на сухом же спрашивать... :)

Ну, на самом деле, получается, что маршрут нужно не генерировать, а выбирать :rolleyes: Выбирать из некоего множества, которое, скажем так, ограничено сеткой дорог. Сетку можно вытащить из map_T.tga, воспользовавшись утилиткой от mr N. Ну а далее задача, насколько я понимаю, превращается в чисто математическую.

Это я уже обсасывал. Утилитка дает только дороги. Причем она рисует их а не вырезает.
Для маршрута же необходимы именно точки поворотов. Это сокращает значительно объем данных. Вот если б вытащить повороты только.. это значительно облегчит задачу.
Но и в этом случае боюсь время обсчета будет значительным. Хотя, и не столь критичным.

Тут примерно посчитал. Чтоб на Крым сделать достаточное количество маршрутов - придется минимум 60-80 маршрутов нарисовать.
Но пока это самый реальный способ, учитывая мосты.

Ну, идея-то есть. В полном редакторе уже есть код поиска пути. Даже примерно понятно где он там (классы Path, PPoint, PNodes, PathFind). Но там все несколько запутано, так сразу не совсем понятно как это применить вне полного редактора.

Нуу.. туда мне не добраться. Я понимаю, что редактор использует или тот же tga или что-то похожее, и + статики мостов.
Вот выдрать бы алгоритм - в редакторе это делается двумя инсертами - начало и конец, все остальное софт.

А если проложить маршруты в редакторе?
Хотя бы по основным дорогам. Тупо, в ручную, из одного края к другому.
Там же будут все повороты и мосты.
Останется только все это отсортировать и можно генерить маршруты.
Ну и наконец, как-то же редактор их создает, значит копая глубже можно вытащить вообще сам алгоритм и прикрутить его к генератору миссий.

А, уже написали.

Это я уже сделал. Получил несколько списков
Попробовал такой алгоритм:
беру точку старта. Ищу к ней ближайшую на дороге ( неоптимизировано, долго ищу) Затем от неё в ту или другую сторона по списку тупо копирую точки. тут проблема - посчитать дистанцию, пока только по прямой между стартом и следующей точкой. Но вот например провести маршрут имея 2 точки - два города например.. тут уже клинит мою голову. Только перебор - обсчитываем несколько маршрутов и берем тот который ближе всего подходит..
черт.. такие массивы получаются...

Вручную тяжко будет.
Гляньте на карту Нормандия1 хотя бы.


з/ы/ перебор маршрутов это из теории графов - алгоритм не сильно сложный (вложенные циклы, рекурсивные вызовы + стек). Сложнее построить сам граф, все его отрезки от поворота до поворота и точки ветвлений (перекрестки). Грубо говоря, оцифровать все дороги. Вот как это сделать на автомате, пока не представляю. :I'm_thinking:

Тут можно подойти так - "хватит и 10 колонн на карте", и тогда проблем нет. Но если делать что-то более красивое и логичное, колонны направлять от складов и заводов к точкам снабжения, а пункты меняются каждую миссию, На ГФ, например, если место позволяет. то точки для целей находятся в каждом квадрате, да и не по одной зачастую...

Можно конечно попробовать провести трассировку дорог из map_T.tga на предмет точек поворота.
Вопрос - кто знает - к чему привязаны координаты в Иле?

Что значит к чему? 1 пиксел = 200 метрам на map_t

Как сказать ... Кнопки Save As... в блоках дорог сохраняют дороги из map_t в виде отдельных файлов (они там нарисованы черным по белому) ;) Тобто получается 2-битный файл и сделать трассировку такого, ПМСМ, задача для программера не из сложных ... я так думаю (с) :rolleyes:

А, это да. Но я программер-самоучка поневоле. Для меня сложно.

Грубо говоря верхний левый угол 00000.00 00000.00
Правый нижний хххххх.00 ххххх.00
Я имею ввиду те координаты что стоят в файле миссии:
(пример)
[0_Chief_Road]
500.00 43500.00 20.00 0 70 5.555555820465088
6300.00 43500.00 20.00
6500.00 43700.00 20.00
9900.00 43700.00 20.00
10100.00 43900.00 20.00
....
и все это в метрах?

0 = левый нижний угол.
Цифры в метрах.

Упс :I'm_thinking: Тогда видится два варианта ... Или привлекать SJack'а (прошу простить великодушно, что в третьем лице :ups: ) - товарищ, как-никак, программер, или идти на поклон к народу, поддерживающему нынче АДВ - там ведь, ЕМНИП, колонны путешествуют по карте ... нет?

Жив разве еще АДВ?
Не.. на поклон не пойду никуда. Лоб уже расшиб. Сделаю как смогу.
Я только подсказки прошу.

С АДВшным софтом скорее всего никто не поможет....:)
Сами ГТ не дадут, а админам с АДВ не разрешат давать....

По большому счету - никто ничего давать не хочет. Пообщался я с парой проектов. Мне, который 5 лет занимается проектами, куски моего кода на половине серверов, говорят "А что с этого буду иметь..." Аж противно стало, до чего люди с короткой памятью.

Что-то я не уловил, если пиксели на map_t.tga с шагом 200 м то почему же координаты точек маршрута не кратны 200-м?
500.00 43500.00 20.00 0 70 5.555555820465088
6300.00 43500.00 20.00
6500.00 43700.00 20.00
:I'm_thinking:


И еще, просто интересно, а с ботами как быть предполагается, или уж совсем без них?

Дороги "нарезаются" отрезками по 200 м, но точка маршрута м. б. в любом месте отрезка.

Офигел чтоль... :)
6500 - 6300 = 200
43700 - 43500 = 200
Это от начальной точки может быть по всякому.
А то что 500 а не 400 - так и надо. Отсчет то полпиксела учитывает, видимо. Т.е. если линия идет посередине квадратного пиксела ( 200х200м) то как раз смещение на половину.

Боты обязательно.

Вот это и интересовало, спасибо. т.е поправочка нужна при трассировке - сдвиг начала координат (100,100).

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

Трассировка tga? Это ползадачи, надо еще мосты привязывать. У каждого моста свой номер и координаты.
Нужен алгоритм итоговый...

Хотя.. вроде уже понимаю как надо сделать.
Спасибо LSA, подтолкнул мысли - надо брать отрезки, а не вершины для расчета..
Если коротко:
Надо найти все отрезки дорог в один список (X1,Y1,I1 ;X2,Y2,I2) , где I - идентификатор точки.
Вот это один отрезок:
[[7300.00, 50900.00, 20.00], [7500.00, 50700.00, -42.00]]
У нас будет один список с такими отрезками, его получить надо с mis
Делаем в ПН "штриховку" 1 или более длииииными маршрутами
Утилитой формируем список - удаляем дубли. Готов тхт файл (или в другом виде)
При генерации находим ближайшую вершину, Берем отрезок и пошли перебором, взяли конец - нашли начало другого, + в маршрут. При нахождении "перекрестка" определяем отрезок, конечная точка которого ближе к таргет, берем его и пошли дальше. Если последняя координата не повторяется - это конец дороге.
Прикинул - это будет достаточно быстро. Ну и так далее, дело техники.
Утилиту по парсеру *.mis кто-то может собрать по быстрому? Её назначение парсинг, удаление дублей в том числе и (x,y) = (y,x)
Вывод в формате

a b
b c
c d
с а
с f
f b
.........

6300.00 51700.00 20.00 6500.00 51700.00 20.00
6500.00 51700.00 20.00 7300.00 50900.00 20.00
7300.00 50900.00 20.00 7500.00 50700.00 -42.00
.........

Вуаля. Обработку этого файла уж каждый проект будет делать по своему. Могу себе утилитку сделать и на Питоне, но если будет *.exe, это будет универсальный парсер маршрутов для общего пользования.

список только точек сам по себе бесполезен

Ндык координаты мостов (вернее, начала и конца моста, как оне, собственно и отражаются в маршруте) содержатся в outWing.txt (тот, который получается на выходе java -jar Act.jar extract ), а номер ... зачем он?

да уже ненадо. А вобще, номер пишется как -XX. Я так понял.
7500.00 50700.00 -42.00

Вроде же делал такую для тебя неск. лет назад на Питоне.
Поищу.

А... Ты наверно из Мурманска :)
Я ж сказал - для всех :)
Зачем другим ставить для одной утилитки питон?
На питоне то я и сам сделаю, всё что нужно уже есть. Наверно на выходных, как с маршрутами для ботов закончу.

Я про сортировщик.
А про генератор маршрутов, "для всех" нужен только алгоритм - кто на чем хочет, на том закодирует и прикрутит к своему остальному софту.

П.С. А на Питоне тоже можно делать исполняемые файлы .exe

Хм, а парсер лога сервера нигде не завалялся? На чем угодно. В декомпилировании несилен.... :(

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

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

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

А ссылочку на подобный исходник мона? В личку или по аське 404-132-377, если что. (вообще говоря интересует все что сервер там пишет, интерпретация событий, все ж ситуации я сам не смогу вооспроизвести :()

Да канечно. Вот на Питоне

Спасибо!!!

Получилось в общем-то. Запустил на ГФ.
Есть небольшие погрешности - при прокладывании маршрутов иногда срезаются углы. Чем точнее проложить маршруты для создания базы, тем точнее будет результат в миссии.

Чтоб не создавать отдельную тему:
Есть отдельный мод для "S" ? Нужно чтоб лог был(трекописание нужно обязательно), а всё о вражине отключено.