Четверг, 28 Марта 2024, 17:30

Приветствую Вас Гость

[ Новые сообщения · Игроделы · Правила · Поиск ]
  • Страница 1 из 1
  • 1
Форум игроделов » Программирование » Общие обсуждения программистов » генерация лабиринтов
генерация лабиринтов
nonameДата: Вторник, 12 Марта 2013, 18:41 | Сообщение # 1
заслуженный участник
Сейчас нет на сайте
моя программа генерации лабиринтов
на C++
с исходником,
описанием алгоритма,
с выводом результата работы в текстовый файл:
http://zalil.ru/34340028
файл будет удалён через 10 дней после последнего скачивания.

и будьте бдительны: проверяйте файл на вирусы!

Добавлено (12.03.2013, 18:41)
---------------------------------------------
получающиеся лабиринты не похожи на те, которые вы могли видеть в рогаликах. тем не менее, можно придумать игры, для которых именно такая генерация идеально подойдёт. получающиеся лабиринты похожи на лабиринты из синклеровской игрушки Maziacs.

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

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

дальнейшее развитие идеи в том, чтобы генерировать лабиринты с комнатами, как в рогаликах.

например, вы можете видеть это на второй картинке здесь.

или в лабиринтах, генерируемых здесь.


все правила форумной игры Дуэль Программистов
stalker5889Дата: Вторник, 12 Марта 2013, 19:04 | Сообщение # 2
Свободный игродел
Сейчас нет на сайте
Ну ты и зверь) Вот это я понимаю, сказал - сделал. smile Жалко нельзя ещё плюс поставить. Щас прикручу к игре)

TiendilДата: Вторник, 12 Марта 2013, 22:20 | Сообщение # 3
участник
Сейчас нет на сайте
Выложи на github а то не все будут качать неизвестно что, а так и посмотреть можно и багу запостить.

Участвовал в разработке Order of War (C++ UI & логика) и WoT (Python портал worldoftanks.ru почти всё :-) )

Текущий проект: the-tale.org - indie mmozpg
-Mikle-Дата: Среда, 13 Марта 2013, 14:51 | Сообщение # 4
Изобретатель велосипедов
Сейчас нет на сайте
Ну и я свои варианты лабиринта покажу:
Прямоугольный и Круглый
С выводом результата в виде картинки и исходником на VB6. Код очень простой.
nonameДата: Четверг, 14 Марта 2013, 16:13 | Сообщение # 5
заслуженный участник
Сейчас нет на сайте
Цитата (-Mikle-)
Код очень простой.

посмотрел код прямоугольного лабиринта. код действительно очень прост, за счёт использования рекурсии. да, рекурсия рулит, если уметь её применять!

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

обычно списки организуют с помощью указателей. но многие игроделы используют скриптовые языки конструкторов, в которых указатели не предусмотрены. что тогда делать?

в этом случае список можно организовать с помощью достаточно большого массива и переменной, хранящей количество элементов "списка".

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

вот, например, как могут быть организованы операции над списком из моей программы, для "списка" из достаточно большого массива и переменной, хранящей количество элементов "списка":

1) добавление элемента в список:
в "списке" все элементы хранятся подряд, начиная с начала массива и далее. благодаря тому, что мы всегда знаем количество элементов "списка", мы всегда знаем номер последнего элемента. так вот, новый элемент мы будем добавлять в следующую за ним ячейку. и нарастим количество элементов на 1.

2) просмотр элемента списка номер N:
ну, это совсем просто- если нам нужно просмотреть информацию элемента "списка" номер N, мы просто обращаемся к соответствующей ячейке массива.

3) удаление из списка элемента номер N:
вот тут есть маленькая хитрость. как мы выкрутимся, если нам надо уметь удалять любой элемент "списка"? на самом деле удаление можно сделать очень просто: меняем местами содержимое последнего элемента и элемента N. а затем уменьшаем количество элементов на 1. вот и всё! то, что находится в массиве после элементов "списка", никого не интересует.

схожим образом можно организовать и популярные в программировании списки типа "стек" и "очередь". стек проще, очередь- чуть сложнее.

