Войти
ПрограммированиеФорумОбщее

Генерация карт в рогалике

Страницы: 1 2 Следующая »
#0
19:32, 1 апр. 2011

Сап геймдев.
Пишу шоколадный рогалик со случайными подземельями. Хотелось бы найти способ генерации подземелий, чтобы быстро и качественно.
Как сделано сейчас:
1. Поле 50х50 случайно заполняется числами от 0 до 100.
2. Значения усредняются несколько раз - если в соседних клетках маленькие числа, число в клетке уменьшается, если большие, то увеличивается.
3. Если в клетке значение > 47 (получено эмпирическим путем), то там стена, иначе - пустое пространство.
4. Хитрым алгоритмом делаются проходы между не связанными областями, чтобы получить одну большую связанную пещеру.

Получается примерно такой результат:
Изображение

Проблема в хитром алгоритме на шаге 4. Он подтормаживает. Есть ли какие-нибудь другие хорошие способы достичь похожего результата?


#1
20:35, 1 апр. 2011

Просто на случай, если ты не знаешь,
http://roguebasin.roguelikedevelopment.org/index.php?title=Articles#Map

#2
21:02, 1 апр. 2011

// на шаге 4. Он подтормаживает
Ну и что ?
Сколько сейчас секунд делаются дополнительные дыры ?
Сколько хочеш ?

#3
21:43, 1 апр. 2011

>Проблема в хитром алгоритме на шаге 4. Он подтормаживает.

неприятно, но как часто генерация лабиринта вызывается?

#4
11:02, 2 апр. 2011

trleq
Ок, почитаю.

slatazan
dub
Зависит от браузера (забыл сказать что пишу на html5 + js). Пока терпимо, но если генерировать карты побольше, да несколько этажей, да с наполнением - будет долго.

#5
11:43, 2 апр. 2011

А что известно насчет алгоритма на шаге 4 кроме того, что он хитрый?

PS. Есть подозрение, что шаги 3 и 4 нужно объединить, и вместо эмпирического 47 использовать значение, вычисляемое по месту для данного фрагмента.

#6
11:54, 2 апр. 2011

Я конечно не спец в HTML5, но если генерировать все подземелья во время запуска игры и потом их просто хранить в памяти, это не лучший вариант?

#7
12:17, 2 апр. 2011

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

andriano
Хитрый алгоритм значит. Идем из любой пустой клетки, находим кратчайший путь алгоритмом Дейкстры, причем на длину пути влияют только клетки со стенами. То есть, каждый раз на очередном шаге выбираем клетку, на пути к которой стена минимальной толщины. Как только мы вышли на пустую клетку из "стены", пробиваем проход к ней. Повторять до тех пор, пока все пустые области не будут соединены.

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

#8
13:14, 2 апр. 2011

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

#9
13:36, 2 апр. 2011

TarasB
Граничное значение все равно должно быть около 50, иначе будет или очень маленькая пещерка, или наоборот на всю карту.

#10
13:47, 2 апр. 2011

Да, кстати, метод описанный в статье http://roguebasin.roguelikedevelopment.org/index.php?title=Basic_… on_generation выдает негодные результаты. Карта сразу делится пополам, например.
Изображение

#11
15:00, 2 апр. 2011

Bigfoot
> Граничное значение все равно должно быть около 50, иначе будет или очень
> маленькая пещерка, или наоборот на всю карту.

Проверил свою методу у себя.
Связность брал только по сторонам (по углу не брал).

Получил такое:

0............000......0............0..00
....0........0....................00....
00......00.......................000....
00.....000.........................00..0
..................0............0.....0..
....00............0.......000...........
...000...................000..........0.
........................0000..00......00
.....................0...00.....0......0
...............0.00.............0.......
0.....0....0...000.........0.0...0......
0...0.0........000.........00...........
...000..........0....0..............00.0
.....0.0..0.....00..00..........0000....
......000.......00...00.....0...........
........................0...............
.0...00.......0.........0.........00000.
0000.0.......000........0.....00..0000..
0000..........00..0...........0....00...
00...........................0.....00...

Короче отстой.

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

#12
16:23, 2 апр. 2011

Я такой алгоритм решил применить:
1. Пещера изначально пуста, без стен. Некоторые клетки помечаем, что там нельзя делать стены (там будут комнаты).
2. Выбираем случайную неотмеченную клетку, где ещё нет стены.
3. Смотрим, если поставить в эту клетку стенку, не станет ли пещера несвязной. Если не станет, то ставим стенку.

Пункт три делаем много-много раз, по вкусу.

Результат такой:

88888  88     8 88888888    888   88888  88888888888   88   888888888
8 8 88  8 888 8 88888888 88 88888  88888   8888   88 888888  888    8
8    88   8        888   8   88888 8 888 8 88 888 8  888888 8888888 8
  8 88   88 88888      888 888888  8 888 8     88   8    88  888888 8
888    8  8    888 8 8 8888888    88  8  888  8888    8 88   888888
8    88   8888 88 88  88888888 88   8 88888        8 88    888   88 88         8
8 8888888888    8 888   888888 88 8 8 88888 88888 88 8888 8    8 88888        88
8  8      8  88    8888 88 888 88 8   88888888888 88   8  8888 8   888 8     88
88888 888   88888   8   8  888 88 888  888888 8   88 88  8  88888 8888 88 88 88
  88   8888   88888 88888 88888   88888888  8   888 8888   88 88   888  8 88
