WoRmS.oRg.Ua

[player]

RR Generator

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

А ещё просьба перезалить на worms.org.ua, так как ссылка может исчезнуть.

[Баклажань]

знать бы как открыть эту прогу=(

[NickyNick]

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


...

[MoDErahN]

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

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


Мне кажется что из-за специфичности графа (ну фактически у нас получается решетка) можно как-то упростить поиск гамильтонова пути, но я никак не могу придумать как.
Если кто знает, плз скажите.