Генерация мира
Модераторы: Sanja, Максим Кич
Генерация мира
Меня очень интересует вопрос автоматического создания карт мира, поэтому я решил открыть эту тему. На данный момент существует множество алгоритмов создания многосложных карт местности. На сайте клуба, насколько я помню, можно найти несколько полезных статей. В последнее время я изучал шедевр под названием Dwarf Fortress. Здесь картогенерация идет на достаточно высоком уровне. Только посмотрите, какие красивые карты генерит программа
http://templer-world.narod.ru/world_map-1-1050-0.GIF (1,3 Мб)
Так же неплохим примером качественного генератора карт может послужить игра Warlords, которая умеет создавать рандомные карты в соответствии с исходными параметрами, задаваемыми пользователем, учитывая количество воды, леса, гор, рек, число островов и т.п.
Есть ли у кого-нибудь соображения, как реализуются такие технологии?
http://templer-world.narod.ru/world_map-1-1050-0.GIF (1,3 Мб)
Так же неплохим примером качественного генератора карт может послужить игра Warlords, которая умеет создавать рандомные карты в соответствии с исходными параметрами, задаваемыми пользователем, учитывая количество воды, леса, гор, рек, число островов и т.п.
Есть ли у кого-нибудь соображения, как реализуются такие технологии?
- reincarnation
- Сообщения: 33
- Зарегистрирован: 25 ноя 2006, 22:24
- Откуда: Москва
- Alchemist
- Мастер
- Сообщения: 203
- Зарегистрирован: 13 дек 2006, 09:15
- Откуда: Нижний Тагил, Иваново
- Контактная информация:
Найдите сайт open-source игры CivEvo2 (правда она на Delphi сварганена). Там именно такой настраиваемый, очень шикарный генератор карт. Алгоритм генерит замкнутую карту мира с континентами, морями, реками, озерами, горами, равнинами и т.п. Все довольно правдоподобно. Правда там кажется нигде не сказано, что автор разрешает использовать его алгоритмы, но для ознакомления - подойдет.Так же неплохим примером качественного генератора карт может послужить игра Warlords, которая умеет создавать рандомные карты в соответствии с исходными параметрами, задаваемыми пользователем, учитывая количество воды, леса, гор, рек, число островов и т.п.
- Максим Кич
- Администратор
- Сообщения: 1642
- Зарегистрирован: 03 дек 2006, 20:17
- Откуда: Витебск, Беларусь
- Контактная информация:
Вообще-то статья есть. На этом же самом сайтеreincarnation писал(а):Это множества, у к-рых Хаусдорфова размерность не совпадает с топологической. Правда, из определения не видно, как их в генерации использоватьMaelstrom писал(а):Фракталами. Хотя я даже не очень знаю, что это такое.
Dump the screen? [y/n]
- Максим Кич
- Администратор
- Сообщения: 1642
- Зарегистрирован: 03 дек 2006, 20:17
- Откуда: Витебск, Беларусь
- Контактная информация:
Примитивно, собрано на коленке за полчаса из которых большую часть времени я искал весьма тупую ошибку. Но общее представление даёт.ADB писал(а):А есть ли у кого-нибудь алгоритм или программа на любом языке (кроме ассемблера ), демонстрирующая такие вещи?
4 вида ландшафта, разность высот не рассматривается.
Простой фрактальный генератор ландшафта
Принцип работы:
1. Строим квадрат 2*2, заполняем:
Код: Выделить всё
1 2
3 4
Код: Выделить всё
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
Код: Выделить всё
1 2 2 2
1 1 4 2
3 2 1 4
3 3 3 4
В своей программе я рассматривал тор, поэтому на больших итерациях карту можно считать замкнутой (на малых будут некоторые нестыковки на границах)
Можно увеличить количество стартовых клеток, тогда результаты будут интереснее. Для ландшафта с учётом высот алгоритм похожий, но требует доработки... Как-нибудь выложу.
Dump the screen? [y/n]
- Максим Кич
- Администратор
- Сообщения: 1642
- Зарегистрирован: 03 дек 2006, 20:17
- Откуда: Витебск, Беларусь
- Контактная информация:
Тут интересно, что можно выбрать произвольный прямоугольник из полученной карты и снова подать на вход алгоритма. И, кроме того, если использовать собственный random, то весь пейзаж на жёстком диске можно хранить в трёх-четырёх байтах.ADB писал(а):Все понял. Извини, ссылку не заметил. Видимо сегодня переработал чутокADB писал(а):Гениально интересная и простая идея, Максим. Вопрос, что получится, если я увеличу масштаб в 10 раз? У тебя нет примера такой программки (своей или чужой)?
И что ты бы поставил, дял примера, под цифры 1,2,3,4?
Разумеется, на деле должен использоваться более сложный генератор, но суть остаётся неизменной.
Я ещё наблюдал статью про рекурсивное построение подземелий, но мне, откровенно, не понравилось, что алгоритм выдаёт на-гора...
Была ещё мысль, которую я никак не откатаю: берётся карта, которую мы по умолчанию считаем заполненной целиком. Случайно распределяем по карте источники гравитации. Вырезаем в этих точках, например, круги. Из этих точек выбрасываем со случайным вектором ускорения частицы случайной массы. Отслеживаем их полёт в гравитационном поле, пока они не свалятся ещё в какой-нибудь источник гравитации. Следы, оставленные частицами, тоже вырезаем.
В итоге, в цельной породе у нас получаются круглые (по умолчанию) пещеры, соединённые замысловатыми туннелями.
Dump the screen? [y/n]
Да-а-а, Максим, ты просто кладезь знаний! Много интересного предлагаешь. Спасибо.
По поводу фрактального генератора, я вчера мучался со своим примером по твоему алгоритму, результаты действительно удивительные. Не сегодня - завтра выложу сие на всеобщее обозрение для заинтересованных этой проблематикой.
Вопрос. А есть ли способы еще более усовершенствовать представленный алгоритм?
Изначально у нас существует полностью заполненное "землей" пространство. Потом мы выбираем точку пуска и оттуда запускаем "горящие" цастицы, различного размера. Эти частицы прожигают все на своем пути, делая в заполненом массиве коридоры. Надо научится математически задавать характер их движения, скорость и инерцию. Чтобы они двигались не прямолинейно, хаотически, но по определенным правилам. Словно шаровая молния С этим мне пока трудно разбирается.
По поводу фрактального генератора, я вчера мучался со своим примером по твоему алгоритму, результаты действительно удивительные. Не сегодня - завтра выложу сие на всеобщее обозрение для заинтересованных этой проблематикой.
Вопрос. А есть ли способы еще более усовершенствовать представленный алгоритм?
Да, мне более чем известны такие методы. Могу выложить отличный пример родного генератора "стабильных" случайных чисел игры ELITE, с помощью которого можно получить астрономическое колличество миров (ландшафтов), обходясь всего лишь 4-мя байтами в сохранении.Максим Кич писал(а):И, кроме того, если использовать собственный random, то весь пейзаж на жёстком диске можно хранить в трёх-четырёх байтах.
Вот оно! Нужная весчь! Хотелось бы развить эту тему до демонстрационного алгоритма. Я сейчас пытался придумать подобный генератор подземелий, который бы мог делать достаточно логичные подземелья с непрямыми коридорами, расширениями и сужениями, перекрестиями и тупиками. Для этого я расматривал двидение различных по размеру частиц...Максим Кич писал(а):Была ещё мысль, которую я никак не откатаю: берётся карта, которую мы по умолчанию считаем заполненной целиком. Случайно распределяем по карте источники гравитации. Вырезаем в этих точках, например, круги. Из этих точек выбрасываем со случайным вектором ускорения частицы случайной массы. Отслеживаем их полёт в гравитационном поле, пока они не свалятся ещё в какой-нибудь источник гравитации. Следы, оставленные частицами, тоже вырезаем.
В итоге, в цельной породе у нас получаются круглые (по умолчанию) пещеры, соединённые замысловатыми туннелями.
Изначально у нас существует полностью заполненное "землей" пространство. Потом мы выбираем точку пуска и оттуда запускаем "горящие" цастицы, различного размера. Эти частицы прожигают все на своем пути, делая в заполненом массиве коридоры. Надо научится математически задавать характер их движения, скорость и инерцию. Чтобы они двигались не прямолинейно, хаотически, но по определенным правилам. Словно шаровая молния С этим мне пока трудно разбирается.
- Maelstrom
- Мастер
- Сообщения: 2062
- Зарегистрирован: 26 ноя 2006, 14:19
- Откуда: г. Усть-Кирдык
- Контактная информация:
Рассчитывается векторное поле сил гравитации от этих "дырок" и потом рассматривается движение частиц под действитем этого поля? Я правильно понял?Была ещё мысль, которую я никак не откатаю: берётся карта, которую мы по умолчанию считаем заполненной целиком. Случайно распределяем по карте источники гравитации. Вырезаем в этих точках, например, круги. Из этих точек выбрасываем со случайным вектором ускорения частицы случайной массы. Отслеживаем их полёт в гравитационном поле, пока они не свалятся ещё в какой-нибудь источник гравитации. Следы, оставленные частицами, тоже вырезаем.
Айв кнгенгах Йог-Сотот
- Максим Кич
- Администратор
- Сообщения: 1642
- Зарегистрирован: 03 дек 2006, 20:17
- Откуда: Витебск, Беларусь
- Контактная информация:
Алгоритм не мой, а честно списанный. Статьи по роглайкостроительству - вот настоящая кладезь, если подходить с умом.ADB писал(а): По поводу фрактального генератора, я вчера мучался со своим примером по твоему алгоритму, результаты действительно удивительные. Не сегодня - завтра выложу сие на всеобщее обозрение для заинтересованных этой проблематикой.
Вопрос. А есть ли способы еще более усовершенствовать представленный алгоритм?
Есть модификация, которая выстраивает рельеф, достаточно распространённая, надо заметить. Если генерировать более-менее правдоподобный ландшафт, то даже с двухмерной картой будет логично пользоваться таким. Тогда мы автоматом можем распределять типы местности по высоте над уровнем моря и достаточно реалистично отображать водные объекты. Плюс, исходя из этого мы получим неплохую затравку для «озеленения» местности.
Да, мне более чем известны такие методы. Могу выложить отличный пример родного генератора "стабильных" случайных чисел игры ELITE, с помощью которого можно получить астрономическое колличество миров (ландшафтов), обходясь всего лишь 4-мя байтами в сохранении.[/quote]Максим Кич писал(а):И, кроме того, если использовать собственный random, то весь пейзаж на жёстком диске можно хранить в трёх-четырёх байтах.
Ну, у меня под рукой формула генератора с периодом 2^158 (конкретно - нелинейный конгруэнтный), но думаю, что это тоже не лучший вариант.
Вот поэтому я и взял движение частиц в гравитационном поле. Другой вариант постоения извилистых пещер пришёл мне практически только что: выстраиваем методом фрактального деления рельеф. Размещаем в вершинах (n самых высоких точек рельефа) и в смежных точках, «горящие частицы». И отпускаем на произвол гравитации. Частицы покатятся к аттракторам, т.е. в нашем случае к самым низким точкам рельефа, и там снова соберутся. Другой вопрос, что рельеф надо будет строить из соображения отсутствия промежуточных «впадин», либо просчитывать для частиц инерцию, чтобы они не застрявали на полдороги.ADB писал(а): Изначально у нас существует полностью заполненное "землей" пространство. Потом мы выбираем точку пуска и оттуда запускаем "горящие" цастицы, различного размера. Эти частицы прожигают все на своем пути, делая в заполненом массиве коридоры. Надо научится математически задавать характер их движения, скорость и инерцию. Чтобы они двигались не прямолинейно, хаотически, но по определенным правилам. Словно шаровая молния С этим мне пока трудно разбирается.
Короче говоря, фракталы - это наше всё
Dump the screen? [y/n]
- Максим Кич
- Администратор
- Сообщения: 1642
- Зарегистрирован: 03 дек 2006, 20:17
- Откуда: Витебск, Беларусь
- Контактная информация:
Ну да, я как-то сумбурно выразился. В примерах к FreePascal есть игрушка Gravity Wars... кстати, хорошо что вспомнил, надо будет оттуда выдрать часть кода.Maelstrom писал(а):Рассчитывается векторное поле сил гравитации от этих "дырок" и потом рассматривается движение частиц под действитем этого поля? Я правильно понял?
Dump the screen? [y/n]
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 22 гостя