Geekly Articles each Day
📜 ⬆️ ⬇️

Using BSP-trees to create game cards

image

When you fill an area with objects (for example, rooms in a dungeon) in a random order, you risk that everything will be too random. The result may be absolutely useless chaos. In this tutorial, I’ll show you how to use Binary Space Partitioning (BSP) to solve this problem.

I will describe in detail and in stages the use of BSP to create a simple two-dimensional map, for example, a dungeon scheme. I will show you how to create a simple Leaf object that we use to divide an area into small segments. Then we will generate a random room in each Leaf . And finally, learn how to connect all the rooms corridors.
')
Note: although the code of the examples is written in AS3, the concept can be used in almost any other language.


Demo project


I created a demo showing part of the capabilities of the BSP. The demo is written using the free open source AS3 Flixel library.

When you click on the Generate button, the demo executes the code to generate several Leaf , and then draws them in the BitmapData object, after which it is displayed on the screen (zooming in to fill the screen).


Generate a random map. ( Click to download the demo. )

When you click on the Play button, the program sends the generated Bitmap map to the FlxTilemap object, which generates a playable tile map and displays it on the screen. You can wander through it using the arrows:


We play on the map. ( Click to download the demo. )


What is bsp?


Binary partitioning of space is a way of dividing a region into smaller parts.

We take the area called leaf ( Leaf ), and divide it vertically or horizontally into two smaller sheets, and then repeat the process with smaller areas, again and again, until each area is less than or equal to the specified maximum value.

After the completion of the process, we will have a hierarchy of broken Leaf , with which you can do anything. In 3D graphics, BSP can be used to sort objects visible to the player or to recognize collisions in even smaller parts.


Why use BSP to generate maps?


There are many different ways to generate a random map. You can write simple logic to create random-sized rectangles in random places, but the result is maps filled with intersecting, crowded or oddly located rooms. In addition, it is a little more difficult to connect all the rooms with each other and to make sure that there are no isolated rooms left.

Thanks to BSP, you can guarantee the creation of more evenly distributed rooms and ensure their connection.


Making leaves


The first thing we need to create in the code is the Leaf class. In essence, our Leaf will be a rectangle with some additional features. Each Leaf will contain either a pair of Leaf subsidiaries, or a pair of Room rooms, as well as one or two corridors.

