Anders Hesselboms teknikblogg

Labyrint (recursive backtracking)

2017-01-05

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();
                }
            }
        }
    }
}