Share
Lorsque vous remplissez une zone au hasard avec des objets, comme des pièces dans un donjon au hasard, vous courez le risque de créer des objets. aussi aléatoire, entraînant une agglutination ou simplement un désordre inutilisable. Dans ce tutoriel, je vais vous montrer comment utiliser Partitionnement binaire pour résoudre ce problème.
Je vais vous guider à travers quelques étapes générales pour utiliser BSP afin de créer une carte simple en 2D, qui pourrait être utilisée pour une mise en page de donjon pour un jeu. Je vais vous montrer comment faire une base Feuille objet, que nous allons utiliser pour diviser une zone en petits segments; puis, comment générer une pièce aléatoire dans chaque Feuille; et, enfin, comment connecter toutes les pièces avec les couloirs.
J'ai créé un programme de démonstration qui montre une partie de la puissance de BSP. La démo est écrite avec Flixel, une librairie AS3 libre et open source pour la création de jeux..
Lorsque vous cliquez sur le produire bouton, il parcourt le même code que ci-dessus pour générer des Leafs, puis les attire sur un BitmapData objet, qu'il affiche ensuite (mis à l'échelle pour remplir l'écran).
Quand vous frappez le Jouer bouton, il passe la carte générée Bitmap vers le FlxTilemap objet, qui génère ensuite un tilemap lisible et l’affiche à l’écran pour que vous puissiez vous déplacer:
Utilisez les flèches pour vous déplacer.
La partition d'espace binaire est une méthode de division d'une zone en morceaux plus petits..
Fondamentalement, vous prenez une zone, appelée Feuille, et divisez-le verticalement ou horizontalement en deux feuilles plus petites, puis répétez le processus sur les zones les plus petites encore et encore jusqu'à ce que chaque zone soit au moins aussi petite qu'une valeur maximale définie..
Lorsque vous avez terminé, vous avez une hiérarchie de partitionné Leafs, avec lequel vous pouvez faire toutes sortes de choses. Dans les graphiques 3D, vous pouvez utiliser BSP pour trier les objets visibles pour le lecteur ou pour aider à la détection des collisions par petits morceaux..
Si vous voulez générer une carte aléatoire, il y a toutes sortes de façons de s'y prendre. Vous pouvez écrire une logique simple pour créer des rectangles de taille aléatoire à des emplacements aléatoires, mais cela peut vous laisser avec des cartes remplies de pièces superposées, encombrées ou étrangement espacées. Il est également un peu plus difficile de connecter les salles les unes aux autres et de s'assurer qu'il n'y a pas de salles orphelines..
Avec BSP, vous pouvez garantir des pièces plus espacées, tout en veillant à pouvoir connecter toutes les pièces ensemble..
La première chose dont nous avons besoin est de créer notre Feuille classe. Fondamentalement, notre Feuille va être un rectangle, avec quelques fonctionnalités supplémentaires. Chaque Feuille contiendra soit une paire d'enfants Leafs, ou une paire de Pièces, ainsi qu'un couloir ou deux.
Voici ce que notre Feuille ressemble à:
Classe publique Leaf private const MIN_LEAF_SIZE: uint = 6; public var y: int, x: int, largeur: int, hauteur: int; // la position et la taille de cette feuille public var leftChild: Leaf; // l'enfant gauche de la feuille Leaf public var rightChild: Leaf; // l'enfant droit de la feuille Leaf public var room: Rectangle; // la pièce qui se trouve à l'intérieur de ce hall public virtuel Leaf: Vector .; // couloirs pour relier cette feuille à d'autres feuilles fonction publique Leafs Feuille (X: int, Y: int, Largeur: int, Hauteur: int) // initialise notre feuille x = X; y = Y; largeur = largeur; hauteur = hauteur; public function split (): Boolean // commence à scinder la feuille en deux enfants if (leftChild! = null || rightChild! = null) return false; // nous sommes déjà divisés! Avorter! // détermine la direction de la division // si la largeur est> 25% supérieure à la hauteur, nous nous séparons verticalement // si la hauteur est> 25% supérieure à la largeur, nous divisons horizontalement // sinon nous scindons de manière aléatoire var splitH: Boolean = FlxG.random ()> 0,5; if (largeur> hauteur && largeur / hauteur> = 1.25) splitH = false; sinon si (hauteur> largeur && hauteur / largeur> = 1.25) splitH = true; var max: int = (splitH? hauteur: largeur) - MIN_LEAF_SIZE; // détermine la hauteur ou la largeur maximale if (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!
Maintenant, vous devez réellement créer votre Leafs:
const MAX_LEAF_SIZE: uint = 20; var _leafs: Vector= nouveau vecteur ; var l: feuille; // helper Leaf // tout d'abord, créez une feuille pour qu'elle devienne la "racine" de toutes les feuilles. racine var: Leaf = new Leaf (0, 0, _sprMap.width, _sprMap.height); _leafs.push (racine); var did_split: Boolean = true; // nous parcourons chaque feuille de notre vecteur encore et encore, jusqu'à ce qu'il ne soit plus possible de scinder les feuilles. while (did_split) did_split = false; pour chaque (l dans _leafs) if (l.leftChild == null && l.rightChild == null) // si cette feuille n'est pas déjà divisée… // si cette feuille est trop grosse ou si 75% de chance… si (l.width> MAX_LEAF_SIZE || l.height> MAX_LEAF_SIZE || FlxG.random ()> 0.25) if (l.split ()) // divise la feuille! // si nous nous sommes séparés, poussez l'enfant vers le vecteur afin que nous puissions y faire une boucle. _leafs.push (l.leftChild); _leafs.push (l.rightChild); did_split = true;
Une fois cette boucle terminée, vous resterez avec un Vecteur (un tableau dactylographié) plein de tous vos Leafs.
Voici un exemple avec des lignes séparant chaque Feuille:
Maintenant que votre Leafs sont définis, nous devons faire les chambres. Nous voulons une sorte d’effet de «retombée» de notre plus grand «racine» Feuille tout le chemin à notre plus petit Leafs sans enfants, puis faites une chambre dans chacun de ceux.
Alors, ajoutez cette fonction à votre Feuille classe:
fonction publique createRooms (): void // cette fonction génère toutes les chambres et tous les couloirs de cette feuille et de tous ses enfants. if (leftChild! = null || rightChild! = null) // cette feuille a été scindée, alors entrez dans les feuilles des enfants if (leftChild! = null) leftChild.createRooms (); if (rightChild! = null) rightChild.createRooms (); else // this Leaf est prêt à créer une pièce var roomSize: Point; var roomPos: Point; // la pièce peut contenir entre 3 x 3 carreaux et la taille de la feuille - 2. roomSize = nouveau Point (Registry.randomNumber (3, largeur - 2), Registry.randomNumber (3, hauteur - 2)); // place la pièce dans la feuille, mais ne la place pas bien // contre le côté de la feuille (qui fusionnerait des pièces) roomPos = nouveau 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);
Ensuite, après avoir créé votre Vecteur de Leafs, appelez notre nouvelle fonction depuis votre racine Feuille:
_leafs = nouveau vecteur; var l: feuille; // helper Leaf // tout d'abord, créez une feuille pour qu'elle devienne la "racine" de toutes les feuilles. racine var: Leaf = new Leaf (0, 0, _sprMap.width, _sprMap.height); _leafs.push (racine); var did_split: Boolean = true; // nous parcourons chaque feuille de notre vecteur encore et encore, jusqu'à ce qu'il ne soit plus possible de scinder les feuilles. while (did_split) did_split = false; pour chaque (l dans _leafs) if (l.leftChild == null && l.rightChild == null) // si cette feuille n'est pas déjà divisée… // si cette feuille est trop grosse ou si 75% de chance… si (l.width> MAX_LEAF_SIZE || l.height> MAX_LEAF_SIZE || FlxG.random ()> 0.25) if (l.split ()) // divise la feuille! // si nous nous sommes scindés, placez l'enfant Leafs sur le vecteur afin que nous puissions y faire une boucle. _leafs.push (l.leftChild); _leafs.push (l.rightChild); did_split = true; // Ensuite, parcourez chaque feuille et créez une pièce dans chacune d'elles. root.createRooms ();
Voici un exemple de certains générés Leafs avec des chambres à l'intérieur d'eux:
Comme vous pouvez le voir, chacun Feuille contient une seule pièce avec une taille et une position aléatoires. Vous pouvez jouer avec les valeurs minimum et maximum Feuille taille, et modifier la façon dont vous déterminez la taille et la position de chaque pièce, pour obtenir des effets différents.
Si nous enlevons notre Feuille lignes de séparation, vous pouvez voir que les pièces occupent toute la carte - il n’ya pas beaucoup d’espace gaspillé - et dégagent un sentiment un peu plus organique..
Accentsconagua
Leafs avec une pièce à l'intérieur de chacun, avec les lignes de séparation enlevées. Il ne reste plus qu'à connecter chaque pièce. Heureusement, puisque nous avons les relations intrinsèques entre Leafs, tout ce que nous avons à faire est de nous assurer que chaque Feuille qui a enfant Leafs a un couloir qui relie ses enfants.
Nous prendrons un Feuille, regarde chacun de ses enfants Leafs, tout au long de chaque enfant jusqu'à ce que nous arrivions à un Feuille avec une chambre, puis connectez les chambres ensemble. Nous pouvons le faire en même temps que nous générons nos chambres.
Premièrement, nous avons besoin d’une nouvelle fonction pour itérer de tout Feuille dans l'une des pièces qui se trouvent dans l'un des enfants Leafs:
fonction publique getRoom (): Rectangle // itère complètement ces feuilles pour trouver une pièce, s'il en existe une. si (room! = null) retourne la salle; else var lRoom: Rectangle; var rRoom: Rectangle; if (leftChild! = null) lRoom = leftChild.getRoom (); if (rightChild! = null) rRoom = rightChild.getRoom (); if (lRoom == null && rRoom == null) renvoie null; else if (rRoom == null) renvoie lRoom; else if (lRoom == null) renvoie rRoom; else if (FlxG.random ()> .5) renvoie lRoom; sinon, retournez rRoom;
Ensuite, nous avons besoin d’une fonction qui prend deux pièces, choisit un point au hasard dans les deux pièces, puis crée un ou deux rectangles de deux carreaux d’épaisseur pour relier les points ensemble..
fonction publique createHall (l: Rectangle, r: Rectangle): void // maintenant, nous connectons ces deux pièces avec des corridors. // cela semble assez compliqué, mais il s'agit simplement d'essayer de déterminer quel point correspond à l'endroit où, puis tracez une ligne droite ou une paire de lignes pour créer un angle droit permettant de les relier. // vous pouvez faire un peu plus de logique pour rendre vos salles plus flexibles, ou faire des choses plus avancées si vous le souhaitez. halls = nouveau vecteur; var point1: Point = nouveau Point (Registry.randomNumber (l.ftft + 1, l.right - 2), Registry.randomNumber (l.top + 1, l.bottom - 2)); var point2: Point = nouveau 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; si (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) si (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 (nouveau Rectangle (point1.x, point1.y, 1, Math.abs (h)));
Enfin, changez votre createRooms () fonction pour appeler le createHall () fonctionner sur tout Feuille qui a une paire d'enfants:
fonction publique createRooms (): void // cette fonction génère toutes les chambres et tous les couloirs de cette feuille et de tous ses enfants. if (leftChild! = null || rightChild! = null) // cette feuille a été scindée, alors entrez dans les feuilles des enfants if (leftChild! = null) leftChild.createRooms (); if (rightChild! = null) rightChild.createRooms (); // s'il y a des enfants gauche et droit dans cette feuille, créez un couloir entre eux (leftChild! = null && rightChild! = null) createHall (leftChild.getRoom (), rightChild.getRoom ()); else // this Leaf est prêt à créer une pièce var roomSize: Point; var roomPos: Point; // la pièce peut contenir entre 3 x 3 carreaux et la taille de la feuille - 2. roomSize = nouveau Point (Registry.randomNumber (3, largeur - 2), Registry.randomNumber (3, hauteur - 2)); // place la pièce dans la feuille, mais ne la placez pas contre le bord de la feuille (qui fusionnerait les pièces) 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);
Vos pièces et couloirs devraient maintenant ressembler à ceci:
Leafs rempli de pièces aléatoires reliées par des couloirs. Comme vous pouvez le constater, car nous veillons à connecter chaque Feuille, il ne nous reste plus de chambres orphelines. Évidemment, la logique de couloir pourrait être un peu plus raffinée pour éviter de courir trop près des autres couloirs, mais cela fonctionne assez bien.
C'est fondamentalement ça! Nous avons expliqué comment créer un (relativement) simple Feuille objet, que vous pouvez utiliser pour générer un arbre de feuilles divisées, générer une pièce aléatoire à l'intérieur de chaque Feuille, et connectez les chambres par des couloirs.
Actuellement, tous les objets que nous avons créés sont essentiellement des rectangles, mais en fonction de la manière dont vous comptez utiliser le donjon résultant, vous pouvez les manipuler de différentes manières..
Maintenant, vous pouvez utiliser BSP pour créer n'importe quel type de carte aléatoire, ou pour répartir équitablement des power-ups ou des ennemis dans une zone donnée… ou ce que vous voulez.!
