Inledning

Om vi säger worms så kanske det ringer en klocka. Worms var, och är nog, ett av de allra kändaste datorspel som handlar om att skjuta på varandra i ett landskap som kan deformeras. Andra spel i samma genre är bl. a. Scorched Earth och Gorilla.

En viktigt detalj i denna sortens spel är terrängen. Ett första steg mot att skapa ett worms-liknande spel är att kunna generera banor som ser naturliga ut. I artikeln ska vi koncentrera oss på att skapa en algoritm som kan slumpvis generera naturtrogna landskap. Algoritmen kan vara grunden i ett worms-liknande spel, eller varför inte någon trevlig lemmings-klon?

Teori

Det tillvägagångssätt vi har valt bygger på något som kallas fraktaler. Nu behöver inte det nödvändigtvis betyda krångliga beräkningar utan just detta är faktiskt rätt enkelt. Vi ska skapa en horisont som ser naturlig ut. En horisont är en 1-dimensionell linje.

Linjen skapar vi genom att lägga till punkter i en lista och dra streck mellan punkterna. Punkterna kommer att ha värden mellan +-1.0 där 0 kommer att vara den vertikalt centrerade nivån. Tal över 0 kan vi se som bergstoppar och tal under 0 som dalar.

Nu ska vi ta en titt på hur det kan se ut. I bilden nedan har vi börjat med att lägga in start- och slut-punkt med värdet 0 (gröna). Mellan punkterna har vi sedan lagt in en enda punkt med ett slumpvis valt värde (+-1.0 röd markering).

Nästa steg blir att vi går igenom alla punkter igen och stoppar in nya punkter mellan två punkter på linjen. De nya punkterna får värdet som ligger på linjen (medelvärdet av föregående och kommande punkt) plus ett slumpvärde på +-0.5, Märk att vi låter slumptalet minska i amplitud. De nya punkterna är också markerade med rött i bilden nedan.

Vi upprepar återigen samma process och lägger till punkter med +-0.25 i avvikelse.

Märk väl att vi började med 3 punkter, sedan 5 och till sist 9. Upprepar vi några gånger till får vi 17, 33, 65, 129, 257 osv. Till slut får vi också ett rätt hyffsat resultat som bilden nedan illustrerar.

Algoritmen

Först av allt behöver vi en lista med double för att lagra våra punkter samt ett Bitmap-objekt och ett Random-objekt.

        //Lagring för vår horisentallinje
        List<double> HeightMap = new List<double>();
        //Randomerare för slumptal
        private Random rnd = new Random();
        //Bilden som kommer attt genereras i form av en bitmap
        Bitmap b = new Bitmap(640, 480);

Hela algoritmen för att generera linjen blir:

            //Nollställer listan med punkter
            HeightMap.Clear();

            //Lägger till start- och stop-punkt
            HeightMap.Add(0);
            HeightMap.Add(0);
            
            //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);

            //Generera linjen
            //
            //Uprepa enligt angivet antal iterationer
            for (int j = 0; j < numericUpDown1.Value; j++)
            {
                //Räkna ut hur många nya punkter som ska skapas
                int count = HeightMap.Count;
                for (int i = 0; i < count - 1; i++)
                {
                    //Medelvärdet mellan två punkter
                    double tmp = (HeightMap[i*2] + HeightMap[i*2 + 1]) / 2.0;
                    //Beräkna en slumpvis förskjutning +-Max
                    double offset = (rnd.NextDouble() * 2.0 - 1.0) * Max;

                    //Skapa ny punkt med medelvärde + slumvis förskjutning
                    HeightMap.Insert(i * 2 + 1, tmp+offset);
                }
                //Beräkna Max för nästa iteration, avtagande med en faktor 2^(x)
                Max = Max * Math.Pow(2, -Roughness);
            }

På rad 5 och 6 läggs startpunkterna in. Variabeln Max anger slumpgänserna som börjar på +-1.0. I algoritmen har vi också infört en ojämnhetsfaktor, Roughness som anger med vilken faktor värdet på Max ska avta efter varje iteration. På rad 31 ser vi beräkningen för nya värden på Max. Om Roughness har värdet 1.0 så kommer Max = 1.0 * 2^-1 bli Max = 1.0 * 0.5 vilket är 0.5. Efter varje iteration kommer värdet på Max, dvs slumpens inverkan, att halveras. Se tabellen nedan för jämförelser mella olika värden på Roughness.

