Generera terräng (3D)

Inledning

Vi ska nu ta steget från 2D till 3D. I den tidigare artikeln, Generera terräng (2D) , konstruerade vi en algoritm som genererade en linje för att kunna användas som terräng i ett 2D-spel. Nu ska vi generara en heightmap i 2D som kan användas i 3D-spel.

Algoritmen vi ska använda är faktiskt ungefär samma som vi använde tidigare. Man brukar säga att kärt barn har många namn. Algoritmen kallas bl a för Diamond-square, cloud fractal eller plasma fractal. Resultatet från algoritmen blir en höjdkarta där varje punkt motsvarar en höjd. Översatt till en svartvit bild kan det se ut som:

bild

Använder vi höjdkartan för att generera ett landskap i 3D så kan det se ut som bilden nedan. Bilden av höjdkartan är infälld för att visa betraktningsvinkeln.

bild

Teori

Vi vill börja med att påpeka att det finns en mängd variationer på hur algoritmen kan implementeras. För att generera en 3x3 pixlars bild börjar vi med att slumpa värdena i hörnen. I bilden nedan ha hörnen fått värde 0, 2, 4 och 8.

bild

Mittpunkten beräknas utifrån hörnen till (0 + 2 + 4 + 8) / 4 = 14 / 4 = 3,5.

Övriga punkter beräkns som ett medelvärde mellan närmaste grannar, t ex punkten ovanför beräknas som (0 + 2) / 2 = 1, nedanför som (4 + 8) / 2 = 6, vänster som (0 + 4) / 2 = 2 och höger som (2 + 8) / 2 = 5.

Detta motsvarar en iteration. Fler iterationer skapar en större bild då varje iteration delar varje kvadrat i fyra mindre kvadrater. Storleken växer i kvardat med 3x3, 5x5, 9x9, 17x17, 33x33, 65x65, 129x129 osv. Som exempel kan vi ge oss på att skapa en 9x9 pixlars bild. Detta medför 3 iterationer.

bild

Första steget är att slumpa värden i hörnen, de gröna punkterna i bilden ovan. Sedan utförs första iterationen markerade som gula punkter. Andra iterationen utförs på de fyra mindre kvadraterna markerade i blått. Sista iterationen täcker in alla kvarvarande pixlar och är i bilden markerade som röda.

Iterationerna kan illustreras steg för steg som i bilden nedan. De gråa punkterna markerar pixlar som används i beräkningen för de nya för varje steg.

bild

Till varje beräkning läggs även ett slumptal. Utan att tillföra slumptal så blir landskapen inte så intressanta.

Algoritmen

Exempel: Rendera terräng

//Skapa om data och bild beroende på genererad storlek;
int size = (int)Math.Pow(2, (double)numericUpDown1.Value);
b = new Bitmap(size + 1, size + 1);
HeightMap = new double[size + 1, size + 1];
pictureBox1.Size = new Size(size + 1, size + 1);

//Börjar algoritmen med slump +- 1.0
double Max = 1.0;
//Bestämmer ojämnheten i terrängen
double Roughness = ((double)numericUpDown2.Value / 100.0);

//Slumpa startvärden i alla hörn
HeightMap[0, 0] = (rnd.NextDouble() * 2.0 - 1.0) * Max;
HeightMap[size, 0] = (rnd.NextDouble() * 2.0 - 1.0) * Max;
HeightMap[0, size] = (rnd.NextDouble() * 2.0 - 1.0) * Max;
HeightMap[size, size] = (rnd.NextDouble() * 2.0 - 1.0) * Max;

