BSP（Binary Space Partitioning）について

# はじめに
BSP（Binary Space Partitioning）は、ゲーム開発やダンジョン生成で広く使われる空間分割の手法です。特にローグライクゲームやダンジョン探索型ゲームでは、「ランダムな部屋配置」や「つながった通路」を作成するのに非常に役立ちます。

今回は、BSP分割についてtypescriptで実装したので説明していこうと思います。

:::note warn
※補足：
本記事では、可視化のためにHTML5 Canvasを使用していますが、描画処理そのものについては割愛しています。
:::

![Videotogif (1).gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2730382/5a845f44-fc97-404a-a1de-2f7a37fadb5c.gif)

## BSPとは？
BSP（Binary Space Partitioning）は、空間を再帰的に2つに分割していく手法です。2Dマップ生成においては、長方形のエリアを繰り返し2分割することで、部屋や通路の配置を決定します。

## BSP分割の基本ステップ
1. 最初にマップ全体を1つの大きな長方形として扱います
1. 分割方向を決定します（縦か横か - 本実装では長辺優先）
1. 分割位置をランダムに決めて（本実装では40%-60%の範囲で）、空間を2つに分けます
1. 最大の面積を持つ部屋を選んで、さらに分割していきます
1. 設定した条件（最小サイズなど）に達したら分割を終了します

## 実際のコード



<details><summary>typescript</summary>