Here’s what the Leaf code looks like:

 public class Leaf { private const MIN_LEAF_SIZE:uint = 6; public var y:int, x:int, width:int, height:int; //      public var leftChild:Leaf; //   Leaf   public var rightChild:Leaf; //   Leaf   public var room:Rectangle; // ,    public var halls:Vector.; // ,       public function Leaf(X:int, Y:int, Width:int, Height:int) { //   x = X; y = Y; width = Width; height = Height; } public function split():Boolean { //        if (leftChild != null || rightChild != null) return false; //    ! ! //    //      25%  ,    //      25%  ,    //       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; //      if (max <= MIN_LEAF_SIZE) return false; //   ,    ... var split:int = Registry.randomNumber(MIN_LEAF_SIZE, max); // ,    //           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; //  ! } }

Now we need to create a Leaf :

 const MAX_LEAF_SIZE:uint = 20; var _leafs:Vector<Leaf> = new Vector<Leaf>; var l:Leaf; //   //   ,   ""    . var root:Leaf = new Leaf(0, 0, _sprMap.width, _sprMap.height); _leafs.push(root); var did_split:Boolean = true; //           Vector,     ,   . while (did_split) { did_split = false; for each (l in _leafs) { if (l.leftChild == null && l.rightChild == null) //     ... { //     ,    75%... if (l.width > MAX_LEAF_SIZE || l.height > MAX_LEAF_SIZE || FlxG.random() > 0.25) { if (l.split()) //  ! { //    ,     Vector,           _leafs.push(l.leftChild); _leafs.push(l.rightChild); did_split = true; } } } } }

After completing this cycle, we will have a Vector (typed array) filled with leaves.

Here is an example with leaves separated by lines:


An example of an area divided into leaves


Creating rooms


We decided on the leaves, now we need to create rooms. We want to implement a peculiar effect of “flowing”: let's start with the largest, “root” Leaf and go down to the smallest Leaf that do not have child leaves, and then create a room in each of them.

Therefore, we will add this function to the Leaf class:

 public function createRooms():void { //               . if (leftChild != null || rightChild != null) { //    ,       if (leftChild != null) { leftChild.createRooms(); } if (rightChild != null) { rightChild.createRooms(); } } else { //       var roomSize:Point; var roomPos:Point; //        3 x 3     - 2. roomSize = new Point(Registry.randomNumber(3, width - 2), Registry.randomNumber(3, height - 2)); //    ,      //     (  ) 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); } }

Now that we have created a Vector from leaves, let's call our new function from the root leaf:

 _leafs = new Vector<Leaf>; var l:Leaf; //   //   ,   ""  . var root:Leaf = new Leaf(0, 0, _sprMap.width, _sprMap.height); _leafs.push(root); var did_split:Boolean = true; //       Vector,   ,     . while (did_split) { did_split = false; for each (l in _leafs) { if (l.leftChild == null && l.rightChild == null) //      ... { //     ,    75%... if (l.width > MAX_LEAF_SIZE || l.height > MAX_LEAF_SIZE || FlxG.random() > 0.25) { if (l.split()) //  ! { //    ,     Vector,           _leafs.push(l.leftChild); _leafs.push(l.rightChild); did_split = true; } } } } } //           . root.createRooms();

Here is an example of several generated leaves with rooms inside:


An example of leaves with random rooms inside each.

As you can see, each sheet contains one room of random size and with a random arrangement. You can experiment with the values ​​of the minimum and maximum sheet size, change the size and position of each room to learn how to get different effects.

If you remove the lines separating the leaves, you can see that the rooms fill the entire volume of the card well - not much space is needed - and they look a bit more natural.


An example of leaves with rooms inside without dividing lines.


Compound leaves


Now we need to connect each room. Fortunately, since we have built-in links between the leaves, we can only make sure that every leaf that has daughter leaves is connected to them.

We take a sheet, consider each of its daughter leaves, go through each of the daughter leaves, until we reach the sheet with the room, and then connect the rooms. We can do this while generating rooms.

To begin with, we need a new function, iteratively passing from any sheet to one of the rooms inside its daughter leaves:

 public function getRoom():Rectangle { //       ,   ,   . if (room != null) return 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) return null; else if (rRoom == null) return lRoom; else if (lRoom == null) return rRoom; else if (FlxG.random() > .5) return lRoom; else return rRoom; } }

Then we need a function that takes a couple of rooms and selects a random point inside both rooms, and then creates rectangles one or two tiles wide, connecting two points together.

 public function createHall(l:Rectangle, r:Rectangle):void { //       . //   ,     ,    ,        ,       . //     ,    ,     . halls = new Vector<Rectangle>; 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; if (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 //  (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 //  (h == 0) { halls.push(new Rectangle(point1.x, point1.y, Math.abs(w), 1)); } } else //  (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))); } } }

Finally, we createRooms() function to createRooms() function for each sheet that has a pair of child leaves:

 public function createRooms():void { //               . if (leftChild != null || rightChild != null) { //    ,       if (leftChild != null) { leftChild.createRooms(); } if (rightChild != null) { rightChild.createRooms(); } //       ,    ,      if (leftChild != null && rightChild != null) { createHall(leftChild.getRoom(), rightChild.getRoom()); } } else { //       var roomSize:Point; var roomPos:Point; //        3 x 3     - 2. roomSize = new Point(Registry.randomNumber(3, width - 2), Registry.randomNumber(3, height - 2)); //    ,          (  ) 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); } }

The resulting rooms and corridors should look something like this:


An example of leaves filled with random rooms and connected corridors.

As you can see, since we connected all the leaves, we have no isolated rooms. Obviously, the logic of creating corridors should be a little more complicated so that the corridors are not located too close to each other, but even now the program works quite well.


Summarize


That's all! We learned how to create a (relatively) simple Leaf object that can be used to generate a tree of separated leaves, created random rooms in each of the leaves, and connected rooms with corridors.

At this stage, all objects created by us are rectangles, but if necessary, they can be given any shape.

Now you can use BSP to create any type of random cards, apply it to even distribution in the field of bonuses or enemies ... or come up with any other use.

Source: https://habr.com/ru/post/332832/

More articles:


All Articles