//Utför ett antal iterationer beroende på bildens storlek
for (int start = size / 2; start >= 1; start = start / 2)
{
    for (int y = start; y < size; y += 2 * start)
    {
        for (int x = start; x < size; x += 2 * start)
        {
            //Mittpunkt i rektangeln
            double tmp = (HeightMap[x - start, y - start] + HeightMap[x + start, y + start] +
                HeightMap[x + start, y - start] + HeightMap[x - start, y + start]) / 4.0;
            //Lägg till en slumpvis förskjutning +-Max
            tmp += (rnd.NextDouble() * 2.0 - 1.0) * Max;
            //Uppdatera punkt i kartan
            HeightMap[x, y] = tmp;

            //Beräkna punkt ovanför
            HeightMap[x, y - start] = (HeightMap[x - start, y - start] + HeightMap[x+start, y-start])/2.0;
            HeightMap[x, y - start] += (rnd.NextDouble() * 2.0 - 1.0) * Max;
            //Beräkna punkt till vänster
            HeightMap[x - start, y] = (HeightMap[x - start, y - start] + HeightMap[x-start, y+start])/2.0;
            HeightMap[x - start, y] += (rnd.NextDouble() * 2.0 - 1.0) * Max;
            //Beräkna punkt till höger
            HeightMap[x + start, y] = (HeightMap[x + start, y - start] + HeightMap[x+start, y+start])/2.0;
            HeightMap[x + start, y] += (rnd.NextDouble() * 2.0 - 1.0) * Max;
            //Beräkna punkt nedanför
            HeightMap[x, y + start] = (HeightMap[x - start, y + start] + HeightMap[x+start, y+start])/2.0;
            HeightMap[x, y + start] += (rnd.NextDouble() * 2.0 - 1.0) * Max;
        }
    }
    //Beräkna Max för nästa iteration, avtagande med en faktor 2^(x)
    Max = Max * Math.Pow(2, -Roughness);
}

//Rendera gråskalig bild
for (int y = 0; y < HeightMap.GetUpperBound(0); y++)
{
    for (int x = 0; x < HeightMap.GetUpperBound(1); x++)
    {
        //Värden i HeightMap ligger i runda slängar +- 1.0
        //Skala med 127 ger +-127 och lägg till offset på 128 ger 0 till 255
        int greyscale = (int)((HeightMap[x, y] * 127.0) + 128.0);

        //Extra kolla så att värdena ligger inom giltiga gränser
        if (greyscale < 0)
            greyscale = 0;
        if (greyscale > 255)
            greyscale = 255;
        //Uppdatera pixel med gråskaligt värde
        b.SetPixel(x, y, Color.FromArgb(greyscale, greyscale, greyscale));
    }
}
//Uppdatera bilden
pictureBox1.Image = b;

Algoritmen genererar slumpvärden mellan ca +-1.0. Först beräknas hur stor bild vi behöver utifrån en NumericUpDown. Beräkningen på size ligger till grund för hur många iterationer som behöver genomföras på rad 19. Beräkningen av Roughness och Max är densamma som i artikeln Generera terräng (2D) . Faktum är att det mesta är detsamma förutom att vi har lagt till en dimenson. En stor skillnad är också att vi direkt beräknar och skapar en datastruktur beroende på antal iterationer. Tidigare använde vi oss av en dynamisk List.

Kodexemplet ovan är direkt taget från det färdiga projektet nedan som du kan ladda hem och testa.

Avslutning

Algoritmen kan vara användbar då du i spelet kan generera höjdkartor utan avrundningsfel. I de fall då du laddar in bilder och använder som höjdkartor så kan du upptäcka avrundningsfel som görs då höjdkartan översätts till bild. Dessa avrundningsfel kan vara synliga och irriterande. Sen bör det tilläggas att det finns personer och företag som inte gör annat än att generera naturtrogna landskap så det finns en rad metoder som är betydligt mer sofistikerade än denna.

Andra användningsområden kan vara att generera molntexturer eller liknande.

Ladda gärna ned det kompletta exemplet nedan och testa.

bild

Lämna ett svar

Din e-postadress kommer inte publiceras. Obligatoriska fält är märkta *

Scroll to top