```typescript

// RoomStatusの列挙型
enum RoomStatus {
  x = 0,
  y = 1,
  w = 2,
  h = 3
}

// BSP分割の可視化クラス
class BSPVisualizer {
  private canvas: HTMLCanvasElement;
  private ctx: CanvasRenderingContext2D;
  private width: number;
  private height: number;
  private colors: string[] = [];
  
  // 部屋の状態を管理する配列
  private roomStatus: {
    [RoomStatus.x]: number[];
    [RoomStatus.y]: number[];
    [RoomStatus.w]: number[];
    [RoomStatus.h]: number[];
  };
  
  public roomCount: number = 1;
  private animationSpeed: number = 500; // ミリ秒
  private isAnimating: boolean = false;
  
  constructor(canvasId: string) {
    this.canvas = document.getElementById(canvasId) as HTMLCanvasElement;
    if (!this.canvas) {
      throw new Error(`Canvas with ID ${canvasId} not found`);
    }
    
    this.ctx = this.canvas.getContext('2d')!;
    this.width = this.canvas.width;
    this.height = this.canvas.height;
    
    // 部屋の状態を初期化
    this.roomStatus = {
      [RoomStatus.x]: [0],
      [RoomStatus.y]: [0],
      [RoomStatus.w]: [this.width],
      [RoomStatus.h]: [this.height]
    };
    
    // 色を生成
    this.generateColors(50);
    
    // 初期描画
    this.drawRooms();
  }
  
  // 色をランダムに生成
  private generateColors(count: number): void {
    for (let i = 0; i < count; i++) {
      const hue = (i * 137.5) % 360; // 黄金角で均等に分散
      const saturation = 60 + Math.random() * 20; // 60-80%
      const lightness = 50 + Math.random() * 20; // 50-70%
      this.colors.push(`hsl(${hue}, ${saturation}%, ${lightness}%)`);
    }
  }
  
  // 分割点を決定
  private splitPoint(w: number, h: number): { isVertical: boolean; line: number } {
    // 縦横の長さに応じて分割方向を決定
    const isVertical = w > h;
    
    // 分割位置を決める（40%-60%の間でランダム）
    let min: number, max: number;
    if (isVertical) {
      min = Math.floor(w * 0.4);
      max = Math.ceil(w * 0.6);
    } else {
      min = Math.floor(h * 0.4);
      max = Math.ceil(h * 0.6);
    }
    
    // 分割線の位置
    const line = Math.floor(Math.random() * (max - min + 1)) + min;
    
    return { isVertical, line };
  }
  
  // 部屋を描画
  private drawRooms(): void {
    this.ctx.clearRect(0, 0, this.width, this.height);
    
    // 各部屋を描画
    for (let i = 0; i < this.roomCount; i++) {
      const x = this.roomStatus[RoomStatus.x][i];
      const y = this.roomStatus[RoomStatus.y][i];
      const w = this.roomStatus[RoomStatus.w][i];
      const h = this.roomStatus[RoomStatus.h][i];
      
      // 部屋の塗りつぶし
      this.ctx.fillStyle = this.colors[i % this.colors.length];
      this.ctx.fillRect(x, y, w, h);
      
      // 部屋の境界線
      this.ctx.strokeStyle = '#000';
      this.ctx.lineWidth = 2;
      this.ctx.strokeRect(x, y, w, h);
      
      // 部屋番号を表示
      this.ctx.fillStyle = '#000';
      this.ctx.font = '14px Arial';
      this.ctx.textAlign = 'center';
      this.ctx.textBaseline = 'middle';
      this.ctx.fillText(String(i + 1), x + w / 2, y + h / 2);
    }
  }
  
  // アニメーションつきで部屋を1回分割
  public async splitRoomWithAnimation(): Promise<void> {
    if (this.isAnimating) return;
    this.isAnimating = true;
    
    // 分割前の状態を描画
    this.drawRooms();
    
    // 少し待機
    await new Promise(resolve => setTimeout(resolve, this.animationSpeed / 2));
    
    // 1回分割
    this.splitRoomOnce();
    
    // 分割後の状態を描画
    this.drawRooms();
    
    // UIの更新
    this.updateRoomCount();
    
    this.isAnimating = false;
  }
  
  // 部屋を一回分割する
  public splitRoomOnce(): void {
    let maxArea = 0;
    let parentIdx = 0;

    // 最大面積の部屋を探す
    for (let j = 0; j < this.roomCount; j++) {
      const area = this.roomStatus[RoomStatus.w][j] * this.roomStatus[RoomStatus.h][j];
      if (area > maxArea) {
        maxArea = area;
        parentIdx = j;
      }
    }

    const w = this.roomStatus[RoomStatus.w][parentIdx];
    const h = this.roomStatus[RoomStatus.h][parentIdx];
    
    // 部屋が小さすぎる場合は分割しない
    if (w < 50 || h < 50) {
      console.log('これ以上分割できません: 部屋が小さすぎます');
      return;
    }
    
    const { isVertical, line } = this.splitPoint(w, h);

    if (isVertical) {
      // 垂直分割
      this.roomStatus[RoomStatus.x][this.roomCount] = this.roomStatus[RoomStatus.x][parentIdx];
      this.roomStatus[RoomStatus.y][this.roomCount] = this.roomStatus[RoomStatus.y][parentIdx];
      this.roomStatus[RoomStatus.w][this.roomCount] = line;
      this.roomStatus[RoomStatus.h][this.roomCount] = h;

      this.roomStatus[RoomStatus.x][parentIdx] += line;
      this.roomStatus[RoomStatus.w][parentIdx] -= line;
    } else {
      // 水平分割
      this.roomStatus[RoomStatus.x][this.roomCount] = this.roomStatus[RoomStatus.x][parentIdx];
      this.roomStatus[RoomStatus.y][this.roomCount] = this.roomStatus[RoomStatus.y][parentIdx];
      this.roomStatus[RoomStatus.w][this.roomCount] = w;
      this.roomStatus[RoomStatus.h][this.roomCount] = line;

      this.roomStatus[RoomStatus.y][parentIdx] += line;
      this.roomStatus[RoomStatus.h][parentIdx] -= line;
    }

    this.roomCount++;
  }
  
  // 複数回分割
  public splitRooms(count: number): void {
    for (let i = 0; i < count; i++) {
      this.splitRoomOnce();
    }
    this.drawRooms();
    this.updateRoomCount();
  }
  
  // リセット
  public reset(): void {
    this.roomCount = 1;
    this.roomStatus = {
      [RoomStatus.x]: [0],
      [RoomStatus.y]: [0],
      [RoomStatus.w]: [this.width],
      [RoomStatus.h]: [this.height]
    };
    
    this.drawRooms();
    this.updateRoomCount();
  }
  
  // 部屋数の表示を更新
  private updateRoomCount(): void {
    const roomCountElement = document.getElementById('roomCount');
    if (roomCountElement) {
      roomCountElement.textContent = String(this.roomCount);
    }
  }
}

// DOMの読み込み完了後に実行
window.addEventListener('DOMContentLoaded', () => {
  // BSP可視化クラスを初期化
  const visualizer = new BSPVisualizer('bspCanvas');
  
  // ボタンの設定
  const splitBtn = document.getElementById('splitBtn');
  const splitMultiBtn = document.getElementById('splitMultiBtn');
  const resetBtn = document.getElementById('resetBtn');
  
  if (splitBtn) {
    splitBtn.addEventListener('click', () => {
      visualizer.splitRoomWithAnimation();
    });
  }
  
  if (splitMultiBtn) {
    splitMultiBtn.addEventListener('click', () => {
      visualizer.splitRooms(5);
    });
  }
  
  if (resetBtn) {
    resetBtn.addEventListener('click', () => {
      visualizer.reset();
    });
  }
});

```

