Список форумов WoRmS.oRg.Ua WoRmS.oRg.Ua
червивый форум


  

rr generator
Создание и гинерирование карт Roper Race

 
Начать новую тему   Ответить на тему    Список форумов WoRmS.oRg.Ua -> •ПРОГРАММЫ•
Предыдущая тема :: Следующая тема  
player



Зарегистрирован: 08.04.2006
Сообщения: 539
Рейтинг: 14 [+/-*
Откуда: Russia, Samara
Медали: 1 (еще...)
рекордсмен миссий (Количество: 1)

 СообщениеДобавлено: Пт Июл 28, 2006 22:35    Заголовок сообщения: rr generator Ответить с цитатой Back to top

RR Generator

Весьма не плохая программа для гинерации карт roper race
Скачать

А ещё просьба перезалить на worms.org.ua, так как ссылка может исчезнуть.
Перейти наверх
Посмотреть профиль Отправить личное сообщение Отправить мыло Номер ICQ
Баклажань



Зарегистрирован: 30.07.2009
Сообщения: 19
Рейтинг: 0 [+/-*
Откуда: da
Ник на WormNet: Hock
Медали: Нет

 СообщениеДобавлено: Вт Авг 25, 2009 16:25    Заголовок сообщения: Ответить с цитатой Back to top

знать бы как открыть эту прогу=(
Перейти наверх
Посмотреть профиль Отправить личное сообщение Ник на WormNet
NickyNick
модератор



Зарегистрирован: 23.11.2007
Сообщения: 667
Рейтинг: 50 [+/-*
Откуда: Харьков
Играю в: W:A
Хостить: могу
Медали: Нет

 СообщениеДобавлено: Вт Авг 25, 2009 17:04    Заголовок сообщения: Ответить с цитатой Back to top

Это называется "архив". Для того, чтобы его открыть, тебе нужна специальная программа - архиватор. Например, Winrar. Внутри архива содержатся файлы, которые можно оттуда извлечь и далее пользоваться ими как обычно.


...
Перейти наверх
Посмотреть профиль Отправить личное сообщение Отправить мыло Номер ICQ
MoDErahN
программист



Зарегистрирован: 16.10.2008
Сообщения: 96
Рейтинг: 11 [+/-*
Откуда: Минск
Медали: Нет

 СообщениеДобавлено: Вс Авг 30, 2009 20:42    Заголовок сообщения: Ответить с цитатой Back to top

Я пытался автоматизировать построение RR карт, вот только затык получился.
Дело в том, что фактически RR карта это гамильтонов граф без одного ребра. Вершины в нем - клетки, а ребра - проходы между клетками.
Т.е. клетки в углах карты примыкают к двум ребрам, граничные клетки - к 3-м ребрам, а остальные к четырем. Выберем две вершины (старт и финиш). Для построения карты RR (т.е. максимально длинного лабиритна без тупиков и циклов) достаточно:
1) Ввести в наш граф дополнительное ребро между стартом и финишем.
2) Проверить граф на наличие гамильтонова пути, и если его нет, то удалить угловую вершину, получая таким образом граф с гамильтоновым путем.
3) Найти любой гамильтонов путь.

Вот в пункте 3 и скрывается весть 3.14..дец. Ибо нахождение гамильтонова пути это NP задача, и для карты размером 3*7 клеток (а это при стандартных размерах карты даст громадные проходы, ну представьте себе обычный WXW) получается 2^4 * 3^12 * 4^5 = 8 707 129 344 итераций, т.е. прога будет отрабатывать до второго пришествия.


Мне кажется что из-за специфичности графа (ну фактически у нас получается решетка) можно как-то упростить поиск гамильтонова пути, но я никак не могу придумать как.
Если кто знает, плз скажите.
Перейти наверх
Посмотреть профиль Отправить личное сообщение
Показать сообщения:   
Начать новую тему   Ответить на тему    Список форумов WoRmS.oRg.Ua -> •ПРОГРАММЫ• Часовой пояс: GMT +4:00
Страница 1 из 1

 
Перейти:  
Ты не можешь начинать темы
Ты не можешь отвечать на сообщения
Ты не можешь редактировать свои сообщения
Ты не можешь удалять свои сообщения
Ты не можешь голосовать в опросах