Share
Bij het willekeurig invullen van een gebied met objecten, zoals kamers in een willekeurige kerker, loop je het risico dingen te maken te willekeurig, resulterend in klontering of gewoon een onbruikbare puinhoop. In deze zelfstudie laat ik je zien hoe te gebruiken Binary Space Partitioning om dit probleem op te lossen.
Ik zal u door een aantal algemene stappen leiden om BSP te gebruiken om een eenvoudige 2D-kaart te maken die kan worden gebruikt voor een kerkerindeling voor een spel. Ik zal je laten zien hoe je een basis maakt Blad object, dat we zullen gebruiken om een gebied op te splitsen in kleine segmenten; dan, hoe een willekeurige kamer in elk genereren Blad; en, ten slotte, hoe alle kamers samen te verbinden met gangen.
Ik heb een demoprogramma gemaakt dat een deel van de kracht van BSP laat zien. De demo is geschreven met Flixel, een gratis open-source AS3-bibliotheek voor het maken van spellen.
Wanneer u op klikt voortbrengen knop, het loopt door dezelfde code als hierboven om wat te genereren leafs, en trekt ze vervolgens naar a BitmapData object, dat vervolgens wordt weergegeven (opgeschaald om het scherm te vullen).
Wanneer je op de Spelen knop, het passeert de gegenereerde kaart Bitmap naar de FlxTilemap object, dat vervolgens een afspeelbare tilemap genereert en deze op het scherm laat zien waarin u kunt rondwandelen:
Gebruik de pijltjes toetsen om te bewegen.
Binary Space Partitioning is een methode om een gebied in kleinere stukken te verdelen.
Kortom, je neemt een gebied, genaamd a Blad, en splits het - verticaal of horizontaal - in twee kleinere blaadjes en herhaal het proces steeds opnieuw op de kleinere gebieden totdat elk gebied minstens even klein is als een ingestelde maximale waarde.
Als je klaar bent, heb je een hiërarchie van gepartitioneerd leafs, waar je van alles mee kunt doen. In 3D-afbeeldingen kunt u BSP gebruiken om te sorteren welke objecten zichtbaar zijn voor de speler, of om te helpen bij botsdetectie in kleinere, hapklare stukken.
Als u een willekeurige kaart wilt genereren, zijn er allerlei manieren om dit te doen. Je zou eenvoudige logica kunnen schrijven om willekeurig grote rechthoeken op willekeurige locaties te maken, maar dit kan je achterlaten met kaarten die vol zitten met overlappende, samengeklonterde of vreemd verdeelde ruimtes. Het maakt het ook een beetje moeilijker om de kamers met elkaar te verbinden en ervoor te zorgen dat er geen weeskamers zijn.
Met BSP kunt u meer gelijkmatig verdeelde kamers garanderen en tegelijkertijd ervoor zorgen dat u alle kamers met elkaar kunt verbinden.
Het eerste dat we nodig hebben, is onze Blad klasse. Kortom, onze Blad wordt een rechthoek, met wat extra functionaliteit. Elk Blad bevat of een paar kinderen leafs, of een paar kamers, evenals een gang of twee.
Dit is wat onze Blad lijkt op:
openbare klasse Leaf private const MIN_LEAF_SIZE: uint = 6; public var y: int, x: int, width: int, height: int; // de positie en grootte van deze Leaf public var leftChild: Leaf; // the Leaf's left child Leaf public var rightChild: Leaf; // the Leaf's right child Blad public var room: Rectangle; // de kamer die zich in deze Leaf bevindt: public var halls: Vector .; // gangen om dit blad te verbinden met andere Leafs openbare functie Leaf (X: int, Y: int, Width: int, Height: int) // initialiseer ons blad x = X; y = Y; breedte = Breedte; hoogte = hoogte; public function split (): Boolean // begin het blad in twee kinderen te splitsen als (leftChild! = null || rightChild! = null) false retourneert; // we zijn al gespleten! Afbreken! // bepaal de splitsrichting // als de breedte> 25% groter is dan de hoogte, splitsen we verticaal // als de hoogte> 25% groter is dan de breedte, splitsen we horizontaal // anders splitsen we willekeurig var splitH: Boolean = FlxG.random ()> 0,5; if (width> height && width / height> = 1.25) splitH = false; else if (height> width && height / width> = 1.25) splitH = true; var max: int = (splitH? height: width) - MIN_LEAF_SIZE; // bepaal de maximale hoogte of breedte als (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 moet je je eigen maken leafs:
const MAX_LEAF_SIZE: uint = 20; var _leafs: Vector= nieuwe Vector ; var l: Blad; // helperblad // maak eerst een blad om de 'wortel' van alle bladeren te zijn. var root: Leaf = new Leaf (0, 0, _sprMap.width, _sprMap.height); _leafs.push (root); var did_split: Boolean = true; // we doorlopen elk blad in onze Vector keer op keer, totdat er geen Leaf meer kan worden gesplitst. while (did_split) did_split = false; voor elke (l in _leafs) if (l.leftChild == null && l.rightChild == null) // als dit blad nog niet is gesplitst ... // als dit blad te groot is, of 75% kans ... als (l.width> MAX_LEAF_SIZE || l.height> MAX_LEAF_SIZE || FlxG.random ()> 0.25) if (l.split ()) // deel het blad! // als we ons hebben gesplitst, duwt het kind naar de Vector zodat we ze in de volgende lus kunnen herhalen _leafs.push (l.leftChild); _leafs.push (l.rightChild); did_split = true;
Nadat deze lus is voltooid, blijft er een Vector (een getypte array) vol met al uw leafs.
Hier is een voorbeeld met lijnen die elk van elkaar scheiden Blad:
Nu dat van jou leafs zijn gedefinieerd, we moeten de kamers maken. We willen een soort 'trickle-down'-effect waarbij we uitgaan van onze grootste,' root ' Blad helemaal tot het kleinste leafs zonder kinderen, en maak dan een kamer in elk daarvan.
Voeg deze functie dus toe aan uw Blad klasse:
public function createRooms (): void // deze functie genereert alle kamers en gangen voor dit blad en al zijn kinderen. if (leftChild! = null || rightChild! = null) // dit blad is gesplitst, dus ga in de kinderen bladeren als (leftChild! = null) leftChild.createRooms (); if (rightChild! = null) rightChild.createRooms (); else // dit blad is klaar om een kamer te maken var roomSize: Point; var roomPos: Point; // de kamer kan tussen 3 x 3 tegels zijn ter grootte van het blad - 2. roomSize = new Point (Registry.randomNumber (3, width - 2), Registry.randomNumber (3, height - 2)); // plaats de kamer in het blad, maar plaats het niet goed // tegen de zijkant van het blad (dat zou kamers samenvoegen) roomPos = new Point (Registry.randomNumber (1, width - roomSize.x - 1) , Registry.randomNumber (1, height - roomSize.y - 1)); room = new Rectangle (x + roomPos.x, y + roomPos.y, roomSize.x, roomSize.y);
Vervolgens, nadat u uw hebt gemaakt Vector van leafs, bel onze nieuwe functie vanuit je root Blad:
_leafs = nieuwe Vector; var l: Blad; // helperblad // maak eerst een blad om de 'wortel' van alle bladeren te zijn. var root: Leaf = new Leaf (0, 0, _sprMap.width, _sprMap.height); _leafs.push (root); var did_split: Boolean = true; // we doorlopen elk blad in onze Vector keer op keer, totdat er geen Leaf meer kan worden gesplitst. while (did_split) did_split = false; voor elke (l in _leafs) if (l.leftChild == null && l.rightChild == null) // als dit blad nog niet is gesplitst ... // als dit blad te groot is, of 75% kans ... als (l.width> MAX_LEAF_SIZE || l.height> MAX_LEAF_SIZE || FlxG.random ()> 0.25) if (l.split ()) // deel het blad! // als we gesplitst hebben, druk dan op het blaadje van het kind naar de vector, zodat we ze in volgende stap kunnen herhalen: _leafs.push (l.leftChild); _leafs.push (l.rightChild); did_split = true; // volgende, doorloop elk blad en maak een kamer in elk blad. root.createRooms ();
Hier is een voorbeeld van een aantal gegenereerd leafs met kamers in hen:
Zoals je kunt zien, elk Blad bevat een enkele kamer met een willekeurige grootte en positie. Je kunt spelen met de waarden voor minimum en maximum Blad grootte, en verander hoe je de grootte en positie van elke kamer bepaalt, om verschillende effecten te krijgen.
Als we onze verwijderen Blad scheidingslijnen, kunt u zien dat de kamers de hele kaart netjes vullen - er is niet veel verspilde ruimte - en hebben ze een iets meer organische uitstraling.
Accentsconagua
leafs met een ruimte binnen elke kamer, met scheidingslijnen verwijderd. Nu hoeven we alleen maar elke kamer te verbinden. Gelukkig hebben we de ingebouwde relaties ertussen leafs, alles wat we moeten doen is ervoor zorgen dat elk Blad dat heeft een kind leafs heeft een gang die zijn kinderen verbindt.
We nemen een Blad, kijk naar elk van zijn kinderen leafs, ga helemaal door elk kind totdat we bij een Blad met een kamer en verbind dan de kamers met elkaar. We kunnen dit doen op hetzelfde moment dat we onze kamers genereren.
Ten eerste hebben we een nieuwe functie nodig om deze te herleiden Blad in een van de kamers die zich in een van de kinderen bevinden leafs:
openbare functie getRoom (): Rectangle // itereer helemaal door deze bladeren om een kamer te vinden, als deze bestaat. if (room! = null) retourneer kamer; else var lRoom: Rectangle; var rRoom: Rectangle; if (leftChild! = null) lRoom = leftChild.getRoom (); if (rightChild! = null) rRoom = rightChild.getRoom (); if (lRoom == null && rRoom == null) return null; else if (rRoom == null) return lRoom; else if (lRoom == null) return rRoom; else if (FlxG.random ()> .5) retourneer lRoom; anders ga je terug naar rRoom;
Vervolgens hebben we een functie nodig die een paar kamers neemt, een willekeurig punt in beide kamers selecteert en vervolgens een of twee rechthoeken met twee tegels maakt om de punten met elkaar te verbinden.
public function createHall (l: Rectangle, r: Rectangle): void // nu verbinden we deze twee kamers met gangen. // dit ziet er behoorlijk gecompliceerd uit, maar het probeert alleen maar uit te zoeken op welk punt en dan een rechte lijn tekent, of een paar lijnen om een rechte hoek te maken om ze te verbinden. // je zou wat extra logica kunnen gebruiken om je hallen buigzamer te maken, of wat meer geavanceerde dingen te doen als je dat wilde. zalen = nieuwe Vector; var point1: Point = new Point (Registry.randomNumber (l.left + 1, l.right - 2), Registry.randomNumber (l.top + 1, l.bottom - 2)); var point2: Point = new Point (Registry.randomNumber (r.left + 1, r.right - 2), Registry.randomNumber (r.top + 1, r.bottom - 2)); var w: Number = point2.x - point1.x; var h: Number = point2.y - point1.y; als (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) if (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) if (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) if (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 (nieuwe Rectangle (point1.x, point1.y, 1, Math.abs (h)));
Wijzig tot slot uw createRooms () functie om de createHall () functie op elke Blad dat heeft een paar kinderen:
public function createRooms (): void // deze functie genereert alle kamers en gangen voor dit blad en al zijn kinderen. if (leftChild! = null || rightChild! = null) // dit blad is gesplitst, dus ga in de kinderen bladeren als (leftChild! = null) leftChild.createRooms (); if (rightChild! = null) rightChild.createRooms (); // als er zowel linker- als rechterkinderen in dit blad zijn, maak een gang tussen hen als (leftChild! = null && rightChild! = null) createHall (leftChild.getRoom (), rightChild.getRoom ()); else // dit blad is klaar om een kamer te maken var roomSize: Point; var roomPos: Point; // de kamer kan tussen 3 x 3 tegels zijn ter grootte van het blad - 2. roomSize = new Point (Registry.randomNumber (3, width - 2), Registry.randomNumber (3, height - 2)); // plaats de kamer in de Leaf, maar plaats deze niet recht tegen de zijkant van het blad (dat zou kamers samenvoegen) roomPos = new Point (Registry.randomNumber (1, width - roomSize.x - 1), Registry .randomNumber (1, height - roomSize.y - 1)); room = new Rectangle (x + roomPos.x, y + roomPos.y, roomSize.x, roomSize.y);
Uw kamers en gangen zouden er nu ongeveer zo uit moeten zien:
leafs gevuld met willekeurige kamers verbonden via gangen. Zoals je kunt zien, omdat we er zeker van zijn om elke verbinding te maken Blad, we hebben geen weeskamers meer. Het is duidelijk dat de logica in de gang iets verfijnder is om te proberen te voorkomen dat je te dicht bij andere gangen loopt, maar het werkt goed genoeg.
Dat is het eigenlijk! We hebben besproken hoe je een (relatief) eenvoudige kunt maken Blad object, dat je kunt gebruiken om een boom met verdeelde Leafs te genereren, genereer een willekeurige kamer binnenin elk Blad, en verbind de kamers via gangen.
Momenteel zijn alle objecten die we hebben gemaakt in wezen rechthoeken, maar afhankelijk van hoe je de resulterende kerker wilt gebruiken, kun je ze op allerlei manieren aan..
Nu kunt u BSP gebruiken om willekeurige kaarten te maken die u maar wilt, of deze gebruiken om power-ups of vijanden gelijkmatig over een gebied te verdelen ... of wat u maar wilt!
