Рекурсивная генерация карты мира - Программинг - Программинг - Каталог статей - Развлекательный сайт для программистов-игроделов

Категории каталога

Программинг [38]
Программинг, уроки, формулы, туториалы
Dark Basic [31]
Помощь начинающим в Dark Basic (Статьи,учебники,книги)
Blitz 3d [7]
Статьи и уроки по Blitz 3d
C/C++ [8]
Статьи по C/C++
Delphi [12]
книги, уроки, статьи, программирование в Delphi
Game Maker [12]
Статьи, помощь для программистов игроделов на Game Maker
Ассемблер (Assembler) [5]
Стати по Ассемблеру для начинающих и продвинутых программистов
ВЕБ-ПРОГРАММИРОВАНИЕ [5]
Уроки и статьи по ВЕБ-программированию
Scirra Construct [0]

Форма входа

Приветствую Вас Гость!

Логин:
Пароль:

Поиск

Друзья сайта



    Случайное фото

    Статистика

    Онлайн всего: 4
    Гостей: 4
    Пользователей: 0

Поддержите наш проект

WebMoney:
R309699065243
U292079291240
Z373355457648

Счётчики


Rambler's Top100
Рейтинг@Mail.ru

Наш опрос

Почему люди пьют?
Всего ответов: 54

Статистика

$COUNTERdiv>

Каталог статей

Главная » Статьи » Программинг » Программинг

Рекурсивная генерация карты мира

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

Пожалуйста имейте в виду, что это - алгоритм построения карты мира. Я могу представить, что если Вы используете этот метод, чтобы генерировать, скажем, подземелье, то Вы получите очень смешанные результаты. Сказав это, начнём.

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

 #define MAXWIDTH 30
 #define MAXHEIGHT 30

 struct terrain
 {
 char name[10]; //название типа местности
 int mc; //стоимость передвижения по местности
 };

 terrain plain = {"Plains", 3}; (Равнины)
 terrain forest = {"Forest", 5}; (Лес)
 terrain hills = {"Hilles", 8}; (Холмы)

 terrain map[MAXWIDTH][MAXHEIGHT]; //массив, с которым будет работать алгоритм

Теперь, когда мы определили мою структуру и несколько её примеров, реализация моего алгоритма пойдёт примерно так: у меня есть три главных функции - ReturnTerrain(), CreateMap(), и CreateArea(). ReturnTerrain просто возвращает структуру местности определенного типа. CreateMap, как легко можно представить, проходит через каждую ячейку моего двумерного массива местности и вызывает функцию необходимую для генерации этой местности, а именно: CreateArea. Как мы увидим, CreateMap вероятно не потребуется более одного раза вызывать CreateArea, но я почувствовал, что будет надёжнее запланировать все возможности, если я смогу. CreateMap также генерирует произвольное "seed-число", которое соответствует одному из моих типов местности (напр. 0-6). Это число затем переходит в CreateArea.

Функция CreateArea - место, где алгоритм начинает принимать форму. Я основывал свою область создания значений (area-creation values) на предположении, что конкретный тип местности (в моем случае, в ячейках, представляющих область около 1 квадратного километра), вероятно будет соприкасаться с аналогичными типами местности (заметим, что этот алгоритм не включает часть "сглаживания" (smoothing portion) - это оставлено читателю если ваша программа потребует этого). Например, область, состоящая по большей части из равнин вероятно будет иметь вокруг себя в основном равнины, а также немного дополнительных типов местности (скажем, лес), который также вероятно будет соприкасаться со своей собственным конкретным набором типов местности (например: холмами).

Функция CreateArea сначала ищет ячейку карты, которая ещё не заполнена. Кроме того, хотя вряд ли, чтобы CreateArea должна вызываться более чем один раз, в моем случае я хотел учесть более высокую степень детализации не допуская чтобы CreateArea перезаписывала любую ранее записанную область. Если Вы хотите наслаивать вашу местность, Вы можете задать, чтобы CreateArea делала несколько "проходов" по вашему массиву карты. Это оставлено читателю, если он того захочет.

 //Заметим, что массив карты[][] был инициализирован заблаговременно
 CreateArea(int seed)
 for (x < MAXWIDTH)
 for (y < MAXHEIGHT)
 if map[x][y].mc == 0 //устанавливается во время инициализации
 set map[x][y] = ReturnTerrain(seed)

