Генерация мира

Темы, связанные с проектированием и программированием roguelike-игр

Модераторы: Sanja, Максим Кич

ADB

Генерация мира

Сообщение ADB » 10 фев 2007, 10:51

Меня очень интересует вопрос автоматического создания карт мира, поэтому я решил открыть эту тему. На данный момент существует множество алгоритмов создания многосложных карт местности. На сайте клуба, насколько я помню, можно найти несколько полезных статей. В последнее время я изучал шедевр под названием Dwarf Fortress. Здесь картогенерация идет на достаточно высоком уровне. Только посмотрите, какие красивые карты генерит программа
http://templer-world.narod.ru/world_map-1-1050-0.GIF (1,3 Мб)
Так же неплохим примером качественного генератора карт может послужить игра Warlords, которая умеет создавать рандомные карты в соответствии с исходными параметрами, задаваемыми пользователем, учитывая количество воды, леса, гор, рек, число островов и т.п.

Есть ли у кого-нибудь соображения, как реализуются такие технологии?

Аватара пользователя
Maelstrom
Мастер
Сообщения: 2062
Зарегистрирован: 26 ноя 2006, 14:19
Откуда: г. Усть-Кирдык
Контактная информация:

Сообщение Maelstrom » 10 фев 2007, 13:53

Фракталами. Хотя я даже не очень знаю, что это такое.
Айв кнгенгах Йог-Сотот

Аватара пользователя
reincarnation
Сообщения: 33
Зарегистрирован: 25 ноя 2006, 22:24
Откуда: Москва

Сообщение reincarnation » 11 фев 2007, 12:11

Maelstrom писал(а):Фракталами. Хотя я даже не очень знаю, что это такое.
Это множества, у к-рых Хаусдорфова размерность не совпадает с топологической. Правда, из определения не видно, как их в генерации использовать :)

Аватара пользователя
Alchemist
Мастер
Сообщения: 203
Зарегистрирован: 13 дек 2006, 09:15
Откуда: Нижний Тагил, Иваново
Контактная информация:

Сообщение Alchemist » 11 фев 2007, 13:04

Так же неплохим примером качественного генератора карт может послужить игра Warlords, которая умеет создавать рандомные карты в соответствии с исходными параметрами, задаваемыми пользователем, учитывая количество воды, леса, гор, рек, число островов и т.п.
Найдите сайт open-source игры CivEvo2 (правда она на Delphi сварганена). Там именно такой настраиваемый, очень шикарный генератор карт. Алгоритм генерит замкнутую карту мира с континентами, морями, реками, озерами, горами, равнинами и т.п. Все довольно правдоподобно. Правда там кажется нигде не сказано, что автор разрешает использовать его алгоритмы, но для ознакомления - подойдет.

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Сообщение Максим Кич » 13 фев 2007, 23:30

reincarnation писал(а):
Maelstrom писал(а):Фракталами. Хотя я даже не очень знаю, что это такое.
Это множества, у к-рых Хаусдорфова размерность не совпадает с топологической. Правда, из определения не видно, как их в генерации использовать :)
Вообще-то статья есть. На этом же самом сайте ;)
Dump the screen? [y/n]

ADB

Сообщение ADB » 16 фев 2007, 11:39

А есть ли у кого-нибудь алгоритм или программа на любом языке (кроме ассемблера :lol: ), демонстрирующая такие вещи?

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Сообщение Максим Кич » 21 фев 2007, 11:06

ADB писал(а):А есть ли у кого-нибудь алгоритм или программа на любом языке (кроме ассемблера :lol: ), демонстрирующая такие вещи?
Примитивно, собрано на коленке за полчаса из которых большую часть времени я искал весьма тупую ошибку. Но общее представление даёт.
4 вида ландшафта, разность высот не рассматривается.

Простой фрактальный генератор ландшафта

Принцип работы:

1. Строим квадрат 2*2, заполняем:

Код: Выделить всё

1 2
3 4
2. Увеличиваем квадрат в два раза:

Код: Выделить всё

1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
3. Подставляем во все поля кроме угловых значения случайной соседней клетки, получаем что-то вроде

Код: Выделить всё

