LoginSignup
6
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@generoKoki(koki nishida)in株式会社GENEROSITY

BSP（Binary Space Partitioning）について

Last updated at Posted at 2025-04-30

はじめに

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

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

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

Videotogif (1).gif

BSPとは？

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

BSP分割の基本ステップ

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

実際のコード

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();
    });
  }
});
index.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>

実装の解説

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

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

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

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

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

// 最大面積の部屋を探す
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 isVertical = w > h;

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

// 分割位置を決める（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法を用いてマップの自動生成をやってみようと思います。

参考

6
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?