Fortsätt till huvudinnehåll
Startsidan      |      Min nya blogg!      |     YouTube     |      Twitter      |      Podcasts      |      Hall of fame     |      Evolution

Labyrint (recursive backtracking)

Jag har börjat arbeta med ett datorspel i kategorin roguelike. Varje spel ska vara unikt, så kartan genereras när en användare spelar spelet. Vid uppstart skapar jag en labyrint som sen används som kontur för rummen som genereras efter behov. De rum som spelaren inte besöker behöver man trots allt inte hålla i RAM, men jag vill ha konturen färdig för att kunna ha lite kontroll över kartans kvalité.

Totalt okunnig om labyrintalgoritmer läste jag igenom Wikipedias artikel om recursive backtracking som i korthet går ut på följande:

1. Utgå från den cell som ska vara startpunkten, C.

2. Om C inte är vald sedan tidigare, plocka bort en slumpvis utvald vägg på C. Följ den nyskapade öppningen och låt den vara C.

3. Om nya C har varit C tidigare, stega bakåt till första cell som fortfarande har fyra väggar, gör den till C, upprepa steg 2.

4. Om C nu är samma som var C vid punkt 1 så är labyrinten klar.

Så i princip startar mitt (blivande) datorspel med en hel hög av celler (precis hur många jag vill) som håller information om in- och utgångar (konturen), men det är först när cellen används som fyller jag på med s.k. tiles, alltså de byggstenar som bestämmer kartans detaljer. Låt oss titta på själva labyrinten, och lämna resten därhän.

För detta exempel valde jag språket C#. Trots att språket är lite pratigt, är det ganska flexibelt och användbart.

Först av allt behövs en entitet - en cell - som kan ha väggar i fyra riktningar: Norr, öst, söder och väst. Jag anger att jag både vill kunna läsa (get) och skriva (set) dessa egenskaper under programmets gång. Initialt måste cellen ha alla sina fyra möjliga väggar.

 public class Cell
{
    public bool WallNorth { get; set; } = true;
    public bool WallEast { get; set; } = true;
    public bool WallSouth { get; set; } = true;
    public bool WallWest { get; set; } = true;
}

Vidare måste cellen kunna svara på var i labyrinten den befinner sig. Det behövs för att cellens grannar ska kunna hittas. En cell som inte kan svara på det, får inte skapas över huvudet taget.

    public int X { get; }
    public int Y { get; }
    public Cell(int x, int y)
    {
        X = x;
        Y = y;
    }

Eftersom cellen enligt algoritmens regler måste kunna svara på hur många väggar den har, måste vi beskriva hur vi kan veta det.

    public int WallsCount
    {
        get
        {
            var c = WallNorth ? 1 : 0;
            c += WallEast ? 1 : 0;
            c += WallSouth ? 1 : 0;
            c += WallWest ? 1 : 0;
            return c;
        }
    }

Och slutligen måste cellen kunna berätta om sin position i ett lämpligt format.

    public Point Position => new Point(X, Y);

Därefter behövs en representation av själva labyrinten som kan hålla en matris av celler. Denna gång väljer jag att skapa en liten labyrint med 100 celler (10 x 10). Bredden och höjden måste kunna läsas (get) under programmets gång. Koden skapar inte cellerna, endast platshållaren för dem.

public class Labyrinth
{
    public static int Width { get; } = 10;
    public static int Height { get; } = 10;
    public Cell[,] Cell = new Cell[Width, Height];
}

Sen ska vi beskriva algoritmen i labyrintens konstruktor (=funktion med ansvar för initiering). Vi börjar med att berätta att vi vill kunna skapa slumptal, och att platshållaren för våra celler verkligen ska innehålla celler.

         var rnd = new Random();
        for (var y = 0; y < Height; y++)
            for (var x = 0; x < Width; x++)
                Cells[x, y] = new Cell(x, y);

Därefter måste vi definiera konceptet med grannar för konstruktorn. Grannar är angränsande celler.

        Func<int, int, List<Point>> getNeighbours = (x, y) =>
        {
            var ret = new List<Point>();
            if (y > 0 && Cells[x, y - 1].WallsCount >= 4)
                ret.Add(Cells[x, y - 1].Position);
            if (x < Width - 1 && Cells[x + 1, y].WallsCount >= 4)
                ret.Add(Cells[x + 1, y].Position);
            if (y < Height - 1 && Cells[x, y + 1].WallsCount >= 4)
                ret.Add(Cells[x, y + 1].Position);
            if (x > 0 && Cells[x - 1, y].WallsCount >= 4)
                ret.Add(Cells[x - 1, y].Position);
            return ret;
        };