8 888 88888 8888888    88   88  88888888888   8  88 888888  8    8     88 888 88
      88888 8 88888888  8 8  8 888888888 888888 888     888 8888 888 8888 8    8
 8888888888   888888888    888 8 8888    8888   8        888888   88 8888  8
  888888 8888     88 88888   8 8  888 88888 888           8 88888 88 88888888 8
8     8  8888 888 88   88  8 8 88 888 888   888 8           888   88   888888 8
 8 88   888888888888 8    88      888 8 888 8   8           888 888  88888888 88
   88 8 88   888888   88  88      888   888   888           8888    88  88888  8
8 8 88  8888    88888 888 8           8    888888         8    888 888 888    88
    88 88888 88888888  88 88     8 8888888 8888888       8      8        888888
 8 88  888   88 8 8888 88888     88888888     888       88             88 88888
 8 8888888 8      8888   88  8 8 88888888 888 888 88888 88            888   888
  8888     8888 88888888 8888888 8888 888 88        88888             88 88 8
 888888888 88    88   88  88 88888888 888  8888 8 8888888 8     8     8     88 8
  8 8888 888  8 88  8 888    8 8888   8888 888  88888888888    888 88888 88    8
8 8 8888 888 88    88     8 88 8888 88888   888 8 88888 888 888888   8 8   888 8
8        888 88 88  8 8888      88    88  8 88    8888   88 888888 8   888  8 88
8 8888  8  8 88  88 8 888888888    8888888  8  88 88   8  8     88 88 88888 8 88
8888   88 88 88 8 888888  88888 88  88888888888 8888 8  8   888 8888  88       8
8888 8888     8   8 88    8   88888 888   88888 8888  88888 888 88888 888888 8 8
8    888  888  88    888 88 8 88 88   8 8  8    88  8 8888  88888 8  8888888 888
888 8888 8       8 8     888     888 8888  88  888 88  88888  888 88          88
888888   8 88888 8888 88     8 888 8888888  8 8    888 88    8     88 8 88888  8
8   8888 8   88  88     888 88 888 88888888   8 88888    888 88 88 8  8 888888 8
888 88   888  8888  8 8  8888  88      88888 88    88888 888  888  8 8888888   8
888    8   8888  8888 88888888    888    888    888  88888888 8   88  8  88888 8
888 88 88888888 8 888 888888888888   8 8  88 888888 8  888888   8888 88 88888
8   88   88888     88 88 8888888   8 8888 88 8888     8888   88 8888    88  888
88 8888     88 88 888 88 888 888 8888888  88   8  888  88  8         8    8 8 8
88 8    888  8888  88        888    88888         8888 888 8888 8888 8888 8 8
8  8 88   8 888888  88 88 8888888 8888888          888 8 8 8888 88 888888   8
8 88 8888 888 88888     8   888 8 8888888         888      8 88 8      88 888
8 888  88 888 888888888  88  8    888888           88 8 888  8    8888 888888
8 888 8   888     8888888888   8888                8  888888   8   8  88888888
8888    888888888  8    8 88 888888 8 88           8888 888888 888   8 888 88888
8888 88 888      8        88 88888  8  88         8888  88 888 88  888     88888
 88  88 888 8888 88       88 888 88 88888           8   8    88888 88 8 8 8888
 88 8 8888  8888                  8 8 8888       88   8  8 8888888       88    8
 88   88888 888            888888 8   888888   8 88  888   88    8888 88    88 8
 888 8888    888           8888   8 8   88888888888 8888888888 8  8 8 88888 8888
      888 88 888888        8888 88888 8 88888888888     88888  88     8888888888

И пункт 3 надо делать не в лоб, у меня каждая стенка хранит номер своей компоненты связности.

#13
16:28, 2 апр. 2011

Ещё вариант:

██ ████    █████  ██ ███████████████████
██ ████ ██    ███ █  █    ██  █████ ████
█  ████ █████ ███   ██ ████  ██████
█   ███ ███████         ███ ██ ███ █ ██
█ █     ███████       ████  ██   █   ██
███ █ ████████             █████ █ ███
███ ████ █████          █ █████    ███ █
███ ████  ██ █          █████     ████
███     █             ████    █   ██████
█   █████ ████        █████████   ██████
█  ██████ ████ ██   ██   █████  █ ██████
██ ███ ████    █    ██ ███████ ██   ████
██ ███    ███  ██████  ██████████ █
██         █   ████   █████   █   █
█  █       █ █   ████  ██████  ████
█ █          █████         ███  ███
█ █         █████   █  ███    █  ██
  █         ██    █ ██  ██ ██   ███ ████
████       ███ ███  ██████████  █     ██
███         ██  ██ ██████  ██  █       █
███ ██    █████  █ ███████ ██ ██       █
███  ██████████ █████   ██ ██
█     ███  ████ ███████    █████       █
█ █  ████ ██    █████ ████ ████        █
  █ ██     ████  ████ ████ ██   █
 ██    ███    ██  ███ ████ █ ████ ████
 ███ ██ █     ███ ███ ████     ██  ███
████  █ █     █       ███        ███   █
█████   █     █████  █ ██       ███
███████ ██   ██████ ██
██  ███ ███  █      █████       ██
███ ███ ████        ██ █        ███    █
██      ████           ███     █████████
████ ███████        ████████  ████ █████
████ ████████          ██████ ██    ████
████ ██     █       ████████      █
████  █████        ████ ███  █ ██████ ██
█  ██ █████ █████   ██  █   █  ███     █
██ █  ██    ████  █    ██████ ███████ ██
██   ████████████ ███████████████████  █

#14
17:00, 2 апр. 2011

TarasB
Выглядит не очень.
Как определяешь где комнаты будут?
Как определяешь что пещера останется связной?

Страницы: 1 2 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.