blog.in-j.com

Three.jsで経路探索AIを作る【NavMeshとrecast-navigation】

Three.jsJavaScript

敵キャラやNPCを「プレイヤーのところまで、壁を避けて移動させたい」。まっすぐ向かわせるだけなら1行ですが、壁を避けるとなると経路探索(パスファインディング)が必要になります。

ゲーム業界の定番手法が NavMesh(ナビゲーションメッシュ) です。「歩ける領域」を多角形のメッシュとして持っておき、その上でA*などの探索を走らせます。UnityのNavMeshやUnreal Engineのナビゲーションと同じ仕組みを、Three.jsでは recast-navigation というライブラリで使えます(業界標準のRecast/DetourのWASM移植です)。

デモは床をクリックすると、オレンジのエージェントが壁を避けた経路(黄色い線)を計算して移動します。水色の領域が生成されたNavMeshです。

デモを別タブで開く

導入と、CDNで使うときの落とし穴

npmなら npm install recast-navigation @recast-navigation/three で入ります。CDN(importmap)で使う場合は1つ罠があるので先に共有しておきます。

<script type="importmap">
  {
    "imports": {
      "three": "https://cdn.jsdelivr.net/npm/three@0.172.0/build/three.module.js",
      "three/addons/": "https://cdn.jsdelivr.net/npm/three@0.172.0/examples/jsm/",
      "@recast-navigation/core": "https://esm.sh/@recast-navigation/core@0.16.4",
      "@recast-navigation/generators": "https://esm.sh/@recast-navigation/generators@0.16.4?external=@recast-navigation/core",
      "@recast-navigation/three": "https://esm.sh/@recast-navigation/three@0.16.4?external=three,@recast-navigation/core,@recast-navigation/generators"
    }
  }
</script>

ポイントは ?external=... です。これを付けないと、esm.shが @recast-navigation/three の中に別コピーのcore(未初期化のWASM)を同梱してしまい、Cannot read properties of undefined (reading 'raw') という謎エラーで死にます。coreとthreeを外部化して1つのインスタンスを共有させるのが正解です。私はこれで小一時間溶かしました。

使う前にWASMの初期化を待つのはRapierと同じ作法です。

import { init as initRecast, NavMeshQuery } from '@recast-navigation/core';
import { threeToSoloNavMesh, NavMeshHelper } from '@recast-navigation/three';

await initRecast();

ステージからNavMeshを生成する

threeToSoloNavMesh に「歩ける場所を構成するメッシュの配列」を渡すと、NavMeshを焼いてくれます。床も壁も全部渡してOKで、壁は自動的に「歩けない障害物」として処理されます。

const { success, navMesh } = threeToSoloNavMesh(levelMeshes, {
  cs: 0.2,           // ボクセルの細かさ(小さいほど精密で生成が重い)
  ch: 0.2,           // ボクセルの高さ
  walkableRadius: 3, // エージェントの半径(ボクセル数)
});

walkableRadius は地味に重要です。エージェントの体の半径ぶんだけ、歩ける領域が壁から内側に削られます。これのおかげで経路が壁ギリギリを通らず、キャラが壁にめり込まないわけです。単位が「ボクセル数」なのに注意してください(半径0.6mでcs=0.2なら3)。

生成結果は NavMeshHelper で可視化できます。デバッグに必須なので最初から入れておきましょう。

const helper = new NavMeshHelper({
  navMesh,
  navMeshMaterial: new THREE.MeshBasicMaterial({
    color: 0x44ccff,
    transparent: true,
    opacity: 0.25,
  }),
});
scene.add(helper);

デモの水色の領域がこれです。「壁の周りが少し空いている」のが見えるはずで、それが walkableRadius の効果です。

経路を計算して歩かせる

経路の計算は NavMeshQuery に始点と終点を渡すだけです。壁を避けたウェイポイント(経由点)の列が返ってきます。

const query = new NavMeshQuery({ navMesh });

const result = query.computePath(
  { x: agent.position.x, y: 0, z: agent.position.z }, // 現在地
  { x: clicked.x, y: 0, z: clicked.z }                // 目的地
);
const waypoints = result.path.map((p) => new THREE.Vector3(p.x, p.y, p.z));

クリック地点の取得はRaycasterの記事でやった intersects[0].point そのままです。

あとはウェイポイントを順番に消化して移動するだけです。

function updateAgent(deltaTime) {
  if (waypoints.length === 0) return;

  const target = waypoints[0];
  const to = new THREE.Vector3(target.x, agent.position.y, target.z);
  const distance = agent.position.distanceTo(to);

  if (distance < 0.15) {
    waypoints.shift(); // 到達したら次の経由点へ
    return;
  }

  const dir = to.clone().sub(agent.position).normalize();
  agent.position.addScaledVector(dir, Math.min(speed * deltaTime, distance));
  agent.rotation.y = Math.atan2(dir.x, dir.z);
}

「敵がプレイヤーを追いかける」なら、目的地をプレイヤーの位置にして定期的(毎フレームではなく0.5秒おきなど)に経路を引き直せば完成です。

ここから先の発展

  • 複数エージェントの群れ — recast-navigationには Crowd というAPIがあり、エージェント同士の回避までやってくれます。敵が10体いるようなケースはこちらが本命です
  • 複雑なマップ — 今回は箱を並べたステージでしたが、glTFで読み込んだレベルモデルのメッシュをそのまま渡せます。生成が重い場合はパラメータ(cs/ch)を粗くします
  • 段差や坂 — walkableClimb(登れる段差)や walkableSlopeAngle(登れる傾斜)のパラメータで制御できます

まとめ

  • 壁を避ける移動は「NavMesh生成 → 経路計算 → ウェイポイント移動」の3段構え
  • recast-navigationで、Unity/UEと同じ業界標準のNavMeshがThree.jsでも使える
  • CDN利用時は ?external= でcoreを共有しないと動かない(重要)
  • walkableRadius がキャラの体格を経路に反映してくれる
  • 可視化(NavMeshHelper)は最初に入れる。「なぜそこを通れないのか」が一目で分かる