Добавлено (14.03.2013, 16:04)
---------------------------------------------
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
собирался сегодня рассказать об особенностях лабиринтов, получающихся при генерации моим способом(как я понял, применяя рекурсию можно добиться ровно тех же результатов). но решил, что те, кому эта информация может быть полезна, способны и сами всё понять. так зачем писать очевидное? лучше я подкину вам задачку.

задача: разместить в лабиринте вход, три ключа(красный, синий, зелёный), три двери(красная, синяя зелёная) и три сундука(красный, синий, зелёный) так, чтобы игрок, вошедший в лабиринт через вход, гарантированно имел бы возможность добраться до каждого сундука. но при этом, чтобы до сундука можно было добраться только после прохода через дверь такого же цвета. изначально все двери заперты, но могут быть открыты ключом такого же цвета.

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

можно решить задачу и более сложным способом: так, чтобы сундук мог оказываться далеко за дверью, чтобы его приходилось искать. причём, можно генерить лабиринт так, чтобы к завершению генерации все объекты были уже в нём расставлены. это не просто. не то, чтобы сложно, но придётся проявить упорство, чтобы написать такую программу.

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

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

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

Добавлено (14.03.2013, 16:13)
---------------------------------------------
ну и решил выложиться на нормальный хостинг: http://yadi.sk/d/SDPz2lWo3HYgw


все правила форумной игры Дуэль Программистов

Сообщение отредактировал noname - Четверг, 14 Марта 2013, 16:13
stalker5889Дата: Четверг, 14 Марта 2013, 18:23 | Сообщение # 6
Свободный игродел
Сейчас нет на сайте
Цитата (noname)
дальнейшее развитие идеи в том, чтобы генерировать лабиринты с комнатами, как в рогаликах.

Дальнейшая реализация идеи с комнатами предвидится?


nonameДата: Четверг, 14 Марта 2013, 19:01 | Сообщение # 7
заслуженный участник
Сейчас нет на сайте
Цитата (stalker5889)

Дальнейшая реализация идеи с комнатами предвидится?

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


все правила форумной игры Дуэль Программистов
stalker5889Дата: Четверг, 14 Марта 2013, 19:09 | Сообщение # 8
Свободный игродел
Сейчас нет на сайте
Цитата (noname)
пожалуй, выложу код.

Няша smile Я посмотрел твой код. Понял что я ещё зелёный нубас и тупо привинтил его к своему двужку) Надеюсь ты не против? Ах, да, пожелание: если в качестве дверей (при входе в комнату) будут двери (знак +) то это будет круто)


nonameДата: Четверг, 14 Марта 2013, 20:40 | Сообщение # 9
заслуженный участник
Сейчас нет на сайте
Цитата (stalker5889)
Я посмотрел твой код. Понял что я ещё зелёный нубас и тупо привинтил его к своему двужку) Надеюсь ты не против?

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

я же специально описал алгоритм в отдельном файле. он простой совсем. как сделать список из массива- читай в этой теме выше.

ты думаешь, я что в этой теме делаю? пишу программы на заказ? лично я надеялся, что даю интересную пищу для ума.

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

Цитата (stalker5889)
пожелание: если в качестве дверей (при входе в комнату) будут двери (знак +) то это будет круто)

cry хочешь научиться программировать? так учись!


все правила форумной игры Дуэль Программистов
stalker5889Дата: Пятница, 15 Марта 2013, 15:52 | Сообщение # 10
Свободный игродел
Сейчас нет на сайте
noname, когда я делал свой алгоритм я реализовал несколько комнат с одной дверью в рандомной стороне, но как соеденить их я не придумал.



Сообщение отредактировал stalker5889 - Пятница, 15 Марта 2013, 15:53
nonameДата: Пятница, 15 Марта 2013, 16:20 | Сообщение # 11
заслуженный участник
Сейчас нет на сайте
лан, нормуль.

Цитата (stalker5889)
noname, когда я делал свой алгоритм я реализовал несколько комнат с одной дверью в рандомной стороне, но как соеденить их я не придумал.

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

а я решил сделать следующее: пару прог, генерящих разные шаблоны и одну прогу, которая будет по шаблону делать лабиринт.

это попытка сделать универсальное решение. суть в чём- шаблон- это типа такой же лабиринт, поля которого помечены:
0- пустое поле
1- стена
2- подлежит генерации

например, одна прога будет заполнять лабиринт двойками и вырезать в нём комнаты нулями

