🚵🏽 👨🏿‍🎓 ⛩️ BSPツリーを使用してゲームカードを作成する 🌲 🚠 👩‍👩‍👦

ランダムな順序でオブジェクト（たとえば、ダンジョンの部屋）で領域を埋めると、すべてがランダムになりすぎるリスクがあります。結果は、まったく役に立たないカオスかもしれません。このチュートリアルでは、 Binary Space Partitioning（BSP）を使用してこの問題を解決する方法を示します。

BSPを使用して簡単な2次元マップ（ダンジョンマップなど）を作成する方法について、詳細にステップごとに説明します。領域を小さなセグメントに分割するために使用する単純なLeafオブジェクトを作成する方法を示します。次に、各Leafランダムルームを生成します。最後に、すべての部屋を廊下に接続する方法を学びます。

注：例のコードはAS3で記述されていますが、この概念は他のほぼすべての言語で使用できます。

デモプロジェクト

BSPの機能の一部を示すデモを作成しました。デモは、オープンソースのAS3 Flixelライブラリを使用して記述されています。

[ Generate ]ボタンをクリックすると、デモはコードを実行して複数のLeafを生成し、それらをBitmapDataオブジェクトに描画します。その後、画面に表示されます（ズームインして画面いっぱいに表示されます）。

ランダムなカード生成。 （クリックしてデモをダウンロードします。）

[ 再生 ]ボタンをクリックすると、生成されたBitmapマップがFlxTilemapオブジェクトにFlxTilemapれ、再生可能なタイルマップが生成されて画面に表示されます。あなたは矢印を使ってそれをさまようことができます：

マップ上でプレイします。 （クリックしてデモをダウンロードします。）

BSPとは何ですか？

バイナリスペースパーティション分割は、領域をより小さな部分に分割する方法です。

Leafと呼ばれる領域を取り、それを垂直または水平に2つの小さなシートに分割し、各領域が所定の最大値以下になるまで、小さな領域で繰り返し処理を繰り返します。

プロセスを完了すると、壊れたLeaf階層が得られ、これを使用して必要な操作を実行できます。 3Dグラフィックスでは、BSPを使用して、プレーヤーに表示されるオブジェクトを並べ替えたり、さらに小さな部分の衝突を検出したりできます。

BSPを使用してカードを生成する理由

ランダムカードを生成するには、さまざまな方法があります。ランダムな場所にランダムなサイズの長方形を作成する簡単なロジックを作成できますが、結果は、交差する部屋、混雑する部屋、または奇妙な場所にある部屋で満たされたマップです。さらに、すべての部屋を互いに接続し、隔離された部屋がないことを確認することはもう少し困難です。

BSPのおかげで、より均等に分散された部屋の作成を保証し、それらの接続を確保できます。

葉作り

コードで最初に作成する必要があるのは、 Leafクラスです。基本的に、 Leafはいくつかの追加機能を備えた長方形になります。各Leafには、 Leaf子会社のペア、またはRoomペア、および1つまたは2つの廊下が含まれます。

Leafコードは次のようになります。

 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; //  ! } }

次に、 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; } } } } }

このループを完了した後Vector 、葉で満たされたVector （型付き配列）がVectorています。

以下は、線で区切られた葉の例です。

葉に分割された領域の例

部屋の作成

葉を決めたので、今度は部屋を作成する必要があります。「あふれる」という独特の効果を実現したいのです。最大の「根」のLeafから始めて、娘の葉のない最小のLeaf降りて、それぞれに部屋を作ります。

したがって、この関数をLeafクラスに追加します。

 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); } }

葉からVectorを作成したので、ルートシートから新しい関数を呼び出します。

 _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();

生成されたいくつかのリーフの例を次に示します。

それぞれの中にランダムな部屋がある葉の例。

ご覧のとおり、各シートには、ランダムなサイズでランダムな配置の部屋が1つ含まれています。シートの最小サイズと最大サイズの値を試して、各部屋のサイズと位置を変更して、さまざまな効果を得る方法を学習できます。

葉を区切る線を削除すると、部屋がマップのボリューム全体を十分に満たしていることがわかります（余分なスペースはあまりありません）。

分割線のない部屋のある葉の例。

葉コンパウンド

次に、各部屋を接続する必要があります。幸いなことに、リーフ間のビルトイン接続があるため、子リーフを持つすべてのリーフが確実に接続されるようにすることしかできません。

葉を取り、その娘の葉のそれぞれを見て、娘の葉のそれぞれを通過し、部屋のある葉に達するまで、部屋を接続します。ルームを生成しながらこれを行うことができます。

まず、任意のシートからその子リーフ内の部屋の1つまで反復する新しい関数が必要です。

 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; } }

次に、いくつかの部屋を受け取り、両方の部屋の中からランダムなポイントを選択し、2つのポイントを接続する1つまたは2つの幅の長方形を作成する関数が必要です。

 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))); } } }

最後に、 createRooms()関数をcreateRooms()して、子の葉のペアを持つ各シートに対してcreateRooms()関数をcreateRooms() 。

 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); } }

結果の部屋と廊下は次のようになります。

ランダムな部屋と接続された廊下で満たされた葉の例。

ご覧のとおり、すべての葉を接続しているため、隔離された部屋はありませんでした。明らかに、コリドーを作成するためのロジックは、コリドーが互いに近すぎないようにもう少し複雑にする必要がありますが、今でもプログラムは非常にうまく機能します。

まとめると

これですべてです！分割された葉の木の生成に使用できる（比較的）シンプルなLeafオブジェクトの作成方法、各葉にランダムな部屋を作成する方法、部屋を廊下に接続する方法を学びました。

この段階では、作成したオブジェクトはすべて長方形ですが、必要に応じて任意の形状を指定できます。

これで、BSPを使用して任意の種類のランダムカードを作成したり、BSPを使用してボーナスや敵の領域に均等に配布したり、他のアプリケーションを作成したりできます。

BSPツリーを使用してゲームカードを作成する