Думаю, эта тема будет полезна многим. Давайте здесь выкладывать свои алгоритмы генерирования случайных лабиринтов. Я вот сейчас обдумываю, как сделать, чтобы было несколько залов, соединенных друг с другом тунелями.
Допустим, мы имеем массив a[1..100,1..100], состоящий из нулей, единиц и двоек.
0 – это проход, 1 – стена, 2 – дверь.
У меня пока на ум приходит только совсем тупой и случайный вариант – сначала все заполняем единицами, дальше случайным образом разбрасываем по массиву нули, а потом случайным образом смотрим, можно ли поставить дверь в случайный квадрат. (проверка выглядит следующим образом – проверяем, пусты ли боковые и стена ли верхняя и нижняя клетки, и наоборот). А чтобы сделать залы, просто когда карта сгенерированна, в случайное место вставляем пару прямоугольников из нулей.
У кого-нибудь есть мысли на этот счет?
Полная версия этой страницы: Рандомный генератор красивых лабиринтов
Цитата
Давайте здесь выкладывать свои алгоритмы генерирования случайных лабиринтов.
Ну, допустим, у меня так:
Код
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())
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.
Конкретно по вопросу бряка хотелось бы уточнить: какая предпологается форма и длинна туннелей ?
форма туннелей любая, но желательно чтобы соблюдался прямоугольный стиль. Длина тоже любая (от одного зала до другого расстояние может быть большое)
Хрона, у тебя лабиринты не очень. вот в crawl класс.
а вообще гугл много интересных вещей по этой теме находит. я искал пару дней назад
а вообще гугл много интересных вещей по этой теме находит. я искал пару дней назад
Цитата
Хрона, у тебя лабиринты не очень.
Так у меня-то сюрреалистическая башня, а в Crawl - подземелие.
Добавлено ([mergetime]1228566179[/mergetime]):
Цитата
форма туннелей любая, но желательно чтобы соблюдался прямоугольный стиль. Длина тоже любая (от одного зала до другого расстояние может быть большое)
Ну тогда сначала действительно делаем список не пересекающихся залов, а потом ищем пути между ними. Можно и через A*.
при попытке скачать досовский crawl, мне всунули версию на 13,6 мб в которой оказалось столько наворотов! однако она была платная... соответственно прошел я ее всю за 20 минут. но оттуда можно подчерпнуть много идей для своих игр...
Цитата(BreakMaster @ 06 Dec 2008, 19:07)
при попытке скачать досовский crawl, мне всунули версию на 13,6 мб в которой оказалось столько наворотов! однако она была платная... соответственно прошел я ее всю за 20 минут. но оттуда можно подчерпнуть много идей для своих игр...
Платная o_o ?
Ну ею там всерьез занялись. она под виндоус идет, музыка красивая играет. там все разрисовано красиво. называется FastCrawl free trial
муахаха!! тебя конкретно развели )))
гугл надо юзать.
гугл надо юзать.
в каком месте меня развели 
?
я разве за нее платил?
?я разве за нее платил?
тебе подсунули что-то даже отдаленно не напоминающее DC
вобще я бы начал генерить лабиринт не с этого, сначала расставляем двери и рисуем пути к ним, когда главный путь есть, допоняем ответвлениями его и возможно будет 2-3 главных пути к одной двери, далее в оставшееся место добавляем нужные сдены препятствия и тп, итог прост - уровень готов.
приблизительный алгоритм генерации лабиринта в Dungeon Crawl:
1. рисуем заполненные и незаполненные прямоугольники-"проходы"
2. рисуем заполненные прямоугольники-"стены"
1. рисуем заполненные и незаполненные прямоугольники-"проходы"
2. рисуем заполненные прямоугольники-"стены"
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.