другая прога будет заполнять лабиринт двойками и вырезать в нём пятно из нулей, перечёркнутое единицами

любой из этих прог или своей прогой, вообще как угодно, создаёшь шаблон.

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

вся сложность для меня в том, чтобы поднапрячься и начать это делать. но- сделаю. жди.


все правила форумной игры Дуэль Программистов

Сообщение отредактировал noname - Пятница, 15 Марта 2013, 16:29
stalker5889Дата: Пятница, 15 Марта 2013, 16:41 | Сообщение # 12
Свободный игродел
Сейчас нет на сайте
Цитата (noname)
пару прог

Почему не функций?
Цитата (noname)
например, одна прога будет заполнять лабиринт двойками и вырезать в нём комнаты нулями

Например такую функцию я писал.
Прошу просвятить невежду smile
Цитата (noname)
есть простой способ: в готовом лабиринте вырезаешь комнату. скорее всего она будет иметь множество выходов и точно будет соединена с остальным лабиринтом. потом просматриваешь края комнаты и помечаешь выходы плюсиком.

И так делал. Получается некрасиво.


nonameДата: Понедельник, 25 Марта 2013, 19:07 | Сообщение # 13
заслуженный участник
Сейчас нет на сайте
Цитата (stalker5889)
Почему не функций?

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

Цитата (stalker5889)
например, одна прога будет заполнять лабиринт двойками и вырезать в нём комнаты нулями

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

Цитата (stalker5889)
Прошу просвятить невежду smile

не понял- к чему это? о чём?

Цитата (stalker5889)
И так делал. Получается некрасиво.

ну, если пустые углы комнаты будут иметь обе нечётные координаты, то должно получиться нормально. то есть, вообще, мой старый алгоритм создаёт узловые точки на полях с обеими нечётными координатами, соединённые стенами или проходами. если же считать углами комнаты внешние поля, которые должны быть всегда со стенами, то они должны иметь обе чётные координаты. в моём старом аглоритме клетки с обеими чётными координатами всегда имеют стены. тогда будет получаться что-то вроде этого:
#O###O#
#OOOOO#
OOOOOO#
#OOOOO#
###O###
проблема только в том, что таким способом в лабиринте может получиться много зацикливаний.

ну, дело вкуса. если тебе нужны комнаты с ровно одним выходом, то при генерёжке шаблона будешь генерить стены вокруг комнаты. моя генерация не должна давать зацикливаний вообще(если их не было в шаблоне). вообще, моя генерация даёт основу лабиринта. зацикливания можно сделать позже, на основе анализа лабиринта. об этом я тоже напишу и, возможно, дам какую-нить прогу.

Добавлено (15.03.2013, 18:54)
---------------------------------------------
--

и, да- писать буду долго. не потому что сложно, а потому что я ленив и вообще, даже бываю иногда чем-то и занят.

Добавлено (16.03.2013, 22:03)
---------------------------------------------
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
сегодня поднапрягся и сделал прогу генерации шаблона комнат практически с нуля до конца.

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

нормальных прог, генерирующих шаблоны, можно будет потом наделать. и ненормальных тоже. чтобы проверить генератор лабиринта.

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

и, да- решил выложить файл на всякий случай. надёжнее, когда работа хранится не только на винте, но и в тырнете:
http://yadi.sk/d/PLLAyYND3K3lk

Добавлено (18.03.2013, 20:11)
---------------------------------------------
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
Цитата (noname)
сли я смогу ещё один раз так напрячься, то новый генератор лабиринтов будет готов. он будет отличаться от старого. лабиринты будут получаться не из таких ровных линий. новому лабиринту нужно уметь быть гибким, чтобы нормально увязать любой шаблон.

звучит немного пугающе, но на самом деле ничего сверхсложного нет. алгоритм генерации такого лабиринта я уже упомянул в этой теме выше:
Цитата (noname)
можно было пробивать не по две клетки в выбранную сторону, а по одной. только тогда надо внимательно проверять соседние поля. мой алгоритм проверяет только одно поле- то, до которого пробивается. а если вы решите пробиваться по одной клетке, то необходимо предварительно проверить, что рядом с ней нет уже пробитых ранее полей. иначе вместо лабиринта может получиться открытая поляна.

