Share
Når du fyller inn et område tilfeldig med objekter, som rom i et tilfeldig fangehull, risikerer du å gjøre ting også tilfeldig, noe som resulterer i clumping eller bare et ubrukelig rot. I denne veiledningen vil jeg vise deg hvordan du bruker Binær plasspartisjonering å løse dette problemet.
Jeg vil lede deg gjennom noen generelle trinn for å bruke BSP for å lage et enkelt 2D-kart, som kan brukes til en fangehullsoppsett for et spill. Jeg vil vise deg hvordan du gjør en grunnleggende Blad objekt, som vi vil bruke til å dele et område opp i små segmenter; da, hvordan å generere et tilfeldig rom i hver Blad; og til slutt, hvordan du kobler alle rommene sammen med gangene.
Jeg har laget et demo-program som viser noe av kraften til BSP. Demoen er skrevet med Flixel, et gratis, åpent AS3-bibliotek for å lage spill.
Når du klikker på generere knappen, den går gjennom samme kode som ovenfor for å generere noen Løv, blader, og trekker dem videre til en BitmapData objekt, som det da viser (oppskalert for å fylle skjermen).
Når du treffer Spille knappen, passerer den det genererte kartet bitmap over til FlxTilemap objekt, som deretter genererer en spillbar tilemap og viser den på skjermen for at du skal gå rundt i:
Bruk piltastene til å flytte.
Binær rompartisjonering er en metode for å dele et område i mindre biter.
I utgangspunktet tar du et område, kalt a Blad, og splitt den enten vertikalt eller horisontalt i to mindre blad, og gjenta prosessen på de mindre områdene igjen og igjen til hvert område er minst like lite som en angitt maksimumsverdi.
Når du er ferdig, har du et hierarki av partisjonert Løv, blader, som du kan gjøre alle slags ting med. I 3D-grafikk kan du bruke BSP til å sortere hvilke objekter som er synlige for spilleren, eller for å hjelpe med kollisjonssporing i mindre bitbitbit.
Hvis du vil generere et tilfeldig kart, finnes det mange forskjellige måter å gå på. Du kan skrive enkel logikk for å lage tilfeldig størrelse rektangler på tilfeldige steder, men dette kan gi deg kart som er fulle av overlappende, klumpete eller merkelige mellomrom. Det gjør det også litt vanskeligere å koble rommene til hverandre og for å sikre at det ikke er foreldreløse rom.
Med BSP kan du garantere flere jevnt fordelte rom, samtidig som du sørger for at du kan koble alle rommene sammen.
Det første vi trenger er å skape vår Blad klasse. I utgangspunktet vår Blad kommer til å bli et rektangel, med litt ekstra funksjonalitet. Hver Blad vil enten inneholde et par barn Løv, blader, eller et par Rom, samt en gang eller to.
Her er hva vår Blad ser ut som:
offentlig klasse Leaf private const MIN_LEAF_SIZE: uint = 6; offentlig var y: int, x: int, bredde: int, høyde: int; // posisjonen og størrelsen til denne Leaf-publiken var igjenKilde: Leaf; // Leafens venstre barn Leaf public var rightChild: Leaf; // Leafens rette barn Leaf public var room: Rectangle; // rommet som er inne i dette Leaf public var halls: Vector .; // hallways for å koble dette bladet til andre bladets offentlige funksjon Leaf (X: int, Y: int, Bredde: int, Høyde: int) // initialiser vårt blad x = X; y = Y; bredde = bredde; høyde = høyde; fellesfunksjonsdeling (): Boolean // begynner å dele bladet i to barn hvis (leftChild! = null || RightChild! = null) returnerer false; // vi er allerede delt! Avbryte! // bestemme splittens retning // hvis bredden er> 25% større enn høyden, deles vi vertikalt // hvis høyden er> 25% større enn bredden deler vi horisontalt // ellers splittes vi tilfeldig var splitH: Boolean = FlxG.random ()> 0,5; hvis (bredde> høyde og bredde / høyde> = 1,25) splitH = false; ellers hvis (høyde> bredde og & høyde / bredde = = 1,25) splitH = true; var max: int = (splitH? høyde: bredde) - MIN_LEAF_SIZE; // bestem maksimal høyde eller bredde hvis (maks <= 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!
Nå må du faktisk lage din Løv, blader:
const MAX_LEAF_SIZE: uint = 20; var _leafs: Vector= Ny Vector ; var l: Leaf; // Helper Leaf // først, lager et blad som "roten" av alle bladene. var rot: Leaf = nytt blad (0, 0, _sprMap.width, _sprMap.height); _leafs.push (rot); var did_split: boolsk = sant; // Vi løper gjennom hvert blad i vektoren vår igjen og igjen, til det ikke lenger kan deles mellom bladene. mens (did_split) did_split = false; for hver (l i _leafs) if (l.leftChild == null && l.rightChild == null) // hvis dette bladet ikke allerede er delt ... // hvis dette bladet er for stort, eller 75% sjanse ... hvis (l.width> MAX_LEAF_SIZE || l.height> MAX_LEAF_SIZE || FlxG.random ()> 0.25) hvis (l.split ()) // del Leaf! // hvis vi splittet, skyver barnet bladene til vektoren slik at vi kan gå inn i dem neste _leafs.push (l.leftChild); _leafs.push (l.rightChild); did_split = true;
Etter at denne sløyfen er ferdig, blir du igjen med a Vector (et skrevet utvalg) fullt av alle dine Løv, blader.
Her er et eksempel med linjer som skiller hver Blad:
Nå som din Løv, blader er definert, må vi gjøre rommene. Vi ønsker en slags "trickle-down" -effekt der vi går fra vår største, "rot" Blad helt til vår minste Løv, blader uten barn, og deretter lage et rom i hver enkelt av dem.
Så legg til denne funksjonen til din Blad klasse:
offentlig funksjon createRooms (): void // denne funksjonen genererer alle rom og hallways for dette bladet og alle sine barn. hvis (leftChild! = null || rightChild! = null) // dette bladet har blitt delt, så gå inn i barna bladene hvis (leftChild! = null) leftChild.createRooms (); hvis (rightChild! = null) rightChild.createRooms (); annet // dette bladet er klar til å lage et rom var rom størrelse: punkt; var roomPos: Point; // rommet kan være mellom 3 x 3 fliser til størrelsen på bladet - 2. roomSize = nytt punkt (Registry.randomNumber (3, bredde - 2), Registry.randomNumber (3, height - 2)); // plasser rommet i bladet, men ikke sett det riktig // mot siden av bladet (det ville fusjonere rom sammen) roomPos = nytt punkt (register.randomnummer (1, bredde - romstørrelse.x - 1) , Registry.randomNumber (1, høyde - roomSize.y - 1)); rom = ny rektangel (x + roomPos.x, y + roomPos.y, roomSize.x, roomSize.y);
Deretter, etter at du har opprettet din Vector av Løv, blader, ring vår nye funksjon fra roten din Blad:
_leafs = ny vektor; var l: Leaf; // Helper Leaf // først, lager et blad som "roten" av alle bladene. var rot: Leaf = nytt blad (0, 0, _sprMap.width, _sprMap.height); _leafs.push (rot); var did_split: boolsk = sant; // Vi løper gjennom hvert blad i vektoren vår igjen og igjen, til det ikke lenger kan deles mellom bladene. mens (did_split) did_split = false; for hver (l i _leafs) if (l.leftChild == null && l.rightChild == null) // hvis dette bladet ikke allerede er delt ... // hvis dette bladet er for stort, eller 75% sjanse ... hvis (l.width> MAX_LEAF_SIZE || l.height> MAX_LEAF_SIZE || FlxG.random ()> 0.25) hvis (l.split ()) // del Leaf! // hvis vi splittet, skyv barnet Leafs til Vector slik at vi kan gå inn i dem neste _leafs.push (l.leftChild); _leafs.push (l.rightChild); did_split = true; // neste, gjenta gjennom hvert blad og opprett et rom i hver enkelt. root.createRooms ();
Her er et eksempel på noen generert Løv, blader med rom inne i dem:
Som du kan se, hver Blad inneholder et enkeltrom med en tilfeldig størrelse og posisjon. Du kan spille med verdiene for minimum og maksimum Blad størrelse og endre hvordan du bestemmer størrelsen og plasseringen av hvert rom for å få forskjellige effekter.
Hvis vi fjerner vår Blad separator linjer, kan du se at rommene fyller hele kartet pent - det er ikke mye bortkastet plass - og har en litt mer organisk følelse for dem.
Accentsconagua
Løv, blader med et rom inne i hver, med separatorlinjer fjernet. Nå, alt vi trenger å gjøre er å koble til hvert rom. Heldigvis, siden vi har de innebygde relasjonene mellom Løv, blader, alt vi trenger å gjøre er å sørge for at hver Blad som har barn Løv, blader har en gang som forbinder sine barn.
Vi tar en Blad, se på hver av sine barn Løv, blader, gå hele veien gjennom hvert barn til vi kommer til en Blad med et rom, og koble deretter sammen rommene. Vi kan gjøre dette samtidig som vi genererer rommene.
Først trenger vi en ny funksjon for å iterere fra noen Blad inn i et av rommene som er inne i ett av barnet Løv, blader:
offentlig funksjon getRoom (): Rektangel // iterate helt gjennom disse bladene for å finne et rom, hvis det finnes en. hvis (rom! = null) returrom; ellers var lRoom: rektangel; var rRoom: rektangel; hvis (leftChild! = null) lRoom = leftChild.getRoom (); hvis (rightChild! = null) rRoom = rightChild.getRoom (); hvis (lRoom == null && rRoom == null) returnere null; ellers hvis (rRoom == null) returnerer lRoom; ellers hvis (lRoom == null) returnerer rRoom; ellers hvis (FlxG.random ()> .5) returnerer lRoom; ellers returner rRoom;
Deretter trenger vi en funksjon som tar et par rom, plukker et tilfeldig punkt i begge rommene, og oppretter deretter en eller to to-flattete rektangler for å koble sammen punktene.
offentlig funksjon createHall (l: rektangel, r: rektangel): void // nå kobler vi disse to rommene sammen med gangene. // dette ser ganske komplisert ut, men det prøver bare å finne ut hvilket punkt er hvor og da enten tegne en rett linje eller et par linjer for å gjøre en vinkel for å koble dem til. // Du kan gjøre litt ekstra logikk for å gjøre salene dine mer bendy, eller gjør noen mer avanserte ting hvis du vil. haller = ny vektor; var punkt1: Punkt = nytt punkt (Registry.randomNumber (l.left + 1, l.right - 2), Registry.randomNumber (l.top + 1, l.bottom - 2)); var punkt2: Punkt = nytt punkt (Registry.randomNumber (r.left + 1, r.right - 2), Registry.randomNumber (r.top + 1, r.bottom - 2)); var w: tall = punkt2.x - punkt1.x; var h: Nummer = punkt2.y - punkt1.y; hvis (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) hvis (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) hvis (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) hvis (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 (nytt rektangel (punkt1.x, punkt1.y, 1, Math.abs (h)));
Endelig, endre din createRooms () funksjon å ringe createHall () funksjon på noen Blad som har et par barn:
offentlig funksjon createRooms (): void // denne funksjonen genererer alle rom og hallways for dette bladet og alle sine barn. hvis (leftChild! = null || rightChild! = null) // dette bladet har blitt delt, så gå inn i barna bladene hvis (leftChild! = null) leftChild.createRooms (); hvis (rightChild! = null) rightChild.createRooms (); // Hvis det er både venstre og høyre barn i dette bladet, opprett en gang mellom dem hvis (leftChild! = null && rightChild! = null) createHall (leftChild.getRoom (), rightChild.getRoom ()); annet // dette bladet er klar til å lage et rom var rom størrelse: punkt; var roomPos: Point; // rommet kan være mellom 3 x 3 fliser til størrelsen på bladet - 2. roomSize = nytt punkt (Registry.randomNumber (3, bredde - 2), Registry.randomNumber (3, height - 2)); // plasser rommet i bladet, men legg det ikke rett mot siden av bladet (det ville fusjonere rom sammen) roomPos = nytt punkt (register.randomnummer (1, bredde - romstørrelse.x - 1), register .randomNumber (1, høyde - roomSize.y - 1)); rom = ny rektangel (x + roomPos.x, y + roomPos.y, roomSize.x, roomSize.y);
Dine rom og ganger bør nå se slik ut:
Løv, blader fylt med tilfeldige rom koblet via gangene. Som du kan se, fordi vi sørger for å koble hver Blad, Vi er ikke igjen med noen foreldreløse rom. Selvfølgelig kan gangens logikk være litt mer raffinert for å unngå å kjøre for nær andre ganger, men det fungerer godt nok.
Det er egentlig det! Vi har dekket hvordan du lager en (relativt) enkel Blad objekt, som du kan bruke til å generere et tre med delte blad, genererer et tilfeldig rom i hver Blad, og koble rommene via gangene.
For øyeblikket er alle objekter vi opprettet i hovedsak rektangler, men avhengig av hvordan du har tenkt å bruke den resulterende fangehullet, kan du håndtere dem på mange måter.
Nå kan du bruke BSP til å gjøre noen form for tilfeldige kart du vil ha, eller bruk den til jevnt å distribuere power ups eller fiender på tvers av et område ... eller hva du vil!