Sen måste vi beskriva hur man slår in en vägg. Det är inte så enkelt som att sätta en cells vägg-egenskap (t.ex. WallNorth) till false, eftersom grannen åt det hållet också måste få sin motsvarande vägg (t.ex. WallSouth) satt till false.

         Action<Cell, Point> knockWall = (cell1, cell2) =>
        {
            if (cell2.Y < cell1.Y)
            {
                cell1.WallNorth = false;
                Cells[cell2.X, cell2.Y].WallSouth = false;
                return;
            }
            if (cell2.X > cell1.X)
            {
                cell1.WallEast = false;
                Cells[cell2.X, cell2.Y].WallWest = false;
                return;
            }
            if (cell2.Y > cell1.Y)
            {
                cell1.WallSouth = false;
                Cells[cell2.X, cell2.Y].WallNorth = false;
                return;
            }
            if (cell2.X < cell1.X)
            {
                cell1.WallWest = false;
                Cells[cell2.X, cell2.Y].WallEast = false;
                return;
            }
        };

Nu har konstruktorn tillgång till resurserna, och den vet vad en granne är och hur man slår in en vägg. Dags att sätta igång! Vi behöver hålla koll på vilka celler vi besökt...

             var queue = new Queue<Cell>();

...och så behöver vi en slumpvis utvald cell att börja i.

             var c = Cells[rnd.Next(Width), rnd.Next(Height)];
            queue.Enqueue(c);

Därefter, slå ut en vägg och följ efter. Om det inte går, backa till start och prova igen.

            while (queue.Count > 0)
            {
                var neighbours = getNeighbours(c.X, c.Y);
                if (neighbours.Count > 0)
                {
                    var neighbour = neighbours[rnd.Next(neighbours.Count)];
                    knockWall(c, neighbour);
                    queue.Enqueue(c);
                    c = Cells[neighbour.X, neighbour.Y];
                }
                else
                {
                    c = queue.Dequeue();
                }
            }

För att representera detta på skärmen, behöver jag bara bekymra mig om två av väggarna, höger och under. Högra grannens vänstervägg och undre grannens övre vägg har samma status (tack vare knockWall).

    private void Form1_Paint(object sender, PaintEventArgs e)
    {
        const int size = 20;
        for (var y = 0; y < Labyrinth.Height; y++)
            for (var x = 0; x < Labyrinth.Width; x++)
            {
                if (Labyrinth.Cells[x, y].WallEast)
                    e.Graphics.DrawLine(Pens.Black, x * size + (size - 1), y * size, x * size + (size - 1), y * size + (size - 1));
                if (Labyrinth.Cells[x, y].WallSouth)
                    e.Graphics.DrawLine(Pens.Black, x * size, y * size + (size - 1), x * size + (size - 1), y * size + (size - 1));
            }
    }

Hela källkoden ser ut så här:

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        private Labyrinth Labyrinth { get; } = new Labyrinth();
        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            const int size = 20;
            for (var y = 0; y < Labyrinth.Height; y++)
                for (var x = 0; x < Labyrinth.Width; x++)
                {
                    if (Labyrinth.Cells[x, y].WallEast)
                        e.Graphics.DrawLine(Pens.Black, x * size + (size - 1), y * size, x * size + (size - 1), y * size + (size - 1));
                    if (Labyrinth.Cells[x, y].WallSouth)
                        e.Graphics.DrawLine(Pens.Black, x * size, y * size + (size - 1), x * size + (size - 1), y * size + (size - 1));
                }
        }
    }
    public class Cell
    {
        public bool WallNorth { get; set; } = true;
        public bool WallEast { get; set; } = true;
        public bool WallSouth { get; set; } = true;
        public bool WallWest { get; set; } = true;
        public int X { get; }
        public int Y { get; }
        public Cell(int x, int y)
        {
            X = x;
            Y = y;
        }
        public int WallsCount
        {
            get
            {
                var c = WallNorth ? 1 : 0;
                c += WallEast ? 1 : 0;
                c += WallSouth ? 1 : 0;
                c += WallWest ? 1 : 0;
                return c;
            }
        }
        public Point Position => new Point(X, Y);
    }
    public class Labyrinth
    {
        public static int Width { get; } = 10;
        public static int Height { get; } = 10;
        public Cell[,] Cells = new Cell[Width, Height];
        public Labyrinth()
        {
            var rnd = new Random();
            for (var y = 0; y < Height; y++)
                for (var x = 0; x < Width; x++)
                    Cells[x, y] = new Cell(x, y);
            Func<int, int, List<Point>> getNeighbours = (x, y) =>
            {
                var ret = new List<Point>();
                if (y > 0 && Cells[x, y - 1].WallsCount >= 4)
                    ret.Add(Cells[x, y - 1].Position);
                if (x < Width - 1 && Cells[x + 1, y].WallsCount >= 4)
                    ret.Add(Cells[x + 1, y].Position);
                if (y < Height - 1 && Cells[x, y + 1].WallsCount >= 4)
                    ret.Add(Cells[x, y + 1].Position);
                if (x > 0 && Cells[x - 1, y].WallsCount >= 4)
                    ret.Add(Cells[x - 1, y].Position);
                return ret;
            };
            Action<Cell, Point> knockWall = (cell1, cell2) =>
            {
                if (cell2.Y < cell1.Y)
                {
                    cell1.WallNorth = false;
                    Cells[cell2.X, cell2.Y].WallSouth = false;
                    return;
                }
                if (cell2.X > cell1.X)
                {
                    cell1.WallEast = false;
                    Cells[cell2.X, cell2.Y].WallWest = false;
                    return;
                }
                if (cell2.Y > cell1.Y)
                {
                    cell1.WallSouth = false;
                    Cells[cell2.X, cell2.Y].WallNorth = false;
                    return;
                }
                if (cell2.X < cell1.X)
                {
                    cell1.WallWest = false;
                    Cells[cell2.X, cell2.Y].WallEast = false;
                    return;
                }
            };
            var queue = new Queue<Cell>();
            var c = Cells[rnd.Next(Width), rnd.Next(Height)];
            queue.Enqueue(c);
            while (queue.Count > 0)
            {
                var neighbours = getNeighbours(c.X, c.Y);
                if (neighbours.Count > 0)
                {
                    var neighbour = neighbours[rnd.Next(neighbours.Count)];
                    knockWall(c, neighbour);
                    queue.Enqueue(c);
                    c = Cells[neighbour.X, neighbour.Y];
                }
                else
                {
                    c = queue.Dequeue();
                }
            }
        }
    }
}

