Фрактальные ландшафты
Данная статья была написана для 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.
