моя программа генерации лабиринтов на C++ с исходником, описанием алгоритма, с выводом результата работы в текстовый файл: http://zalil.ru/34340028 файл будет удалён через 10 дней после последнего скачивания.
и будьте бдительны: проверяйте файл на вирусы!
Добавлено (12.03.2013, 18:41) --------------------------------------------- получающиеся лабиринты не похожи на те, которые вы могли видеть в рогаликах. тем не менее, можно придумать игры, для которых именно такая генерация идеально подойдёт. получающиеся лабиринты похожи на лабиринты из синклеровской игрушки Maziacs.
ознакомьтесь с этим алгоритмом, если вас интересует генерация лабиринтов. если вы поймёте идею этого простого алгоритма, то сможете изменять или дорабатывать алгоритм по-своему.
например, можно было пробивать не по две клетки в выбранную сторону, а по одной. только тогда надо внимательно проверять соседние поля. мой алгоритм проверяет только одно поле- то, до которого пробивается. а если вы решите пробиваться по одной клетке, то необходимо предварительно проверить, что рядом с ней нет уже пробитых ранее полей. иначе вместо лабиринта может получиться открытая поляна.
дальнейшее развитие идеи в том, чтобы генерировать лабиринты с комнатами, как в рогаликах.
например, вы можете видеть это на второй картинке здесь.
Выложи на github а то не все будут качать неизвестно что, а так и посмотреть можно и багу запостить. Участвовал в разработке Order of War (C++ UI & логика) и WoT (Python портал worldoftanks.ru почти всё :-) )
посмотрел код прямоугольного лабиринта. код действительно очень прост, за счёт использования рекурсии. да, рекурсия рулит, если уметь её применять!
а я работал со списком.. впрочем, списки тоже хороши и удобны для решения широкого круга задач.
обычно списки организуют с помощью указателей. но многие игроделы используют скриптовые языки конструкторов, в которых указатели не предусмотрены. что тогда делать?
в этом случае список можно организовать с помощью достаточно большого массива и переменной, хранящей количество элементов "списка".
обычно смысл списка в том, что каждый элемент хранит какую-то информацию и ссылку на следующий элемент(в двусвязных списках- ещё и на предыдущий). НО на практике важно не внутреннее устройство списка, а то, чтобы с нашей структурой можно было работать как со списком.
вот, например, как могут быть организованы операции над списком из моей программы, для "списка" из достаточно большого массива и переменной, хранящей количество элементов "списка":
1) добавление элемента в список: в "списке" все элементы хранятся подряд, начиная с начала массива и далее. благодаря тому, что мы всегда знаем количество элементов "списка", мы всегда знаем номер последнего элемента. так вот, новый элемент мы будем добавлять в следующую за ним ячейку. и нарастим количество элементов на 1.
2) просмотр элемента списка номер N: ну, это совсем просто- если нам нужно просмотреть информацию элемента "списка" номер N, мы просто обращаемся к соответствующей ячейке массива.
3) удаление из списка элемента номер N: вот тут есть маленькая хитрость. как мы выкрутимся, если нам надо уметь удалять любой элемент "списка"? на самом деле удаление можно сделать очень просто: меняем местами содержимое последнего элемента и элемента N. а затем уменьшаем количество элементов на 1. вот и всё! то, что находится в массиве после элементов "списка", никого не интересует.
схожим образом можно организовать и популярные в программировании списки типа "стек" и "очередь". стек проще, очередь- чуть сложнее.
Добавлено (14.03.2013, 16:04) --------------------------------------------- ------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------ собирался сегодня рассказать об особенностях лабиринтов, получающихся при генерации моим способом(как я понял, применяя рекурсию можно добиться ровно тех же результатов). но решил, что те, кому эта информация может быть полезна, способны и сами всё понять. так зачем писать очевидное? лучше я подкину вам задачку.
задача: разместить в лабиринте вход, три ключа(красный, синий, зелёный), три двери(красная, синяя зелёная) и три сундука(красный, синий, зелёный) так, чтобы игрок, вошедший в лабиринт через вход, гарантированно имел бы возможность добраться до каждого сундука. но при этом, чтобы до сундука можно было добраться только после прохода через дверь такого же цвета. изначально все двери заперты, но могут быть открыты ключом такого же цвета.
подумайте. есть один очень простой способ. при расстановке этим способом, сундук всегда оказывается рядом с дверью того же цвета(за дверью). но ключ, конечно, не должен каждый раз получаться лежащим у двери- это было бы не интересно. ключ может оказаться рядом с дверью только случайно. и не надо пытаться просматривать и анализировать лабиринт- решение гораздо проще.
можно решить задачу и более сложным способом: так, чтобы сундук мог оказываться далеко за дверью, чтобы его приходилось искать. причём, можно генерить лабиринт так, чтобы к завершению генерации все объекты были уже в нём расставлены. это не просто. не то, чтобы сложно, но придётся проявить упорство, чтобы написать такую программу.
возможно, в вашей лабиринтовой игре вообще не будет ключей, НО разобравшись с этим упражнением, вы в любом случае сможете подойти более осмысленно к заполнению лабиринта. например, разбрасывая в лабиринте монстров разной силы и оружие разной мощности, вы можете позаботиться о том, чтобы не создавать изначально безнадёжных для игрока ситуаций.
и, конечно же, на основе моего алгоритма можно делать не только такие лабиринты с видом сверху. я видал одну старую 2d-игрушку с видом сбоку, в которой лабиринт состоял из одинаковых прямоугольных комнат, разделённых тонкими перегородками. чтобы генерить такие лабиринты нужно внести совсем не большие изменения в алгоритм.
и, вообще- интерес даже не именно в лабиринтах.. мало ли какие ещё структуры можно генерить. и важно понимать, что случайная генерация может создавать не только хаос, но и сложные упорядоченные структуры.
Дальнейшая реализация идеи с комнатами предвидится?
ну, я уже почти решил, что и как я хотел бы сделать, но.. давать ли код или просто выложить алгоритм? пожалуй, выложу код. но придётся подождать. все правила форумной игры Дуэль Программистов
Няша Я посмотрел твой код. Понял что я ещё зелёный нубас и тупо привинтил его к своему двужку) Надеюсь ты не против? Ах, да, пожелание: если в качестве дверей (при входе в комнату) будут двери (знак +) то это будет круто)
Я посмотрел твой код. Понял что я ещё зелёный нубас и тупо привинтил его к своему двужку) Надеюсь ты не против?
было бы в тысячу раз лучше, если бы ты понял алгоритм, а потом сделал бы его как умеешь- хотя бы без указателей, на массивах. тогда будет проще и короче- весь TList можно будет выкинуть на фик.
я же специально описал алгоритм в отдельном файле. он простой совсем. как сделать список из массива- читай в этой теме выше.
ты думаешь, я что в этой теме делаю? пишу программы на заказ? лично я надеялся, что даю интересную пищу для ума.
алгоритмы нужны не для того, чтобы их копировать, а для того, чтобы освоить какой-то приём, который можно потом по-разному применять в разных ситуациях.
Цитата (stalker5889)
пожелание: если в качестве дверей (при входе в комнату) будут двери (знак +) то это будет круто)
noname, когда я делал свой алгоритм я реализовал несколько комнат с одной дверью в рандомной стороне, но как соеденить их я не придумал.
есть простой способ: в готовом лабиринте вырезаешь комнату. скорее всего она будет иметь множество выходов и точно будет соединена с остальным лабиринтом. потом просматриваешь края комнаты и помечаешь выходы плюсиком. -----------------
а я решил сделать следующее: пару прог, генерящих разные шаблоны и одну прогу, которая будет по шаблону делать лабиринт.
это попытка сделать универсальное решение. суть в чём- шаблон- это типа такой же лабиринт, поля которого помечены: 0- пустое поле 1- стена 2- подлежит генерации
например, одна прога будет заполнять лабиринт двойками и вырезать в нём комнаты нулями
другая прога будет заполнять лабиринт двойками и вырезать в нём пятно из нулей, перечёркнутое единицами
любой из этих прог или своей прогой, вообще как угодно, создаёшь шаблон.
а другая прога делает из этого лабиринт. на месте нулей будут пустые поля, на месте единиц- стены, а там где двойки- будет генерить лабиринт так, чтобы это всё было связано в единый лабиринт. не всегда это возможно- ведь можно перечеркнуть лабиринт единицами пополам. но это мелочи- решаемо.
например, одна прога будет заполнять лабиринт двойками и вырезать в нём комнаты нулями
Например такую функцию я писал. Прошу просвятить невежду
Цитата (noname)
есть простой способ: в готовом лабиринте вырезаешь комнату. скорее всего она будет иметь множество выходов и точно будет соединена с остальным лабиринтом. потом просматриваешь края комнаты и помечаешь выходы плюсиком.
а почему бы и нет? я же не пишу игру. я пишу прогу, которая получает какие-то входные данные и выдаёт какой-то результат. потом- другую прогу и т.д.
Цитата (stalker5889)
например, одна прога будет заполнять лабиринт двойками и вырезать в нём комнаты нулями
Например такую функцию я писал.
да, я уже прочёл выше. это можно было сделать разными способами. в идеале прога должна уметь размещать заданное количество комнат заданного размера, если это вообще возможно. но я пойду более простым путём, исходя из того, что коридоров обычно должно быть заметно больше чем комнат. вообще- посмотрим.. вроде бы мой способ должен давать неплохую упаковку комнат. но если нет- придётся его переделать.
Цитата (stalker5889)
Прошу просвятить невежду smile
не понял- к чему это? о чём?
Цитата (stalker5889)
И так делал. Получается некрасиво.
ну, если пустые углы комнаты будут иметь обе нечётные координаты, то должно получиться нормально. то есть, вообще, мой старый алгоритм создаёт узловые точки на полях с обеими нечётными координатами, соединённые стенами или проходами. если же считать углами комнаты внешние поля, которые должны быть всегда со стенами, то они должны иметь обе чётные координаты. в моём старом аглоритме клетки с обеими чётными координатами всегда имеют стены. тогда будет получаться что-то вроде этого: #O###O# #OOOOO# OOOOOO# #OOOOO# ###O### проблема только в том, что таким способом в лабиринте может получиться много зацикливаний.
ну, дело вкуса. если тебе нужны комнаты с ровно одним выходом, то при генерёжке шаблона будешь генерить стены вокруг комнаты. моя генерация не должна давать зацикливаний вообще(если их не было в шаблоне). вообще, моя генерация даёт основу лабиринта. зацикливания можно сделать позже, на основе анализа лабиринта. об этом я тоже напишу и, возможно, дам какую-нить прогу.
и, да- писать буду долго. не потому что сложно, а потому что я ленив и вообще, даже бываю иногда чем-то и занят.
Добавлено (16.03.2013, 22:03) --------------------------------------------- ------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------ сегодня поднапрягся и сделал прогу генерации шаблона комнат практически с нуля до конца.
прога не совсем идеальна, и к тому же я там добавил горизонтальную сплошную стену, перечёркивающую комнаты, но эта прога подходит для проверки генератора лабиринта, который я напишу.
нормальных прог, генерирующих шаблоны, можно будет потом наделать. и ненормальных тоже. чтобы проверить генератор лабиринта.
если я смогу ещё один раз так напрячься, то новый генератор лабиринтов будет готов. он будет отличаться от старого. лабиринты будут получаться не из таких ровных линий. новому лабиринту нужно уметь быть гибким, чтобы нормально увязать любой шаблон.
и, да- решил выложить файл на всякий случай. надёжнее, когда работа хранится не только на винте, но и в тырнете: http://yadi.sk/d/PLLAyYND3K3lk
сли я смогу ещё один раз так напрячься, то новый генератор лабиринтов будет готов. он будет отличаться от старого. лабиринты будут получаться не из таких ровных линий. новому лабиринту нужно уметь быть гибким, чтобы нормально увязать любой шаблон.
звучит немного пугающе, но на самом деле ничего сверхсложного нет. алгоритм генерации такого лабиринта я уже упомянул в этой теме выше:
Цитата (noname)
можно было пробивать не по две клетки в выбранную сторону, а по одной. только тогда надо внимательно проверять соседние поля. мой алгоритм проверяет только одно поле- то, до которого пробивается. а если вы решите пробиваться по одной клетке, то необходимо предварительно проверить, что рядом с ней нет уже пробитых ранее полей. иначе вместо лабиринта может получиться открытая поляна.
начинаем строить лабиринт от точки входа(она должна быть указана в шаблоне) и распространяемся далее. если встречаем в шаблоне '0', то это место "заливаем" пустотой '.' так же как в графредакторах заливают область цветом. заливка, собственно и есть та "открытая поляна" которая получается если допускать рисование пустот рядом с пустотами. то есть, заливка делается так: - отмечаем встреченный ноль пустотой '.' и заносим это поле в список - пока список не пуст: --- выбираем первое поле из списка --- заносим в список все соседние с ним поля с '0' --- удаляем выбранное поле из списка всё!
но тут есть пара тонких моментов: когда генератор лабиринтов вызывает в заливку, требуется, чтобы заливка вернула лабиринту список полей, от которых можно попытаться строить лабиринт дальше. это означает, что удалённые из списка поля следует добавлять в другой список, который функция заливки будет возвращать тому, кто её вызвал. как-то проверять эти поля не зачем- генератор лабиринта сделает это сам.
на реализацию этих алгоритмов у меня может уйти 2 часа упорной работы. но прямо сейчас у меня есть чем заняться: подвалила работа, от которой я устаю. скорее всего, сделаю лабиринт примерно к концу следующей недели.
задача: разместить в лабиринте вход, три ключа(красный, синий, зелёный), три двери(красная, синяя зелёная) и три сундука(красный, синий, зелёный) так, чтобы игрок, вошедший в лабиринт через вход, гарантированно имел бы возможность добраться до каждого сундука. но при этом, чтобы до сундука можно было добраться только после прохода через дверь такого же цвета. изначально все двери заперты, но могут быть открыты ключом такого же цвета.
и, да - я так подумал.. прежде, чем перейти на новый генератор лабиринтов, хорошо бы до конца разобраться со старым. итого, решение задачи(предполагается, что лабиринт строится по алгоритму, данному мной в архиве RL_Gen_1.rar):
простое решение:
в двух словах, простое решение заключается в том, чтобы при генерации лабиринта размещать ключи раньше сундуков, а сундуки отделять дверьми.
а теперь распишу эту мысль детально:
допустим, мы строим лабиринт 9х11. тогда в нём будет 4х5=20 узловых точек(тех самых, которые попадают в список и точно будут пустыми к концу генерации. если считать координаты от (0,0) включительно, то все поля лабиринта с обеими нечётными координатами будут узловыми точками).
выберем любую узловую точку в качестве точки входа в лабиринт, и с неё же начнём генерацию лабиринта.
в простом варианте мы размещаем в лабиринте 3-и ключа и 3-и сундука, всего шесть элементов(а двери поставим перед с сундуками). 20/6= 3 целых и 2 в остатке. исходя из этого мы первые 2 узловые точки не трогаем, а каждый следующий элемент размещаем в каждой третьей узловой точке.
может быть, эти рассуждения могут показаться сложными, но на самом деле же просто всё: суть в том, что если во время генерации мы поставим в какую-то узловую точку объект1, а потом в какую-то из следующих, объект2, то мы гарантированно из точки генерации сможем пройти к объекту1, избежав попадания в поле с объектом2. поэтому, разместив ключ раньше двери мы гарантируем, что ключ никогда не окажется за дверью(относительно героя, идущего из начального поля генерации). можно ли дойти до объекта2 в обход объекта1? это может сложиться по-разному.
итого мы считаем создаваемые алгоритмом узловые точки и располагаем элементы в следующем порядке: - точка входа- на первом же созданном поле, с которого начинается генерация - красный ключ на 5-м поле - красный сундук на 8-м поле - зелёный ключ на 11-м поле - зелёная дверь на 14-м поле - синий ключ на 17-м поле - синий сундук на 20-м поле в-общем, не так уж и сложно вычислять эти цифры для лабиринта любого размера. но обычно игроделы рогаликов точно знают размеры лабиринта, которые им нужны. в этом случае вычислить эти цифры ещё проще))
то есть, делая очередной пробив(а каждый пробив добавляет к лабиринту новую узловую точку) мы наращиваем счётчик и сверяемся с ним. и если мы пробиваемся к 5-му узловому полю, то вместо двух пустот подряд делаем пустоту и красный ключ.
а если мы пробиваемся к 8-му узловому полю, то(внимание!) вместо двух пустот подряд, делаем красную дверь и красный сундук. красная дверь окажется между двумя узловыми полями, а к сундуку невозможно будет попасть в обход красной двери.
можно ли найти дверь раньше ключа, или можно ли найти зелёный ключ раньше красного? это уж как сложится. зависит от лабиринта. но всегда будет способ найти ключ раньше двери и всегда будет способ найти красный ключ раньше зелёного.
почему получается так, что нельзя найти сундук раньше двери? потому что мы их размещаем не в узловых полях, которые генерятся в случайном порядке, а мы размещаем дверь в коридоре, соединяющем узловую точку сундука с лабиринтом.
в-общем, если вы поняли что и почему получается именно так, то вы поняли всё важное относительно свойств нашего алгоритма генерации лабиринтов))
если вы разобрались с простым решением, то готовы освоить и более сложное.
в более сложном решении нет ровно никаких хитростей но есть необходимость учитывать некоторую информацию.
заведём ещё три массива для хранения инфы об узловых точках.: R, G, B. а так же будем запоминать координаты трёх сундуков. если сундук ещё не размещён, то пусть в его координатах хранится (-1,-1), чтобы мы могли понять, что его пока нет.
ключи и двери будем располагать точно так же как и в простом решении. и даже сундуки будем по-началу располагать так же. но потом будем эти сундуки перемещать. (на самом деле хорошо бы разместить их слегка пораньше, чтобы синий сундук не оказывался всегда на самом последнем поле откуда мы его больше никуда не переместим ввиду того что генерация закончится. в этом варианте лучше бы всё разместить в первой половине генерации, но в-общем, главное- понять суть. а детали каждый сделает так как ему лучше).
по-началу, в массивы R,G, B при каждом пробитии заносим 0 в ячейку, соответствующую новой узловой точке. после размещения красной двери в массив R занесём не ноль, а 1. это означает, что в эту точку можно попасть только через красную дверь. в дальнейшем, если пробитие осуществлялось из точки помеченной в некоторых из этих трёх массивов единицей, то и новую точку тоже помечаем единицами в этих массивах. таким образом получится, что каждый раз, пробиваясь к новой узловой точке, мы уже знаем, какие двери необходимо пройти, чтобы к этой узловой точке попасть. это ключевой момент сложного метода.
теперь о сундуках: - если в новую узловую точку можно попасть через красную дверь, то переносим красный сундук в неё(для этого мы запоминали координаты сундука). так же поступаем и с остальными сундуками. - есть тонкий момент: если в новую узловую точку можно попасть только пройдя через несколько дверей, то перенести надо только один из соответствующих сундуков. просто потому, что в нашем массиве все объекты отмечаются буквами и два сундука на одну клетку мы не поместим. - не факт, что следующая точка будет дальше предыдущей- может оказаться и ближе.. но мы добьёмся того, что сундуки будут находиться неизвестно где за дверьми.
ещё момент: вас достало то, что в нашем лабиринте нет зацикливаний? выберите несколько случайных стен между узловыми точками и если обе узловые точки абсолютно одинаково помечены в массивах R,G и B, то стену между ними можно смело пробивать- вы не создадите пути в обход двери.
Добавлено (22.03.2013, 19:53) --------------------------------------------- ------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------ короч, сделал.. не очень хорошо- всё на костылях, но хуже всего, что новый алгоритм генерации лабиринтов порочен по своей сути: он иногда создаёт сам себе непроходимые препятствия. без комнат это не заметно, но когда объединил его с комнатами и хорошенько потестил, то это всплыло. не всегда генерацией удаётся охватить весь лабиринт.
самое простое и красивое решение- вернуться к своему изначальному ровненькому прямоугольному лабиринту, и генерить комнаты и стены так, чтобы они хорошо вписывались в лабиринт. у такого решения будет один большой недостаток: не любые шаблоны будут корректны. шаблоны придётся генерить так, чтобы они подходили под лабиринт.
вообще, ещё проще сделать обычную нормальную генерацию без всяких шаблонов, а если нужно сгенерить какой-то особый уровень: с большой ареной в центре или ещё что, тогда писать особую генерацию специально для такого уровня.
ещё возможно такое решение: у нас есть список комнат, которые могут быть на данном уровне лабиринта. и во время генерации лабиринта, постепенно в лабиринт подставляются какие-то из подходящих комнат. возиться потом с шаблонами комнат ещё..
хочу ещё заметить, что брать на себя какие-то обязательства- это знатное попадалово. тема вродь интересная и вродь есть пути решения, но бывает интерес пропадает. вообще, обязательства- это плохо.
на данный момент мне уже хочется переделать всё с самого начала.
ещё тут есть такой момент: для любой конкретной игры сделать всю генерацию было бы проще. я же пытался сделать что-то очень общее и очень универсальное. это всё же сложнее.
надо дважды хорошо подумать, что именно делать. пусть это будет не сильно универсальная штука, но пусть это будет какой-то нормально работающий пример генерации лабиринтов с комнатами. короч, да- буду думать.
вернулся к старому способу генерации лабиринтов и комнаты генерю специально под них.
генерация комнат не оптимальна- её можно упростить. но работает- и ладно. я уже устал от этих лабиринтов.
выкладываю генератор шаблонов с комнатами + генератор лабиринтов по шаблону: http://yadi.sk/d/IvufBE1F3XeYA вроде бы всё работает.
ну вот, отделался наконец!
не буду больше никому ничего обещать и никого ничему учить. лучше буду игры писать. и, может быть, даже исходники выложу. с подробными комментами. но- не обещаю.
Код выглядит пугающе, но большое спасибо что прокоментировал. Я не буду копировать твой код, а сделаю свой на его основе. Если получится)
ну, мой первый выложенный здесь архив содержал алгоритм и относительно простую прогу. и там можно было попытаться разобраться и сделать что-то своё на его основе.
в последнем архиве разобраться уже не так просто, но я старался комментировать всё что только возможно. не знаю, насколько имеет смысл избегать копирования.. но, да- если поймешь что там да как, то тебе легче будет изменять его под свои потребности. все правила форумной игры Дуэль Программистов
Жалко нельзя ещё плюс поставить. Щас прикручу к игре)
хочешь научиться программировать? так учись!