Рандомный генератор красивых лабиринтов, обсуждаем алгоритмы Опции

[BreakMaster]

Думаю, эта тема будет полезна многим. Давайте здесь выкладывать свои алгоритмы генерирования случайных лабиринтов. Я вот сейчас обдумываю, как сделать, чтобы было несколько залов, соединенных друг с другом тунелями.
Допустим, мы имеем массив a[1..100,1..100], состоящий из нулей, единиц и двоек.
0 – это проход, 1 – стена, 2 – дверь.
У меня пока на ум приходит только совсем тупой и случайный вариант – сначала все заполняем единицами, дальше случайным образом разбрасываем по массиву нули, а потом случайным образом смотрим, можно ли поставить дверь в случайный квадрат. (проверка выглядит следующим образом – проверяем, пусты ли боковые и стена ли верхняя и нижняя клетки, и наоборот). А чтобы сделать залы, просто когда карта сгенерированна, в случайное место вставляем пару прямоугольников из нулей.
У кого-нибудь есть мысли на этот счет?

[Guevara-chan]

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

Ну, допустим, у меня так:

Код

Macro AddWall(X, Y, Length, IsVert, Type)
AddElement(Walls())
Walls()\Left = X
Walls()\Top = Y
Walls()\Right = Length
If IsVert : Walls()\Right * -1 : EndIf
Walls()\Bottom = Type
EndMacro

Procedure RandomWall()
Select Random(29)
Case 0 : ProcedureReturn #TMetalWall
Case 1 To 5 : ProcedureReturn #THeaterGrid
Default : ProcedureReturn #TRMetalWall
EndSelect
EndProcedure

Procedure GenerateFloor()
#FactorEdge = 3
#ExitStep = 40
Define X, Y, ToFix, XFactor, YFactor, Door
Define Level = *Player\Mental
; -Output "loading" message.
WaitingMessage("Stage generation, please wait...")
If Level < #FinalHeight
NewList Walls.RECT()
; -Reset map-
For Y = 0 To #FloorHeight - 1
For X = 0 To #FloorWidth - 1
PutTile(X, Y, #TFloor)
Floor(X, Y)\Level = Level
EraseList(Floor(X, Y)\Objects)
Next X
Next Y
; -Form initital grid-
For Y = 0 To #FloorHeight - #MinRoomSize Step #MinRoomSize
For X = 0 To #FloorWidth - #MinRoomSize Step #MinRoomSize
If X <> 0 And Random(1) : AddWall(X + Rnd(-1, 1), Y, #MinRoomSize, #True, RandomWall())
If XFactor = #FactorEdge : If CheckTransparency(Walls()\Bottom) : Walls()\Bottom * -1 : EndIf
XFactor = 0 : Else : XFactor + 1 : EndIf
Else : XFactor = 0
EndIf
If Y <> 0 And Random(1) : AddWall(X, Y + Rnd(-1, 1), #MinRoomSize, #False, RandomWall())
If YFactor = #FactorEdge : If CheckTransparency(Walls()\Bottom) : Walls()\Bottom * -1 : EndIf
YFactor = 0 : Else : YFactor + 1 : EndIf
Else : YFactor = 0
EndIf
Next X
Next Y
; -Add Borders-
AddWall(0, 0, #FloorWidth, #False, #TMetalWall)
AddWall(0, #FloorHeight - 1, #FloorWidth, #False, #TMetalWall)
AddWall(0, 0, #FloorHeight, #True, #TMetalWall)
AddWall(#Floorwidth - 1, 0, #FloorHeight, #True, #TMetalWall)
; -Draw walls to map-
ForEach Walls()
With Walls()
If \Bottom < 0 : \Bottom * -1 : Door = #True : EndIf; Place Door
If \Right > 0 : ToFix = \Left + \Right - 1
For X = \Left To ToFix : PutTile(X, \Top, \Bottom) : Next X
If Door = #True : PutTile(\Left + \Right / 2 + Rnd(-1, 1), \Top, #TCDoor) : Door = 0 : EndIf
Else : ToFix = \Top - \Right - 1
For Y = \Top To ToFix : PutTile(\Left, Y, \Bottom) : Next Y
If Door = #True : PutTile(\Left, \Top - \Right / 2 + Rnd(-1, 1), #TCDoor) : Door = 0 : EndIf
EndIf
EndWith
Next
ClearList(Walls())

Смысл: создается сетка из случайно сдвинутых стен (списком), потом часть из них в случайном порядке убирается, а остальные рисуются на карту. Если стена именно стена, а не линия нагревательных решеток, то там еще дверь может быть (считается по частоте идущих подряд стен)... Ну и по краям стены, ес-сно. Результат вы все можете видеть в Finite height.

Конкретно по вопросу бряка хотелось бы уточнить: какая предпологается форма и длинна туннелей ?

[BreakMaster]

форма туннелей любая, но желательно чтобы соблюдался прямоугольный стиль. Длина тоже любая (от одного зала до другого расстояние может быть большое)

[gamecreator]

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

[Guevara-chan]

Хрона, у тебя лабиринты не очень.

Так у меня-то сюрреалистическая башня, а в Crawl - подземелие.

Добавлено ([mergetime]1228566179[/mergetime]):

форма туннелей любая, но желательно чтобы соблюдался прямоугольный стиль. Длина тоже любая (от одного зала до другого расстояние может быть большое)

Ну тогда сначала действительно делаем список не пересекающихся залов, а потом ищем пути между ними. Можно и через A*.

[BreakMaster]

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

[Guevara-chan]

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

Платная o_o ?

[BreakMaster]

Ну ею там всерьез занялись. она под виндоус идет, музыка красивая играет. там все разрисовано красиво. называется FastCrawl free trial

[gamecreator]

муахаха!! тебя конкретно развели )))
гугл надо юзать.

[BreakMaster]

в каком месте меня развели ?
я разве за нее платил?

[gamecreator]

тебе подсунули что-то даже отдаленно не напоминающее DC

[Bourn]

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

[gamecreator]

приблизительный алгоритм генерации лабиринта в Dungeon Crawl:
1. рисуем заполненные и незаполненные прямоугольники-"проходы"
2. рисуем заполненные прямоугольники-"стены"