|
|
|||||
Регистрация: Nov 2010
Адрес: Ярославль
Сообщений: 249
|
Генерация лабиринта
Здравствуйте. Недавно наткнулся на приложение вконтакте с лабиринтом. Сначала набираются 2 команды по 3-4 человека и генерируется карта-лабиринт. Цель каждой команды первыми добраться до базы противника. Если кому интересно, вот приложение: http://vkontakte.ru/maze1.
Так вот, меня как-то вдохновило это приложение, и появилось желание создать что-то подобное. И первый вопрос, который возникает - как сгенерировать подобный лабиринт. Попробовал сделать через "блуждание" от начальной точки к конечной, но получается совсем не так, как хотелось бы. Можете что-нибудь посоветовать? Внесу несколько уточнений: Путь от одной базы к другой один, но, во-первых, он очень ветвится, а во-вторых, даже если базы находятся на небольшом расстоянии друг от друга, сам путь по-прежнему остаётся длинным и запутанным. Последний раз редактировалось Parez; 03.01.2012 в 15:16. |
|
|||||
Регистрация: Nov 2010
Адрес: Ярославль
Сообщений: 249
|
fish_r, нет, так не интересно. Просто, если кто-то здесь уже примерно знает или есть какие-нибудь идеи, это могло бы сократить время на придумывание алгоритма..
Нашёл статью в английской википедии. Попробую разобраться... Последний раз редактировалось Parez; 03.01.2012 в 17:00. |
|
|||||
Регистрация: Dec 2006
Сообщений: 1,764
|
конечно попробуй, можешь даже вступить в диалог с разработчиками http://vkontakte.ru/maze1, я думаю могут помочь
__________________
а за окном атлантический океан! |
|
|||||
Регистрация: Nov 2010
Адрес: Ярославль
Сообщений: 249
|
Ещё кое-что.. Вот щас читаю статью в википедии http://en.wikipedia.org/wiki/Maze_ge...h-first_search. Алгоритм Depth-first_search. И я не совсем понял, как лучше представлять ячейки лабиринта... Там написано:
Цитата:
|
|
|||||
вот тут 3 алгоритма генерации лабиринтов
http://wonderfl.net/c/v7Vh
__________________
Хороший отдых - половина работы. |
|
|||||
Цитата:
|
|
|||||
Modus ponens
|
Алгоритм, принципиально, похож на судоку, т.е. те же методы решения, только условие другое. Или, если сильно упростить - крестики-нолики. Т.е. принцип примерно следующий: перешли в первый квадрат, сделали случайный выбор из четрыех за вычетом уже опробованых направлений, куда идти дальше, если опробованы все направления, делаем еще шаг назад. Перешли в следующий, проверили решаемость лабиринта, если не решается, - идем шаг назад, и повторяем.
Так же как судоку можно абстрагировать до работы с сетами и функцией определенной на сете всех возможных переходов, последовательно "скармливая" такой функции возможные комбинации и проверяя решаемость - наверное будет оптимальный вариант. EDIT: Еще подумалось о алгоритме: берем перлин шум, и с его помощью изначально заполняем доску, проверяем решаемость, если решается, добавляем еще шум, и так по кругу. Можно еще какую-инбудь логистику добавить, чтобы, например, если есть почти решаемый вариант, убирать ранее добавленный шум так, чтобы вариант становился решаемым, и добавлять шум еще раз.
__________________
Hell is the possibility of sanity Последний раз редактировалось wvxvw; 04.01.2012 в 01:39. |
|
|||||
Регистрация: Jul 2011
Сообщений: 67
|
Хмм... Лабиринт ведь концептуально состоит из: начала, конца, коридоров, поворотов, развилок/перекрёстков и тупиков. Можно сначала рандомно выстроить истинный путь, без тупиков, а потом достроить тупиковые ветки. Так можно будет отделить модель лабиринта от его представления. Нарисовать круглый лабиринт например. Или нет?
|
Часовой пояс GMT +4, время: 07:41. |
|
« Предыдущая тема | Следующая тема » |
Теги |
maze , лабиринт |
|
|