Diamond-Square - generowanie terenu

W jednym z projektów oczekujących na realizację użyteczne dla mnie będzie generowanie terenu, więc przydało się w związku z tym nieco poszperać w necie. Po krótkich poszukiwaniach padło na algorytm Diamond-Square, za pomocą którego możliwe jest stworzenie heightmap dających całkiem dobre rezultaty.

Na początek trochę teorii. Przebieg generowania heightmap'y wygląda następująco:

rys. 1

Na początek w tworzonym kwadracie należy przypisać wartości dla punktów znajdujących się w 4 rogach kwadratu (rys . 1 - zaznaczone na zielono). Jakie to będą wartości, w zasadzie nie ma znaczenia. Mogą to być zera, liczby wcześniej zdefiniowane, lub generowane losowo.

rys. 2

W etapie "diamentu" w każdym kwadracie złożonym z 4 punktów (w pierwszej iteracji będzie to tylko jeden kwadrat) należy wyznaczyć środkowy punkt (rys.2 - zaznaczony na żółto) i następnie obliczyć jego wartość wg wzoru:

E = (A + B + C + D) / 4 + a * b

A, B, C, D – wartości punktów kwadratu, dla którego wyznaczany jest punkt E
a – losowa wartość z zakresu <-a, a> wprowadzająca losowe zróżnicowanie terenu. Wartość tę w każdej kolejnej iteracji należy zmniejszać, aby wprowadzana losowość była coraz mniejsza przy operowaniu na coraz mniejszym obszarze generowanej mapy
b – stały parametr określający "szorstkość" generowanej mapy. Im mniejsza wartość tego parametru, tym mniejsze zróżnicowanie generowanej mapy

rys. 3

W etapie "kwadratu" w uzyskanych diamentach należy obliczyć wartość punktu centralnego w podobny sposób, jak w etapie diamentu. Pominąć należy jedynie dodanie losowej wartości, więc będzie to suma 4 punktów otaczających podzielona przez 4 w przypadku punktów wewnątrz obszaru, lub suma 3 punktów otaczających podzielona przez 3 w przypadku punktów na krawędzi liczonego obszaru. Na rys. 3 przedstawiony jest przykład drugiej sytuacji (tylko taka występuje w pierwszej iteracji algorytmu). Aby obliczyć wartość dla punktu F (żółty), należy wyliczyć średnią wartość dla punktów A, B i E (zielone).

Rezultat po pierwszej iteracji to siatka punktów o rozmiarze 3x3:

rys. 4

Następnie należy powtarzać etap liczenia "diamentów" i "kwadratów" aż do uzyskania oczekiwanej gęstości tworzonej mapy. Przebieg drugiej iteracji przedstawia rys.  5

rys. 5

Algorytm w kolejnych iteracjach generować będzie siatki o długości boku 2ⁿ + 1, czyli: 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025 itd.
W związku z tym, aby uzyskać highmap'e o konkretnym rozmiarze, należy wykonać ilość iteracji, która da mapę o rozmiarze przekraczającym oczekiwany i następnie przyciąć do szukanego rozmiaru.

Przygotowałem klasę, za pomocą której możliwe jest generowanie map zgodnie z przedstawionym algorytmem. Kod udostępniam na licencji BSD (link na końcu artykułu).

Przykładowy kod prezentujący sposób użycia klasy (generuje mapę 512x512 i zapisuje do pliku output.png):

DiamondSquare generator = new DiamondSquare();
float[][] mapa = null;
BufferedImage image = null;
File file = null;

generator.setSize(512);
mapa = generator.generate();
image = new BufferedImage(mapa.length, mapa.length, BufferedImage.TYPE_INT_RGB);
for (int i = 0; i < mapa.length; ++i)
    for (int j = 0; j < mapa.length; ++j)
        {
        int rgb = ((int)mapa[i][j] << 16) + ((int)mapa[i][j] << 8) + (int)mapa[i][j];
        image.setRGB(i, j, rgb);
        }

file = new File("output.png");
ImageIO.write(image, "png", file);

Poniżej znajduje się applet, w którym można obejrzeć , jak wyglądają heightmap’y stworzone przy pomocy tego algorytmu. Parametr określający wielkość może przyjmować maksymalnie 512, jednak jest to limit dodany tylko w applecie w celu uproszczenia wyświetlania. Klasa pozwala generować mapy o dowolnym rozmiarze.

A do czego heightmap'a może się przydać? Można je choćby zaimportować w wielu grach, w których następnie na tak wygenerowanej mapie będzie toczyć się rozgrywka, np:

Linki:

Kod źródłowy klasy

Informacje źródłowe: wikipedia, gameprogrammer.com, lighthouse3d.com