Share
När du fyller i ett område slumpmässigt med föremål, som rum i en slumpmässig dungeon, riskerar du att göra saker för slumpmässigt, vilket resulterar i klumpning eller bara en oanvändbar röra. I denna handledning kommer jag att visa dig hur du använder Binär rymdpartitionering för att lösa det här problemet.
Jag kommer att leda dig genom några allmänna steg för att använda BSP för att göra en enkel 2D-karta, som kan användas för en fängelsehållayout för ett spel. Jag ska visa dig hur man gör en grundläggande Blad objekt som vi ska använda för att dela upp ett område upp i små segment då, hur man genererar ett slumpmässigt rum i varje Blad; och slutligen hur man ansluter alla rum tillsammans med hallar.
Jag har skapat ett demo-program som visar lite av kraften i BSP. Demon är skrivet med Flixel, ett gratis, open-source AS3-bibliotek för att skapa spel.
När du klickar på Generera knappen, den går igenom samma kod som ovan för att generera några leafs, och sedan drar dem till en BitmapData objekt som det då visar (uppskalat för att fylla skärmen).
När du slår på Spela knappen, den passerar den genererade kartan Bitmap över till FlxTilemap objekt som sedan genererar en spelbar tillemap och visar den på skärmen för att du ska gå runt i:
Använd piltangenterna för att flytta.
Binär rymdpartitionering är en metod för att dela ett område i mindre bitar.
I grund och botten tar du ett område, kallat a Blad, och dela upp det - antingen vertikalt eller horisontellt - i två mindre blad, och upprepa därefter processen på de mindre områdena om och om igen tills varje område är minst lika liten som ett bestämt maximalt värde.
När du är klar har du en hierarki av partitionerad leafs, som du kan göra alla sorters saker med. I 3D-grafik kan du använda BSP för att sortera vilka objekt som är synliga för spelaren, eller för att hjälpa till med kollisionsdetektering i mindre bitar i bitar.
Om du vill generera en slumpmässig karta finns det alla möjliga sätt att hantera det. Du kan skriva enkel logik för att skapa slumpmässigt stora rektanglar på slumpmässiga platser, men det här kan lämna dig med kartor som är fulla av överlappande, klumpiga eller underligt placerade rum. Det gör det också lite svårare att ansluta rummen till varandra och se till att det inte finns några föräldralösa rum.
Med BSP kan du garantera mer jämnt fördelade rum, samtidigt som du ser till att du kan ansluta alla rum tillsammans.
Det första vi behöver är att skapa vår Blad klass. I grund och botten vår Blad kommer att bli en rektangel, med lite extra funktionalitet. Varje Blad kommer antingen att innehålla ett par barn leafs, eller ett par rum, samt en hall eller två.
Här är vad vår Blad ser ut som:
offentlig klass Leaf privat const MIN_LEAF_SIZE: uint = 6; allmän var y: int, x: int, bredd: int, höjd: int; // positionen och storleken på denna Leaf public var vänsterChild: Leaf; // Leafens vänstra barn Leaf public var rightChild: Leaf; // Leafens rätt barn Leaf public var rum: Rektangel; // rummet som är inne i denna Leaf public var hallar: Vector .; // hallar för att ansluta detta blad till andra bladets offentliga funktion Blad (X: int, Y: int, Bredd: int, Höjd: int) // initiera vårt blad x = X; y = Y; bredd = bredd; höjd = höjd; Public Function Split (): Boolean // Börja dela bladet i två barn om (leftChild! = null || rightChild! = null) returnera false; // vi är redan delade! Avbryta! // bestäm delningsriktningen // om bredden är> 25% större än höjden delas vi vertikalt // om höjden är> 25% större än bredden delas vi horisontellt // annars delas vi slumpvis var splitH: Boolean = FlxG.random ()> 0,5; om (bredd> höjd & bredd / höjd> = 1,25) splitH = false; annars om (höjd> bredd && höjd / bredd = = 1,25) splitH = true; var max: int = (splitH? höjd: bredd) - MIN_LEAF_SIZE; // bestäm maximal höjd eller bredd om (max <= MIN_LEAF_SIZE) return false; // the area is too small to split any more… var split:int = Registry.randomNumber(MIN_LEAF_SIZE, max); // determine where we're going to split // create our left and right children based on the direction of the split if (splitH) leftChild = new Leaf(x, y, width, split); rightChild = new Leaf(x, y + split, width, height - split); else leftChild = new Leaf(x, y, split, height); rightChild = new Leaf(x + split, y, width - split, height); return true; // split successful!
Nu måste du faktiskt skapa din leafs:
const MAX_LEAF_SIZE: uint = 20; var _leafs: Vector= ny vektor ; var l: Leaf; // Helper Leaf // först, skapa ett blad som "rot" för alla blad. var root: Leaf = nytt blad (0, 0, _sprMap.width, _sprMap.height); _leafs.push (root); var did_split: Boolean = true; // Vi slår igenom varje blad i vår vektor om och om igen, tills inga fler blad kan delas upp. medan (did_split) did_split = false; för varje (l i _leafs) om (l.leftChild == null && l.rightChild == null) // om det här bladet inte redan är uppdelat ... // om det här bladet är för stort eller 75% chans ... om (l.width> MAX_LEAF_SIZE || l.height> MAX_LEAF_SIZE || FlxG.random ()> 0.25) om (l.split ()) // dela bladet! // om vi splittrade, tryck barnet blad till vektorn så att vi kan slinga in i dem nästa _leafs.push (l.leftChild); _leafs.push (l.rightChild); did_split = true;
Efter att denna loop har slutförts kommer du att vara kvar med a Vektor (en typad array) full av alla dina leafs.
Här är ett exempel med linjer som skiljer vardera Blad:
Nu när din leafs definieras, vi behöver göra rummen. Vi vill ha en slags "trickle-down" -effekt där vi går från vår största, "root" Blad hela vägen till vårt minsta leafs utan barn, och gör sedan ett rum i var och en av dem.
Så lägg till den här funktionen till din Blad klass:
public function createRooms (): void // den här funktionen genererar alla rum och korridorer för detta blad och alla dess barn. om (leftChild! = null || rightChild! = null) // det här bladet har delats, så gå in i barnen bladar om (leftChild! = null) leftChild.createRooms (); om (rightChild! = null) rightChild.createRooms (); annat // detta blad är redo att göra ett rum var rum storlek: punkt; var roomPos: Point; // rummet kan vara mellan 3 x 3 kakel till storleken på bladet - 2. roomSize = new Point (Registry.randomNumber (3, bredd - 2), Registry.randomNumber (3, height - 2)); // placera rummet i bladet, men lägg det inte rätt // mot bladets sida (det skulle sammanfoga rum tillsammans) roomPos = new Point (Registry.randomNumber (1, width - roomSize.x - 1) , Registry.randomNumber (1, height - roomSize.y - 1)); rum = ny rektangel (x + roomPos.x, y + roomPos.y, roomSize.x, roomSize.y);
Sedan, efter att du har skapat din Vektor av leafs, ring vår nya funktion från din rot Blad:
_leafs = ny vektor; var l: Leaf; // Helper Leaf // först, skapa ett blad som "rot" för alla blad. var root: Leaf = nytt blad (0, 0, _sprMap.width, _sprMap.height); _leafs.push (root); var did_split: Boolean = true; // Vi slår igenom varje blad i vår vektor om och om igen, tills inga fler blad kan delas upp. medan (did_split) did_split = false; för varje (l i _leafs) om (l.leftChild == null && l.rightChild == null) // om det här bladet inte redan är uppdelat ... // om det här bladet är för stort eller 75% chans ... om (l.width> MAX_LEAF_SIZE || l.height> MAX_LEAF_SIZE || FlxG.random ()> 0.25) om (l.split ()) // dela bladet! // om vi splittrade, tryck barnet Leafs till vektorn så att vi kan gå in i dem nästa _leafs.push (l.leftChild); _leafs.push (l.rightChild); did_split = true; // nästa, iterera genom varje blad och skapa ett rum i var och en. root.createRooms ();
Här är ett exempel på några genererade leafs med rum inuti dem:
Som du kan se, var och en Blad innehåller ett enkelrum med en slumpmässig storlek och position. Du kan spela med värdena för minimum och maximalt Blad storlek och ändra hur du bestämmer storleken och positionen för varje rum för att få olika effekter.
Om vi tar bort vårt Blad separatorlinjer, kan du se att rummen fyller hela kartan snyggt - det finns inte mycket slösat utrymme - och har en lite mer organisk känsla för dem.
Accentsconagua
leafs med ett rum inuti var och en, med separatorliner borttagna. Nu är allt vi behöver göra för att ansluta varje rum. Tack och lov, eftersom vi har de inbyggda relationerna mellan leafs, allt vi behöver göra är att se till att varje Blad som har barn leafs har en korridor som förbinder sina barn.
Vi tar en Blad, titta på var och en av sina barn leafs, gå hela vägen genom varje barn tills vi kommer till en Blad med ett rum, och anslut sedan rummen tillsammans. Vi kan göra detta samtidigt som vi genererar våra rum.
Först behöver vi en ny funktion för att iterera från någon Blad in i ett av rummen som är inuti ett av barnet leafs:
offentlig funktion getRoom (): Rektangel // iterera hela vägen genom dessa löv för att hitta ett rum, om man existerar. om (rum! = återvänt) returrum; annars var lRoom: rektangel; var rRoom: rektangel; om (leftChild! = null) lRoom = leftChild.getRoom (); om (rightChild! = null) rRoom = rightChild.getRoom (); om (lRoom == null && rRoom == null) returnera null; annars om (rRoom == null) returnera lRoom; annars om (lRoom == null) returnerar rRoom; annars om (FlxG.random ()> .5) returnera lRoom; returnera annars rRoom;
Därefter behöver vi en funktion som tar ett par rum, väljer en slumpmässig punkt i båda rummen och skapar sedan en eller två två-kakel tjocka rektanglar för att koppla samman punkterna.
public function createHall (l: rektangel, r: rektangel): void // nu kopplar vi dessa två rum tillsammans med hallar. // det ser ganska komplicerat ut, men det är bara att försöka lista ut vilken punkt är var och då antingen dra en rak linje eller ett par linjer för att göra en rätvinkel för att ansluta dem. // Du kan göra lite extra logik för att göra dina hallar mer böjda, eller gör några mer avancerade saker om du vill. hallar = ny vektor; var punkt1: Punkt = ny punkt (Registry.randomNumber (l.left + 1, lright - 2), Registry.randomNumber (l.top + 1, l.bottom - 2)); var punkt2: Punkt = ny punkt (Registry.randomNumber (r.left + 1, r.right - 2), Registry.randomNumber (r.top + 1, r.bottom - 2)); var w: Nummer = punkt2.x - punkt1.x; var h: Number = point2.y - point1.y; om (w < 0) if (h < 0) if (FlxG.random() < 0.5) halls.push(new Rectangle(point2.x, point1.y, Math.abs(w), 1)); halls.push(new Rectangle(point2.x, point2.y, 1, Math.abs(h))); else halls.push(new Rectangle(point2.x, point2.y, Math.abs(w), 1)); halls.push(new Rectangle(point1.x, point2.y, 1, Math.abs(h))); else if (h > 0) om (FlxG.random () < 0.5) halls.push(new Rectangle(point2.x, point1.y, Math.abs(w), 1)); halls.push(new Rectangle(point2.x, point1.y, 1, Math.abs(h))); else halls.push(new Rectangle(point2.x, point2.y, Math.abs(w), 1)); halls.push(new Rectangle(point1.x, point1.y, 1, Math.abs(h))); else // if (h == 0) halls.push(new Rectangle(point2.x, point2.y, Math.abs(w), 1)); else if (w > 0) om (h < 0) if (FlxG.random() < 0.5) halls.push(new Rectangle(point1.x, point2.y, Math.abs(w), 1)); halls.push(new Rectangle(point1.x, point2.y, 1, Math.abs(h))); else halls.push(new Rectangle(point1.x, point1.y, Math.abs(w), 1)); halls.push(new Rectangle(point2.x, point2.y, 1, Math.abs(h))); else if (h > 0) om (FlxG.random () < 0.5) halls.push(new Rectangle(point1.x, point1.y, Math.abs(w), 1)); halls.push(new Rectangle(point2.x, point1.y, 1, Math.abs(h))); else halls.push(new Rectangle(point1.x, point2.y, Math.abs(w), 1)); halls.push(new Rectangle(point1.x, point1.y, 1, Math.abs(h))); else // if (h == 0) halls.push(new Rectangle(point1.x, point1.y, Math.abs(w), 1)); else // if (w == 0) if (h < 0) halls.push(new Rectangle(point2.x, point2.y, 1, Math.abs(h))); else if (h > 0) halls.push (ny rektangel (punkt1.x, punkt1.y, 1, Math.abs (h)));
Ändra ändå din createRooms () funktion att ringa createHall () funktion på någon Blad som har ett par barn:
public function createRooms (): void // den här funktionen genererar alla rum och korridorer för detta blad och alla dess barn. om (leftChild! = null || rightChild! = null) // det här bladet har delats, så gå in i barnen bladar om (leftChild! = null) leftChild.createRooms (); om (rightChild! = null) rightChild.createRooms (); // Om det finns både vänster och höger barn i detta blad, skapa en korridor mellan dem om (leftChild! = null && rightChild! = null) createHall (leftChild.getRoom (), rightChild.getRoom ()); annat // detta blad är redo att göra ett rum var rum storlek: punkt; var roomPos: Point; // rummet kan vara mellan 3 x 3 kakel till storleken på bladet - 2. roomSize = new Point (Registry.randomNumber (3, bredd - 2), Registry.randomNumber (3, height - 2)); // placera rummet i bladet, men lägg det inte direkt mot bladets sida (det skulle sammanfoga rum tillsammans) roomPos = new Point (Registry.randomNumber (1, width - roomSize.x - 1), Registry .randomNumber (1, height - roomSize.y - 1)); rum = ny rektangel (x + roomPos.x, y + roomPos.y, roomSize.x, roomSize.y);
Dina rum och hallar borde nu se ut så här:
leafs fylld med slumpmässiga rum anslutna via korridorer. Som du kan se, för att vi ser till att ansluta alla Blad, Vi är inte kvar med några föräldralösa rum. Självklart kan halliklogiken vara lite mer förfinad för att försöka undvika att springa för nära andra hallar, men det fungerar bra nog.
Det är i princip det! Vi har täckt hur man skapar en (relativt) enkel Blad objekt, som du kan använda för att generera ett träd av uppdelade blad, generera ett slumpmässigt rum inuti varje Blad, och anslut rummen via hallar.
För närvarande är alla objekt vi skapat huvudsakligen rektanglar, men beroende på hur du tänker använda den resulterande fängelsehålan, kan du hantera dem på alla sätt.
Nu kan du använda BSP för att göra någon form av slumpmässiga kartor du vill, eller använda den för att jämnt fördela power ups eller fiender över ett område ... eller vad du vill!