1 2 2 2
1 1 4 2
3 2 1 4
3 3 3 4
4. Повторяем с пункта 2, пока размеры не начнут нас устраивать.

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

Можно увеличить количество стартовых клеток, тогда результаты будут интереснее. Для ландшафта с учётом высот алгоритм похожий, но требует доработки... Как-нибудь выложу.
Dump the screen? [y/n]

Аватара пользователя
Maelstrom
Мастер
Сообщения: 2062
Зарегистрирован: 26 ноя 2006, 14:19
Откуда: г. Усть-Кирдык
Контактная информация:

Сообщение Maelstrom » 21 фев 2007, 12:18

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

ADB

Сообщение ADB » 21 фев 2007, 17:31

Гениально интересная и простая идея, Максим. Вопрос, что получится, если я увеличу масштаб в 10 раз? У тебя нет примера такой программки (своей или чужой)?
И что ты бы поставил, дял примера, под цифры 1,2,3,4?

ADB

Сообщение ADB » 21 фев 2007, 22:45

ADB писал(а):Гениально интересная и простая идея, Максим. Вопрос, что получится, если я увеличу масштаб в 10 раз? У тебя нет примера такой программки (своей или чужой)?
И что ты бы поставил, дял примера, под цифры 1,2,3,4?
Все понял. Извини, ссылку не заметил. Видимо сегодня переработал чуток :D

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Сообщение Максим Кич » 22 фев 2007, 14:38

ADB писал(а):
ADB писал(а):Гениально интересная и простая идея, Максим. Вопрос, что получится, если я увеличу масштаб в 10 раз? У тебя нет примера такой программки (своей или чужой)?
И что ты бы поставил, дял примера, под цифры 1,2,3,4?
Все понял. Извини, ссылку не заметил. Видимо сегодня переработал чуток :D
Тут интересно, что можно выбрать произвольный прямоугольник из полученной карты и снова подать на вход алгоритма. И, кроме того, если использовать собственный random, то весь пейзаж на жёстком диске можно хранить в трёх-четырёх байтах.

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

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

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

В итоге, в цельной породе у нас получаются круглые (по умолчанию) пещеры, соединённые замысловатыми туннелями.
Dump the screen? [y/n]

ADB

Сообщение ADB » 22 фев 2007, 15:19

Да-а-а, Максим, ты просто кладезь знаний! Много интересного предлагаешь. Спасибо.

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

Максим Кич писал(а):И, кроме того, если использовать собственный random, то весь пейзаж на жёстком диске можно хранить в трёх-четырёх байтах.
Да, мне более чем известны такие методы. Могу выложить отличный пример родного генератора "стабильных" случайных чисел игры ELITE, с помощью которого можно получить астрономическое колличество миров (ландшафтов), обходясь всего лишь 4-мя байтами в сохранении.
Максим Кич писал(а):Была ещё мысль, которую я никак не откатаю: берётся карта, которую мы по умолчанию считаем заполненной целиком. Случайно распределяем по карте источники гравитации. Вырезаем в этих точках, например, круги. Из этих точек выбрасываем со случайным вектором ускорения частицы случайной массы. Отслеживаем их полёт в гравитационном поле, пока они не свалятся ещё в какой-нибудь источник гравитации. Следы, оставленные частицами, тоже вырезаем.

В итоге, в цельной породе у нас получаются круглые (по умолчанию) пещеры, соединённые замысловатыми туннелями.
Вот оно! Нужная весчь! Хотелось бы развить эту тему до демонстрационного алгоритма. Я сейчас пытался придумать подобный генератор подземелий, который бы мог делать достаточно логичные подземелья с непрямыми коридорами, расширениями и сужениями, перекрестиями и тупиками. Для этого я расматривал двидение различных по размеру частиц...
Изначально у нас существует полностью заполненное "землей" пространство. Потом мы выбираем точку пуска и оттуда запускаем "горящие" цастицы, различного размера. Эти частицы прожигают все на своем пути, делая в заполненом массиве коридоры. Надо научится математически задавать характер их движения, скорость и инерцию. Чтобы они двигались не прямолинейно, хаотически, но по определенным правилам. Словно шаровая молния :) С этим мне пока трудно разбирается.

