Skip to content
Islumina

aiquadtreejs — 空間分割

This content is not available in your language yet.

import { Aside } from ‘@astrojs/starlight/components’;

aiquadtreejs 是一個專為 per-frame rebuild 設計的 2D quadtree。它只做廣泛相（broadphase）：插入 AABB、查詢候選清單、由呼叫方做精確碰撞判斷。設計目標是 PixiJS 遊戲 500–10,000 個活躍 entity 的規模。

安裝

Section titled “安裝”
Terminal window
pnpm add aiquadtreejs

快速開始

Section titled “快速開始”
import { createQuadtree, type AABB } from "aiquadtreejs";


type Body = { id: number } & AABB;


// 1. 建立 quadtree（通常建一次就好）
const qt = createQuadtree<Body>({
  bounds: { x: 0, y: 0, width: 800, height: 600 },
  maxObjects: 10,   // 一個節點超過這個數量才分裂
  maxLevels: 4,     // 最大深度
});


// 2. 每幀：clear + 重新 insert
function rebuild(entities: Body[]) {
  qt.clear();
  for (const e of entities) qt.insert(e);
}


// 3. 查詢：broadphase 取候選，再做精確判斷
function checkCollisions(player: Body) {
  const region: AABB = {
    x: player.x - 32,
    y: player.y - 32,
    width: 64,
    height: 64,
  };
  const candidates = qt.retrieve(region); // Set 已去重
  return candidates.filter((c) => c.id !== player.id && aabbOverlap(c, player));
}

Per-frame rebuild 是刻意的設計

Section titled “Per-frame rebuild 是刻意的設計”

追蹤 entity 移動到哪個 leaf 的做法理論上省 re-insert，但實作容易出錯。clear() + 全量重新 insert() 在 4 層深度的樹裡很快，而且邏輯清楚。這是 aiquadtreejs 的核心取捨。

AABB 座標語義

Section titled “AABB 座標語義”

x + width、y + height 是開區間（exclusive），與 PixiJS getBounds() 的慣例一致。

刻意排除的功能

Section titled “刻意排除的功能”
  • 精確碰撞：broadphase 只給候選，caller 負責 AABB/圓形/pixel 精確判斷
  • 3D / octree / R-tree / KD-tree：不在 2D 簡單 AABB 的設計範疇
  • Circle / Line primitives：只支援矩形 AABB
  • 移動追蹤：用 clear() + re-insert() 取代

常見搭配

Section titled “常見搭配”
  • 與 aiecsjs 搭配：ECS entity 的 SoA Position 欄位直接組成 AABB 插入 quadtree，不需要另外建物件
  • 與 aipooljs 搭配：Pool 管理子彈物件，quadtree 做空間查詢決定哪些要精確判斷
  • 獨立使用：遊戲 enemy AI 視野查詢、區域事件觸發等