начинаем строить лабиринт от точки входа(она должна быть указана в шаблоне) и распространяемся далее. если встречаем в шаблоне '0', то это место "заливаем" пустотой '.' так же как в графредакторах заливают область цветом. заливка, собственно и есть та "открытая поляна" которая получается если допускать рисование пустот рядом с пустотами. то есть, заливка делается так:
- отмечаем встреченный ноль пустотой '.' и заносим это поле в список
- пока список не пуст:
--- выбираем первое поле из списка
--- заносим в список все соседние с ним поля с '0'
--- удаляем выбранное поле из списка
всё!

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

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

Добавлено (18.03.2013, 20:46)
---------------------------------------------
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
Цитата (noname)
задача: разместить в лабиринте вход, три ключа(красный, синий, зелёный), три двери(красная, синяя зелёная) и три сундука(красный, синий, зелёный) так, чтобы игрок, вошедший в лабиринт через вход, гарантированно имел бы возможность добраться до каждого сундука. но при этом, чтобы до сундука можно было добраться только после прохода через дверь такого же цвета. изначально все двери заперты, но могут быть открыты ключом такого же цвета.

и, да - я так подумал.. прежде, чем перейти на новый генератор лабиринтов, хорошо бы до конца разобраться со старым. итого, решение задачи(предполагается, что лабиринт строится по алгоритму, данному мной в архиве RL_Gen_1.rar):

простое решение:


Добавлено (18.03.2013, 21:07)
---------------------------------------------
продвинутое решение:

Добавлено (22.03.2013, 19:53)
---------------------------------------------
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
короч, сделал.. не очень хорошо- всё на костылях, но хуже всего, что новый алгоритм генерации лабиринтов порочен по своей сути: он иногда создаёт сам себе непроходимые препятствия. без комнат это не заметно, но когда объединил его с комнатами и хорошенько потестил, то это всплыло. не всегда генерацией удаётся охватить весь лабиринт.

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

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

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

короче- надо думать.

а пока что выкладываю свою позорную недоделку на костылях: http://yadi.sk/d/PFQZe92r3T3W6.

хочу ещё заметить, что брать на себя какие-то обязательства- это знатное попадалово. тема вродь интересная и вродь есть пути решения, но бывает интерес пропадает. вообще, обязательства- это плохо.

на данный момент мне уже хочется переделать всё с самого начала.

ещё тут есть такой момент: для любой конкретной игры сделать всю генерацию было бы проще. я же пытался сделать что-то очень общее и очень универсальное. это всё же сложнее.

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

Добавлено (25.03.2013, 19:07)
---------------------------------------------
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------

доделал..

вернулся к старому способу генерации лабиринтов и комнаты генерю специально под них.

генерация комнат не оптимальна- её можно упростить. но работает- и ладно. я уже устал от этих лабиринтов.

выкладываю генератор шаблонов с комнатами + генератор лабиринтов по шаблону:
http://yadi.sk/d/IvufBE1F3XeYA
вроде бы всё работает.

ну вот, отделался наконец!

не буду больше никому ничего обещать и никого ничему учить. лучше буду игры писать. и, может быть, даже исходники выложу. с подробными комментами. но- не обещаю.


все правила форумной игры Дуэль Программистов

Сообщение отредактировал noname - Понедельник, 18 Марта 2013, 21:43
stalker5889Дата: Понедельник, 25 Марта 2013, 19:24 | Сообщение # 14
Свободный игродел
Сейчас нет на сайте
noname, круто)
Цитата (noname)
выкладываю генератор шаблонов с комнатами + генератор лабиринтов по шаблону

Код выглядит пугающе, но большое спасибо что прокоментировал. Я не буду копировать твой код, а сделаю свой на его основе. Если получится)


nonameДата: Понедельник, 25 Марта 2013, 20:13 | Сообщение # 15
заслуженный участник
Сейчас нет на сайте
Цитата (stalker5889)
Код выглядит пугающе, но большое спасибо что прокоментировал. Я не буду копировать твой код, а сделаю свой на его основе. Если получится)

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

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


все правила форумной игры Дуэль Программистов
Форум игроделов » Программирование » Общие обсуждения программистов » генерация лабиринтов
  • Страница 1 из 1
  • 1
Поиск:

Все права сохранены. GcUp.ru © 2008-2024 Рейтинг