Генерация лабиринта

[Parez]

Здравствуйте. Недавно наткнулся на приложение вконтакте с лабиринтом. Сначала набираются 2 команды по 3-4 человека и генерируется карта-лабиринт. Цель каждой команды первыми добраться до базы противника. Если кому интересно, вот приложение: http://vkontakte.ru/maze1.
Так вот, меня как-то вдохновило это приложение, и появилось желание создать что-то подобное. И первый вопрос, который возникает - как сгенерировать подобный лабиринт. Попробовал сделать через "блуждание" от начальной точки к конечной, но получается совсем не так, как хотелось бы. Можете что-нибудь посоветовать?

Внесу несколько уточнений:
Путь от одной базы к другой один, но, во-первых, он очень ветвится, а во-вторых, даже если базы находятся на небольшом расстоянии друг от друга, сам путь по-прежнему остаётся длинным и запутанным.

[fish_r]

если не знаете как сгенерировать, то может набросать десяток, другой шаблонов. Чем не выход?

[Parez]

fish_r, нет, так не интересно. Просто, если кто-то здесь уже примерно знает или есть какие-нибудь идеи, это могло бы сократить время на придумывание алгоритма..
Нашёл статью в английской википедии. Попробую разобраться...

[NikolyA]

конечно попробуй, можешь даже вступить в диалог с разработчиками http://vkontakte.ru/maze1, я думаю могут помочь

[Parez]

Ещё кое-что.. Вот щас читаю статью в википедии http://en.wikipedia.org/wiki/Maze_ge...h-first_search. Алгоритм Depth-first_search. И я не совсем понял, как лучше представлять ячейки лабиринта... Там написано:

Consider the space for a maze being a large grid of cells (like a large chess board), each cell starting with four walls

То есть, как я понял, изначально каждая ячейка - это квадрат 2x2 из стен? Но тогда какой-то бред получается... Не подскажете как следует понимать эту цитату из википедии?

[artcraft]

вот тут 3 алгоритма генерации лабиринтов
http://wonderfl.net/c/v7Vh

[fish_r]

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

вот тут 3 алгоритма генерации лабиринтов
http://wonderfl.net/c/v7Vh

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

[wvxvw]

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

EDIT: Еще подумалось о алгоритме: берем перлин шум, и с его помощью изначально заполняем доску, проверяем решаемость, если решается, добавляем еще шум, и так по кругу. Можно еще какую-инбудь логистику добавить, чтобы, например, если есть почти решаемый вариант, убирать ранее добавленный шум так, чтобы вариант становился решаемым, и добавлять шум еще раз.

[artcraft]

сложность лабиринта можно оценить по количеству развилок от входа до выхода
и по количеству возможных путей прохождения

[ProxyGreen]

Хмм... Лабиринт ведь концептуально состоит из: начала, конца, коридоров, поворотов, развилок/перекрёстков и тупиков. Можно сначала рандомно выстроить истинный путь, без тупиков, а потом достроить тупиковые ветки. Так можно будет отделить модель лабиринта от его представления. Нарисовать круглый лабиринт например. Или нет?