Фрактальные ландшафты

Материал из Клуб любителей рогаликов
Перейти к: навигация, поиск

Данная статья была написана для RLNews Darren'а Hebden'а

Введение

Вот кое-что особенное о фракталах. Возможно, это путь, при помощи которого из самых простых математических формул появляются бесконечно сложные формы.....

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

Здесь я собираюсь представить основной алгоритм фракталов, который был первоначально разработан для генерации произвольных островов, морей и побережий. С несколькими незначительными изменениями, он может быть легко приспособлен для создания всех типов естественных форм ландшафта. Мой алгоритм отдалённо основан на знакомом типе "плазмы" рекурсивного поля высот но модифицирован, чтобы работать с тайловыми картами.

В конце этой статьи я включил исходник для ввода простого Java-генератора побережья. Если вам невтерпёж и хочется немедленно увидеть работающую версию, просто сходите на: http://www.mikera.net/code/coastline.html

Алгоритм фрактала

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

Скажем, вы рассматриваете квадратную область вашей карты с углами помеченными как a, b, c и d:

a * b

* * *

c * d

Каждый квадрат карты может иметь разный цвет. Я использовал зеленый для земли и синий для моря в приводимом примере ввода.

Затем алгоритм определит цвета карты для промежуточных точек, помеченных "*". Это делается случайным выбором цвета одного из смежных угловых квадратов. "*" в центре может принимать цвета a, b, c или d.

Таким образом, возможный конечный результат может быть:

a a b

c b d

c c d

Теперь мы определяем на карте меньшие квадраты. Алгоритм затем может итеративно применяться к меньшему масштабу. Этот процесс продолжается пока не будет достигнут желаемый уровень детализации.

a*a*b
*****
c*b*d
*****
c*c*d

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

Пример

Ниже показаны итерации для сетки 16*16.

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

Кроме того, что карта рассматривается как тороидальная, то есть точки по левому краю будут совмещаться с точками по правому краю, и аналогично для верхнего и нижнего краёв.

Шаг 1:

a-------b#######
--------########
--------########
--------########
--------########
--------########
--------########
--------########
c#######d-------
########--------
########--------
########--------
########--------
########--------
########--------
########--------

(a, b, c и d отмечают как точки были окрашены в начале. Это можно делать произвольно или задать их предварительно, чтобы создавать области земли)

Шаг 2:

--------########
--------########
--------########
--------########
########----####
########----####
########----####
########----####
----####--------
----####--------
----####--------
----####--------
############----
############----
############----
############----

Шаг 3:

------########--
------########--
--##----########
--##----########
########----####
########----####
######--------##
######--------##
----####--------
----####--------
----##----------
----##----------
##########------
##########------
##--########----
##--########----

Шаг 4:

-----########---
------########--
-##-----########
--##----#--#####
########----####
########-----###
######--------##
#-####--------#-
----####--------
---####---------
---###----------
-#--#--#--------
##########-----#
#########-#-----
##-#########----
#----######-----

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

Код

Вот быстрая Java-реализация фрактального алгоритма побережья. Она генерирует новый ландшафт всякий раз, когда апплет перерисовывается.

Фактически, всю работу делает метод makeFractal(step). Этот метод вызывает сам себя для более тонкого управления детализацией уровней.

========= CoastApp.java ==========
package kult.quest;

import java.awt.*;
import java.applet.*;
import java.awt.event.*;

public class CoastApp extends Applet {

  // размер карты: должен быть степенью 2
  public static final int size=128;

  // распределить память
  public int[] map= new int[size*size];

  public void paint(Graphics g) {
    super.paint(g);

    // начальный шаблон (0=море, 1=земля)
    setCell(0,0,0);
    setCell(size/2,0,0);
    setCell(0,size/2,0);
    setCell(size/2,size/2,1);

    makeFractal(size/4);

    // вывести карту
    for (int y=0; y<size; y++) for (int x=0; x<size; x++) {
      g.setColor( (getCell(x,y)==0) ? Color.blue : Color.green );
      g.fillRect(x*2,y*2,2,2);
    }
  }

  public void setCell(int x, int y, int c) {
    map[x+size*y]=c;
  }

  public int getCell(int x, int y) {
    return map[x+size*y];
  }

  // обработка фрактала....
  //   step = ширина детализуемого квадрата
  public void makeFractal(int step) {
  for (int y=0; y<size; y+=step) {
    for (int x=0; x<size; x+=step) {
      // Внутренний цикл вычисляет (cx,cy)
      // это точка от которой копируется цвет карты

      // добавить случайное смещение
      int cx=x+ ((Math.random()<0.5) ? 0 : step);
      int cy=y+ ((Math.random()<0.5) ? 0 : step);

      // округлить до ближайшего произведения от step*2
      // где step*2 предыдущий уровень даталирования
      cx=(cx/(step*2))*step*2;
      cy=(cy/(step*2))*step*2;

      // вращать мир как тор
      // для гарантии что getCell() и setCell() в пределах границ
      cx=cx%size;
      cy=cy%size;

      // копировать из (cx,cy) в (x,y)
      setCell(x,y,getCell(cx,cy));
    }
  }

    // рекурсивное вычисление слудующего уровня детализации
    if (step>1) makeFractal(step/2);
  }

  // инициализация апплета
  public void init() {
    super.init();

    // перерисовка на клик
    addMouseListener(new MouseAdapter()
      public void mouseClicked( MouseEvent e ) {
        repaint();
      }
    });
  }

  // главная функция позволяет апплету выполныться как приложению
  public static void main(String[] args) {

    // создать фрейм
    Frame f = new Frame("Fractal Coastlines");
    f.addWindowListener(new WindowAdapter() {
      public void windowClosing(WindowEvent e) {
        System.exit(0);
      }
    });

    // установить фрейм и добавить апплет
    f.setSize(300,300);
    f.setLayout(new BorderLayout());
    CoastApp q=new CoastApp();
    q.init();
    f.add(q);

    // показ...
    f.show();
  }
}

Вывод

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

Практически я осуществил фрактальный алгоритм для того чтобы генерировать Карты Мира для Tyrant, моей собственной roguelike-игры. Вы можете увидеть это в действии на: http://www.mikera.net/tyrant/

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

Хорошего программирования.

Mike.

Все вопросы или комментарии: mike@mikera.net



Автор: Mike Anderson.
Источник: Fractal Landscapes.
Перевел: Дмитрий О. Бужинский [Bu], 24.05.2005.