Аватара пользователя
Maelstrom
Мастер
Сообщения: 2062
Зарегистрирован: 26 ноя 2006, 14:19
Откуда: г. Усть-Кирдык
Контактная информация:

Сообщение Maelstrom » 22 фев 2007, 19:15

Была ещё мысль, которую я никак не откатаю: берётся карта, которую мы по умолчанию считаем заполненной целиком. Случайно распределяем по карте источники гравитации. Вырезаем в этих точках, например, круги. Из этих точек выбрасываем со случайным вектором ускорения частицы случайной массы. Отслеживаем их полёт в гравитационном поле, пока они не свалятся ещё в какой-нибудь источник гравитации. Следы, оставленные частицами, тоже вырезаем.
Рассчитывается векторное поле сил гравитации от этих "дырок" и потом рассматривается движение частиц под действитем этого поля? Я правильно понял?
Айв кнгенгах Йог-Сотот

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Сообщение Максим Кич » 22 фев 2007, 21:45

ADB писал(а): По поводу фрактального генератора, я вчера мучался со своим примером по твоему алгоритму, результаты действительно удивительные. Не сегодня - завтра выложу сие на всеобщее обозрение для заинтересованных этой проблематикой.
Вопрос. А есть ли способы еще более усовершенствовать представленный алгоритм?
Алгоритм не мой, а честно списанный. Статьи по роглайкостроительству - вот настоящая кладезь, если подходить с умом.

Есть модификация, которая выстраивает рельеф, достаточно распространённая, надо заметить. Если генерировать более-менее правдоподобный ландшафт, то даже с двухмерной картой будет логично пользоваться таким. Тогда мы автоматом можем распределять типы местности по высоте над уровнем моря и достаточно реалистично отображать водные объекты. Плюс, исходя из этого мы получим неплохую затравку для «озеленения» местности.
Максим Кич писал(а):И, кроме того, если использовать собственный random, то весь пейзаж на жёстком диске можно хранить в трёх-четырёх байтах.
Да, мне более чем известны такие методы. Могу выложить отличный пример родного генератора "стабильных" случайных чисел игры ELITE, с помощью которого можно получить астрономическое колличество миров (ландшафтов), обходясь всего лишь 4-мя байтами в сохранении.[/quote]

Ну, у меня под рукой формула генератора с периодом 2^158 (конкретно - нелинейный конгруэнтный), но думаю, что это тоже не лучший вариант.
ADB писал(а): Изначально у нас существует полностью заполненное "землей" пространство. Потом мы выбираем точку пуска и оттуда запускаем "горящие" цастицы, различного размера. Эти частицы прожигают все на своем пути, делая в заполненом массиве коридоры. Надо научится математически задавать характер их движения, скорость и инерцию. Чтобы они двигались не прямолинейно, хаотически, но по определенным правилам. Словно шаровая молния :) С этим мне пока трудно разбирается.
Вот поэтому я и взял движение частиц в гравитационном поле. Другой вариант постоения извилистых пещер пришёл мне практически только что: выстраиваем методом фрактального деления рельеф. Размещаем в вершинах (n самых высоких точек рельефа) и в смежных точках, «горящие частицы». И отпускаем на произвол гравитации. Частицы покатятся к аттракторам, т.е. в нашем случае к самым низким точкам рельефа, и там снова соберутся. Другой вопрос, что рельеф надо будет строить из соображения отсутствия промежуточных «впадин», либо просчитывать для частиц инерцию, чтобы они не застрявали на полдороги.

Короче говоря, фракталы - это наше всё :lol:
Dump the screen? [y/n]

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Сообщение Максим Кич » 22 фев 2007, 21:47

Maelstrom писал(а):Рассчитывается векторное поле сил гравитации от этих "дырок" и потом рассматривается движение частиц под действитем этого поля? Я правильно понял?
Ну да, я как-то сумбурно выразился. В примерах к FreePascal есть игрушка Gravity Wars... кстати, хорошо что вспомнил, надо будет оттуда выдрать часть кода.
Dump the screen? [y/n]

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 3 гостя