</details>






<details><summary>index.html</summary>

```html

<!DOCTYPE html>
<html lang="ja">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>BSP分割可視化</title>
  <link rel="stylesheet" href="style.css">
</head>
<body>
  <div class="container">
    <h1>BSP分割の可視化</h1>
    <div class="controls">
      <button id="splitBtn">1回分割</button>
      <button id="splitMultiBtn">5回分割</button>
      <button id="resetBtn">リセット</button>
      <div class="info">
        <span>部屋の数: <span id="roomCount">1</span></span>
      </div>
    </div>
    <canvas id="bspCanvas" width="800" height="600"></canvas>
  </div>
  <script src="dist/index.js"></script>
</body>
</html>

```
</details>


## 実装の解説
TypeScript と HTML5 Canvas を使ってBSP分割を可視化しています。コードの主要な部分を見ていきましょう。

部屋の管理方法
各部屋は、次の4つのプロパティで管理されています：

x: 部屋の左上X座標
y: 部屋の左上Y座標
w: 部屋の幅
h: 部屋の高さ

```typescript
// 部屋の状態を管理する配列
private roomStatus: {
  [RoomStatus.x]: number[];
  [RoomStatus.y]: number[];
  [RoomStatus.w]: number[];
  [RoomStatus.h]: number[];
};
```

分割のロジック
部屋の分割は「最も面積の大きい部屋」を選択して行います：

```typescript
// 最大面積の部屋を探す
for (let j = 0; j < this.roomCount; j++) {
  const area = this.roomStatus[RoomStatus.w][j] * this.roomStatus[RoomStatus.h][j];
  if (area > maxArea) {
    maxArea = area;
    parentIdx = j;
  }
}
```

分割方向は縦横比に基づいて決定され、長い方を分割します：

```typescript
// 縦横の長さに応じて分割方向を決定
const isVertical = w > h;
```


分割位置はランダムですが、極端に偏らないよう40%-60%の範囲に制限しています

```typescript
// 分割位置を決める（40%-60%の間でランダム）
let min: number, max: number;
if (isVertical) {
  min = Math.floor(w * 0.4);
  max = Math.ceil(w * 0.6);
} else {
  min = Math.floor(h * 0.4);
  max = Math.ceil(h * 0.6);
}
```












## まとめ


BSP（Binary Space Partitioning）は、空間を再帰的に縦または横に2分割する手法で、ゲームのマップ生成などでよく使われます。

実装では、常に「最も面積の大きい部屋」を選んで分割し、無秩序にならないよう分割位置を40〜60%の範囲に制限することで自然な部屋構成を作り出しています。

次はBSP法を用いてマップの自動生成をやってみようと思います。

## 参考
https://qiita.com/LeNia/items/067cc5814f00c9f86624

https://qiita.com/fazerog02/items/4855cd7303dc9365aa79