Share
Quando si riempie in modo casuale un'area con oggetti, come stanze in un dungeon casuale, si corre il rischio di fare cose pure casuale, con conseguente aggregazione o solo un disordine inutilizzabile. In questo tutorial, ti mostrerò come usare Partizionamento dello spazio binario risolvere questo problema.
Ti guiderò attraverso alcuni passaggi generali per utilizzare BSP per creare una semplice mappa 2D, che potrebbe essere utilizzata per un layout di un dungeon per un gioco. Ti mostrerò come fare una base Foglia oggetto, che useremo per dividere un'area in piccoli segmenti; quindi, come generare una stanza a caso in ciascuno Foglia; e, infine, come collegare tutte le stanze insieme ai corridoi.
Ho creato un programma dimostrativo che mette in risalto parte della potenza di BSP. La demo è scritta usando Flixel, una libreria AS3 libera e open-source per creare giochi.
Quando fai clic sul creare pulsante, esegue lo stesso codice di cui sopra per generarne alcuni leafs, e poi li disegna su a BitmapData oggetto, che viene quindi visualizzato (ingrandito per riempire lo schermo).
Quando colpisci il Giocare pulsante, passa la mappa generata Bitmap oltre al FlxTilemap oggetto, che quindi genera una tilemap giocabile e la mostra sullo schermo per consentirvi di camminare in:
Usa le frecce per muoverti.
Il partizionamento dello spazio binario è un metodo per dividere un'area in pezzi più piccoli.
Fondamentalmente, prendi un'area, chiamata a Foglia, e dividerlo - verticalmente o orizzontalmente - in due fogli più piccoli, quindi ripetere il processo sulle aree più piccole più e più volte fino a quando ciascuna area è piccola almeno quanto un valore massimo impostato.
Quando hai finito, hai una gerarchia di partizioni leafs, con cui puoi fare ogni sorta di cose. Nella grafica 3D, è possibile utilizzare BSP per ordinare quali oggetti sono visibili al lettore o per aiutare il rilevamento delle collisioni in pezzi più piccoli di piccole dimensioni.
Se vuoi generare una mappa casuale, ci sono tutti i modi per farlo. Potresti scrivere una logica semplice per creare rettangoli di dimensioni casuali in posizioni casuali, ma questo può lasciarti con mappe piene di stanze sovrapposte, raggruppate o stranamente distanziate. Inoltre rende un po 'più difficile collegare le stanze tra loro e garantire che non ci siano stanze orfane.
Con BSP, puoi garantire stanze più distanziate, assicurandoti anche la possibilità di collegare tutte le stanze insieme.
La prima cosa di cui abbiamo bisogno è creare il nostro Foglia classe. Fondamentalmente, il nostro Foglia sta per essere un rettangolo, con alcune funzionalità extra. Ogni Foglia conterrà o un paio di bambini leafs, o un paio di Camere, così come un corridoio o due.
Ecco cosa è il nostro Foglia sembra:
public class Leaf private const MIN_LEAF_SIZE: uint = 6; public var y: int, x: int, width: int, height: int; // la posizione e le dimensioni di questa foglia public var leftChild: Leaf; // il bambino di sinistra della foglia Foglia public var rightFiglio: Foglia; // figlio di Leaf's right Leaf var room pubblica: Rectangle; // la stanza che si trova all'interno di questa Leaf var halls: Vector .; // corridoi per collegare questa foglia alla funzione pubblica di Leafs Leaf (X: int, Y: int, Larghezza: int, Altezza: int) // inizializza la nostra foglia x = X; y = Y; larghezza = larghezza; altezza = altezza; public function split (): Boolean // inizia a dividere la foglia in due figli se (leftChild! = null || rightChild! = null) restituisce false; // siamo già divisi! Abort! // determina la direzione di split // se la larghezza è> 25% più grande dell'altezza, ci dividiamo verticalmente // se l'altezza è> 25% più grande della larghezza, ci dividiamo orizzontalmente // altrimenti dividiamo casualmente var splitH: Boolean = FlxG.random ()> 0.5; se (larghezza> altezza && larghezza / altezza> = 1,25) splitH = falso; altrimenti se (altezza> larghezza e altezza / larghezza> = 1,25) splitH = true; var max: int = (splitH? height: width) - MIN_LEAF_SIZE; // determina l'altezza o larghezza massima se (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!
Ora, devi effettivamente creare il tuo leafs:
const MAX_LEAF_SIZE: uint = 20; var _leafs: Vector= nuovo vettore ; var l: Leaf; // helper Leaf // prima, crea una foglia per essere la 'radice' di tutte le foglie. var root: Leaf = new Leaf (0, 0, _sprMap.width, _sprMap.height); _leafs.push (root); var did_split: Boolean = true; // attraversiamo ripetutamente ogni foglia del nostro vettore, fino a quando non si possono più dividere le foglie. while (did_split) did_split = false; per ogni (l in _leafs) if (l.leftChild == null && l.rightChild == null) // se questa foglia non è già divisa ... // se questa foglia è troppo grande, o il 75% di probabilità ... se (l.width> MAX_LEAF_SIZE || l.height> MAX_LEAF_SIZE || FlxG.random ()> 0,25) if (l.split ()) // divide la foglia! // se ci siamo divisi, spingi le foglie del bambino sul vettore in modo da poterle inserire in loop vicino a _leafs.push (l.leftChild); _leafs.push (l.rightChild); did_split = true;
Al termine di questo ciclo, ti verrà lasciato un Vettore (un array tipizzato) pieno di tutti i tuoi leafs.
Ecco un esempio con linee che separano ciascuna Foglia:
Ora che sei tuo leafs sono definiti, dobbiamo fare le stanze. Vogliamo una sorta di effetto "a cascata" in cui andiamo dalla nostra più grande "radice" Foglia fino al più piccolo leafs senza figli, e poi creare una stanza in ognuno di questi.
Quindi, aggiungi questa funzione al tuo Foglia classe:
funzione pubblica createRooms (): void // questa funzione genera tutte le stanze e i corridoi per questa foglia e tutti i suoi figli. if (leftChild! = null || rightChild! = null) // questa foglia è stata divisa, quindi vai nelle foglie dei bambini se (leftChild! = null) leftChild.createRooms (); if (rightChild! = null) rightChild.createRooms (); else // questa Leaf è pronta per creare una stanza var roomSize: Point; var roomPos: Point; // la stanza può essere compresa tra 3 x 3 tessere alla dimensione della foglia - 2. roomSize = new Point (Registry.randomNumber (3, width - 2), Registry.randomNumber (3, height - 2)); // posiziona la stanza all'interno della foglia, ma non metterla a destra // contro il lato della foglia (che unirebbe le stanze insieme) 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);
Quindi, dopo aver creato il tuo Vettore di leafs, chiama la nostra nuova funzione dalla tua radice Foglia:
_leafs = new Vector; var l: Leaf; // helper Leaf // prima, crea una foglia per essere la 'radice' di tutte le foglie. var root: Leaf = new Leaf (0, 0, _sprMap.width, _sprMap.height); _leafs.push (root); var did_split: Boolean = true; // attraversiamo ripetutamente ogni foglia del nostro vettore, fino a quando non si possono più dividere le foglie. while (did_split) did_split = false; per ogni (l in _leafs) if (l.leftChild == null && l.rightChild == null) // se questa foglia non è già divisa ... // se questa foglia è troppo grande, o il 75% di probabilità ... se (l.width> MAX_LEAF_SIZE || l.height> MAX_LEAF_SIZE || FlxG.random ()> 0,25) if (l.split ()) // divide la foglia! // se ci siamo spaccati, spingiamo le foglie del bambino sul vettore in modo da poterle inserire in loop vicino a _leafs.push (l.leftChild); _leafs.push (l.rightChild); did_split = true; // next, itera su ogni Leaf e crea una stanza in ciascuna di esse. root.createRooms ();
Ecco un esempio di alcuni generati leafs con stanze all'interno di loro:
Come puoi vedere, ciascuno Foglia contiene una stanza singola con una dimensione e una posizione casuali. Puoi giocare con i valori minimi e massimi Foglia dimensione, e modificare il modo in cui si determina la dimensione e la posizione di ogni stanza, per ottenere effetti diversi.
Se togliamo il nostro Foglia linee di separazione, puoi vedere che le stanze riempiono l'intera mappa in modo piacevole - non c'è molto spazio sprecato - e hanno un aspetto leggermente più organico per loro.
Accentsconagua
leafs con una stanza all'interno di ciascuna, con le linee di separazione rimosse. Ora, tutto ciò che dobbiamo fare è connettere ogni stanza. Per fortuna, dal momento che abbiamo le relazioni integrate tra leafs, tutto ciò che dobbiamo fare è assicurarci che ognuno Foglia questo ha un figlio leafs ha un corridoio che collega i suoi bambini.
Prenderemo un Foglia, guarda ciascuno dei suoi figli leafs, andare fino in fondo attraverso ogni bambino fino a quando arriviamo a Foglia con una stanza, quindi collegare le stanze insieme. Possiamo farlo nello stesso momento in cui generiamo le nostre stanze.
Innanzitutto, abbiamo bisogno di una nuova funzione per iterare da qualsiasi Foglia in una delle stanze che si trovano all'interno di uno dei bambini leafs:
funzione pubblica getRoom (): Rectangle // itera attraverso queste pagine per trovare una stanza, se ne esiste una. se (room! = null) ritorno room; else var lRoom: Rectangle; var rRoom: Rectangle; if (leftChild! = null) lRoom = leftChild.getRoom (); if (rightChild! = null) rRoom = rightChild.getRoom (); if (lRoom == null && rRoom == null) restituisce null; altrimenti if (rRoom == null) restituisce lRoom; else if (lRoom == null) restituisce rRoom; altrimenti se (FlxG.random ()> .5) restituisce lRoom; else return rRoom;
Successivamente, abbiamo bisogno di una funzione che prende un paio di stanze, sceglie un punto casuale all'interno di entrambe le stanze e quindi crea uno o due rettangoli di due tessere per collegare i punti insieme.
funzione pubblica createHall (l: Rectangle, r: Rectangle): void // ora colleghiamo queste due stanze insieme ai corridoi. // sembra piuttosto complicato, ma sta solo cercando di capire quale punto è dove e poi o tracciare una linea retta, o una coppia di linee per creare un angolo retto per collegarle. // potresti fare qualche logica in più per rendere le tue sale più fluttuanti, o fare cose più avanzate se lo si desidera. padiglioni = nuovo vettore; 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; se (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 (new Rectangle (point1.x, point1.y, 1, Math.abs (h)));
Finalmente, cambia il tuo createRooms () funzione per chiamare il createHall () funzione su qualsiasi Foglia che ha un paio di bambini:
funzione pubblica createRooms (): void // questa funzione genera tutte le stanze e i corridoi per questa foglia e tutti i suoi figli. if (leftChild! = null || rightChild! = null) // questa foglia è stata divisa, quindi vai nelle foglie dei bambini se (leftChild! = null) leftChild.createRooms (); if (rightChild! = null) rightChild.createRooms (); // se ci sono entrambi i bambini sinistro e destro in questa foglia, crea un corridoio tra loro se (leftChild! = null && rightChild! = null) createHall (leftChild.getRoom (), rightChild.getRoom ()); else // questa Leaf è pronta per creare una stanza var roomSize: Point; var roomPos: Point; // la stanza può essere compresa tra 3 x 3 tessere alla dimensione della foglia - 2. roomSize = new Point (Registry.randomNumber (3, width - 2), Registry.randomNumber (3, height - 2)); // posiziona la stanza all'interno della foglia, ma non metterla contro il lato della foglia (che unirebbe le stanze insieme) 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);
Le tue stanze e i tuoi corridoi ora dovrebbero assomigliare a questo:
leafs riempito con camere casuali collegate tramite corridoi. Come puoi vedere, perché ci stiamo assicurando di connetterti tutti Foglia, non siamo rimasti con nessuna stanza orfana. Ovviamente, la logica del corridoio potrebbe essere un po 'più raffinata per cercare di evitare di correre troppo vicino agli altri corridoi, ma funziona abbastanza bene.
Questo è fondamentalmente! Abbiamo spiegato come creare un (relativamente) semplice Foglia oggetto, che è possibile utilizzare per generare un albero di foglie divise, generare una stanza casuale all'interno di ciascuna Foglia, e connetti le stanze tramite i corridoi.
Attualmente, tutti gli oggetti che abbiamo creato sono essenzialmente rettangoli, ma a seconda di come intendi usare il dungeon risultante, puoi gestirli in tutti i modi possibili.
Ora puoi utilizzare BSP per creare qualsiasi tipo di mappa casuale che desideri o usarlo per distribuire uniformemente potenziamenti o nemici in un'area ... o qualunque cosa tu voglia!
