モートン順序と空間分割 (Morton Order / Z-Curve)

v1.2.1 の注意点: PlutoEngine は現在、最大限のパフォーマンスを引き出すために WebGPU、InstanceBufferArena、SoA、および Flyweight pattern (Zero-Allocation) を利用しています。

PlutoEngine v1.2.1 は、数万のエンティティの衝突判定や描画順序の最適化のために、空間分割アルゴリズムである「モートン順序（Z-Curve）」プラグインを提供します。

モートン順序とは？

モートン順序は、2次元（または3次元）の座標データを、空間の局所性を保ったまま1次元の整数値（モートンコード）にマッピングする手法です。 2進数のビットを交互にインターリーブ（交差）させることで計算されます。

X座標: 011
Y座標: 101
モートンコード: 100111

CPU ベースの空間ハッシュ

一般的な四分木（Quadtree）は、木構造の生成やノードの再帰的走査でメモリアロケーション（GC）とポインタチェイスが発生するため、データ指向設計（SoA）に反します。

PlutoEngine v1.2.1 では、エンティティのX, Y座標からモートンコードを計算し、CPU 上でエンティティを空間的に近い順に並び替えます。これにより、広域衝突判定（Broad-phase Collision Detection）やカリングが、ポインタを一切使わない Uint32Array の1次元配列のバイナリサーチや線形走査だけでゼロアロケーションで高速に完了します。

NOTE

WGSL コンピュートシェーダによる GPU ソートは将来の対応として検討中です。現行の実装は CPU 側で完結しています。

Standalone Usage

import { MortonSpatialHash } from '@pluto-engine/morton';
const solver = new MortonSpatialHash();

Plugin Usage (this.registerPlugin)

import { MortonPlugin } from '@pluto-engine/morton';

class MyScene extends Scene {
  constructor() {
    super();
    this.registerPlugin(new MortonPlugin());
  }

  update() {
    // 毎フレームのゼロアロケーション空間ハッシュ更新
    this.spatialHash.update(this.arena.posX, this.arena.posY, this.arena.activeCount);
  }
}