Loop'en på rad 16 ser till att ett visst antal iterationer genomförs. Som tidigare förklarats med bilderna så är det i denna loop som nya punkter ska beräknas och läggas till listan med punkter, listan kallad HeightMap. Översatt skulle vi nog kunna tala om en höjdkarta men begreppet är mer känt som det engelska Heightmap och innefattar tekniker tillämpbara både inom 2D-spel men framförallt 3D-spel. Vi håller på att skapa en 1-dimensionell heightmap.

I innerloop'en räknar vi ut hur många punkter som ska läggas in i listan. Med lite finurlig indexering så räknas den mellanliggande punkten ut på rad 23. Detta värde kallat tmp är värdet mellan två punkter längs en tänkt linje. För att skapa lite skillnader behöver vi ochså beräkna en slumvis skillnad, i exemplet kallad offset. Vi slumpar ett decimalt värde mellan -1.0 och +1.0 som vi multiplicerar med varibeln Max. Skalningen med Max gör att den slumpvisa inverkan succesivt avtar med varje iteration som tidigare beskrivits.

Till sist stoppas det nya decimala värdet in som en punkt i vår tänkta linje som representeras av HeightMap.

Uppritning

Inte nog med att vi måste generera datan, vi måste ju även översätta datan till en bild. Vi börjar med koden:

            //Färglägg bilden svart (nollställ)
            Graphics g = Graphics.FromImage(b);
            g.Clear(Color.Black);

            //Rendera bilden (640 pixlar bred)
            //
            for (int x = 0; x  <= 639; x++ )
            {
                //Beräkna vilken punkt på linjen som ligger närmast
                double index = (x / 640.0) * (HeightMap.Count-1);
                int start = (int)Math.Floor(index);

                //Interpolera mellan beräknad punkt och nästa punkt
                double r2 = index - Math.Floor(index);
                double r1 = 1.0 - r2;
                double height = HeightMap[start] * r1 + HeightMap[start + 1] * r2;

                //Ge linjen en offset på 300 pixlar och en amplitud på 150 pixlar
                Point p1 = new Point(x, (int)(  300 + 150.0 * height));
                Point p2 = new Point(x, 0);
                //Rita vertikalt vitt streck från horisonten och uppåt
                g.DrawLine(Pens.White, p1, p2); 
            }
            //Uppdatera bilden
            pictureBox1.Image = b;

Vi loop'ar igenom bredden på bilden för att bestämma vad vi ska färga vitt och vad som ska förbli svart.

På rad 10 och 11 beräknas det index i listan av punkter som vi ligger närmast med tanke på x-position i bilden. Beräkningen begränsas nedåt med Math.Floor() så att vi får ett heltal.

Nästa steg blir att interpolera mellan punkten som anges av index och nästa punkt, dvs index+1. På rad 14 och 15 beräknas hur stor del av första punktens värde och hur stor del av andra punktens värde som ska bestämma den nya punktens höjs, height. Gör vi inte denna interpolering, eller utjämning så kommer resultatet att se konstigt ut. Jämför bilden nedan med den tredje bilden i denna artikel.

När höjden är beräknad så ska vi skala översätta den till pixlar i vår bild. Vi att ha värden mellan -1.0 och +1.0 på höjden. I exemplet ovan så har vi bestämt att höjden ska variera med 150 pixlar kringen en tänkt horisontell linje vid pixel 300 i höjdled. På rad 19 beräknas en Point med dessa väden. Vill vi justera offset'en eller amplituden så kan göra det. I programmet är dessa inställningar inte möjliga. En vit linje ritas sedan från punkt p1 till p2.

Avslutning

Algoritmen som presenteras här är bland de enklare inom spelprogrammering. Den är användbar men ändå begriplig. Koden till exemplet finns i sin helhet nedan. Tanken är att du ska kunna lyfta ut algoritmen ur exemplet nedan och direkt integrera den i ditt spel. Som tidigare nämnts så finns det fler parametrar att leka med för att finjustera algoritmen, främst kanske pixeloffset'en på 300 och amplituden på 150 pixlar men också startvärdet på variabeln Max.