Och detta är resultatet:

Kommentarer

Skicka en kommentar

Populära inlägg i den här bloggen

Bibelns böcker på engelska

Ibland vill man dela roliga bibelord till med sina internationella vänner, men då gäller det att kunna källförteckna så att de förstår. Därför har jag gjort en liten lista över bibelns böcker, beteckning och engelska motsvarighet. Jag har hämtat de svenska benämningarna från Bibel 2000. Gamla Testamentet: Första Moseboken el. Genesis (1 Mos): Genesis Andra Moseboken el. Exodus (2 Mos): Exodus Tredje Moseboken el. Leviticus (3 Mos): Leviticus Fjärde Moseboken el. Numeri (4 Mos): Numbers Femte Moseboken el. Deuteronomium (5 Mos): Deuteronomy Josua (Jos): Joshua Domarboken (Dom): Judges Rut (Rut): Ruth Första Samuelsboken (1 Sam): 1 Samuel Andra Samuelsboken (2 Sam): 2 Samuel Första Kungaboken (1 Kung): 1 Kings Andra Kungaboken (2 Kung): 2 Kings Första Krönikeboken (1 Krön): 1 Chronicles el. 1 Paralipomenon Andra Krönikeboken (2 Krön): 2 Chronicles el. 2 Paralipomenon Esra (Esr): Ezra el. 1 Esdras Nehemja (Neh): Nehemiah el. 2 Esdras Ester (Est): Esther el. 1-2 Maccabe
6 kommentarer
Läs mer

Mattias Irving bör frikännas

Häromdagen ställdes Mattias Irving inför rätta efter att ha visat ohörsamhet inför ordningsmakten. Irving är, på nästan alla tänkbara sätt, min meningsmotståndare. Jag delar definitivt inte hans åsikter om speciellt mycket. Just denna gång handlade ohörsamheten i fråga om att störa en nazistdemonstration med bl.a. psalmsång. Hur meningsmotståndare bör bemötas, är en av de frågor där vi verkligen går isär och denna gång var det nazisterna som var meningsmotståndaren. Både Irving och jag är antinazister, men jag dök inte upp för någon motaktion, det gjorde Irving. Han tog en kula för oss. Civil olydnad är en balansgång, och inte alltid är meningsmotståndaren just nazister. Vem du föraktar, beror på vem du är. Eftersom t.ex. ateister är lika föraktade som nazister i vissa läger - det finns vissa kristna sällskap som odlar myten att Hitlers ateism ledde honom till förintelsen - bör man ha ett system där spelreglerna är konsekventa. Det viktiga är inte vad man protesterar mot, utan
17 kommentarer
Läs mer

Har naturvetenskapen en naturalistisk bias?

Diskussionen om huruvida vetenskapen är agnostisk eller inte fortsätter. I praktiken är vetenskapen både ateistisk och gudsförnekande, bl.a. beroende på kravet att teorier måste kunna falsifieras, vilket i princip är omöjligt när man tar höjd för övernaturliga agenter. Rent tekniskt är vetenskapen agnostisk - ingen kan veta någonting om någonting - särskilt inte om verkligheten kontrolleras av gudar och demoner. Därför måste evidenslägen bedömas och därför bortser vetenskapen i praktiken från Gud. Och alla andra övernaturliga väsen. Non est ponenda pluralitas sine necessitate. Detta faller såklart inte i god jord hos den som faktiskt tror att övernaturliga väsen existerar. De vill gärna att vetenskapen ska ta särskilda hänsyn till just deras specifika föreställningar, och när så inte sker, har vi att göra med en konspiration. Här är ytterligare några invändningar som inkommit. Hittills. 1. Vetenskapen har förutfattade meningar om att gud inte finns 2. Ingen vet hur gravitation fungerar
30 kommentarer
Läs mer