Как только обнаружена незаполненная ячейка карты, CreateArea помещает в неё "семя" (seed) типа местности. Затем, используя пару циклов CreateArea начинает решать какой тип местности должен быть в каждой из восьми соседних ячеек карты, основываясь на установленных программистом "правилах".

for (loop from x-1 to x+1) //помня о проверке границ массива
for (loop from y-1 to y+1) //проверяем правила, чтобы видеть какого типа каждая ячейка

Эти "правила", в моем случае, достаточно просты. Например, если тип ячейки местности, скажем, равнины, тогда четыре или пять из восьми ячеек вокруг неё вероятно также будут равнинами. Основываясь на своём собственном опыте, я почувствовал, что лес часто соседствовует с открытыми "равнинными" областями - так что каждая из других трёх или четырёх ячеек может быть лесом. Лес, с другой стороны, вероятно будет соседствовать с холмами, и так процесс может повторяться. Тем не менее, это может вызвать некоторую блокировку местности если мы не включим "регрессивный" признак, который должен потенциально позволять типу местности, порождать свой генератор - в моем случае, я предусмотрел такую возможность при каждой проверке правил.

Например, хотя лес вероятно (в моем мире), соседствует с холмами, он также вероятно будет соседствовать и с равнинами, что подтверждается тем, что равнины генерируют леса. Так, при "вероятности" кратной десяти, восемь ячеек вокруг ячейки леса в соответствии с моими правилами будут:

  • с вероятностью 40-50% - лесом
  • с вероятностью 20-40% - холмом
  • и с вероятностью 10-40% - равниной

(заметим, что данный пример псевдо-кода упрощает эти вероятности)

 //не забывайте убеждаться, что эта ячейка карты пустая
 chance = randomnumber(10)
 if (chance < 5)
 map[looped x][looped y] = ReturnTerrain(seed)
 if (chance >= 5 and chance < 8)
 map[looped x][looped y] = ReturnTerrain(seed+1)
 if (chance >= 8)
 map[looped x][looped y] = ReturnTerrain(seed-1)

Из этих восьми ячеек, произвольно, одна ячейка и соответствующий ей тип местности выбирается новой ячейкой "семенем" (seed), и соответственно вызывается CreateArea. (Пожалуйста заметьте, что рекурсивно вызываемой функцией CreateArea должны переписываться *только* ячейки, в которых в настоящее время нет местности.)

 chanceofseed = randomnumber(8)
 if (chanceofseed == 1)
 CreateArea(int value of map[x-1][y-1])

и так далее...

Новое семя может быть любым из двух порожденных типов местности, или порождающего типа местности. Таким образом, карта создается рекурсивно и произвольно, несмотря на то, что это по большей части соответствует заданию правил местности. Если кто-нибудь чем-либо заинтересовался в этом алгоритме и хочет кинуть мне строчку или Вы хотите от меня каких-либо разъяснений, пишите мне на pcullit@hotmail.com. К тому же, если у Вас есть комментарии, предложения или жалобы, пожалуйста, также пишите по тому же адресу.

Чтобы закруглиться, я хотел бы выразить свою благодарность всем, кто писал свои алгоритмы и идеи по генерации карт на Dungeondweller'е. Я украл так много вашего кода и идей, что я чувствую, что похоже все мы друг друга знаем. :) Благодарю и надеюсь, что для кого-нибудь из вас что-то из этого будет полезно.

Автор: Phillip C. Culliton.

Перевел: Дмитрий О. Бужинский, 27.02.2006.

Категория: Программинг | Добавил: quadrathell (08.05.2013)
Просмотров: 1134 | Рейтинг: 0.0/0 |
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]