navigation

navcatによるナビゲーション

navcatは、元のジオメトリからナビメッシュ（レベル内で相互に接続された歩行可能なポリゴン）を構築し、その上で経路探索クエリに応答します。敵が障害物を避けて移動する、NPC が巡回する、ユニットに地点を指示する、エージェントが壁や隙間を避けるなど、ワールド内を賢く移動する必要がある場合に使用します。レンダリングエンジンには依存しません。navcat/threeを使うと Three.js に対応できます。

そもそもナビメッシュは必要でしょうか？「開けた平坦な地面でターゲットに向かってまっすぐ進む」なら、ナビメッシュは大げさです。直接操舵してください。エージェントが障害物を避けて進む必要がある場合、起伏のある地形や複数階層の地形を移動する場合、または連携して群衆として移動する場合に、ナビメッシュの価値が出てきます。より単純なケースなら、独自の操舵を実装するのが適切です。

バージョンは変わります — インストール済みの型を確認してください

このスキルは、適切な機能と判断へ導くものであり、正確なシグネチャを固定するものではありません。navcat の API（エクスポート名、オプションのフィールド、戻り値の形式）はバージョンによって変わります。呼び出す前に、インストール済みパッケージのエクスポートと型（navcat、navcat/blocks、navcat/three）を確認し、現在の名前とフィールドを確かめてください。以下のコードは形を示すものであり、仕様ではありません。

パイプラインの概要

1. ジオメトリを抽出する — navcat/threeのgetPositionsAndIndices(meshes)を使って、歩行可能な Three.js メッシュ（床、地形、障害物）をpositions／indicesに変換します。
2. ナビメッシュを生成する — 単一の領域（デフォルト）にはnavcat/blocksのgenerateSoloNavMesh(input, options)を、大規模なワールドや部分的な再構築にはgenerateTiledNavMeshを使います。
3. クエリを実行する — 生成されたナビメッシュ上で、経路、最も近い歩行可能な点、ランダムな点、視線判定を取得します。
4. エージェントを移動させる — 毎フレーム自分で経路をたどらせるか、多数のエージェントをcrowdブロックに渡します。

import { findPath, DEFAULT_QUERY_FILTER } from 'navcat'
import { generateSoloNavMesh } from 'navcat/blocks'
import { getPositionsAndIndices, createNavMeshHelper } from 'navcat/three'

const [positions, indices] = getPositionsAndIndices([floor, ...obstacles])
const { navMesh } = generateSoloNavMesh({ positions, indices }, options) // see options below

scene.add(createNavMeshHelper(navMesh).object) // debug: see the walkable surface

const result = findPath(navMesh, start, end, halfExtents, DEFAULT_QUERY_FILTER)
const waypoints = result.path.map((p) => p.position) // [x,y,z][]

halfExtentsは、start／endをメッシュ上にスナップするための検索ボックスです。クエリが失敗する場合、指定した点がナビメッシュから外れている可能性があります。範囲を広げるか、最初に最近傍ポリゴンのクエリでスナップしてください。

生成の調整

生成オプションでは、エージェントに合わせてナビメッシュのサイズを設定し、詳細さと速度のバランスを調整します。フィールドの一覧を暗記する必要はありません（インストール済みのSoloNavMeshOptionsから確認してください）。大切なのは、重要な項目の意味を把握することです。

• エージェントのサイズ — 歩行可能な半径（壁から確保するクリアランス）、高さ（低い天井を除外）、よじ登り高さ（上れる段差の上限）、歩行可能な傾斜角の上限です。キャラクターに合わせて設定してください。
• 解像度 — セルサイズ／セル高さ（ボクセルグリッド）です。小さくすると精細になりますが、処理は遅くなります。セルサイズはエージェントの半径のおよそ 1/3 から始めるのが一般的です。
• 単純化 — 領域、エッジ、誤差の上限によって、生成されるポリゴンの粗さと滑らかさを調整します。

個々の生成段階をカスタマイズする（領域にタグを付ける、領域を追加する）ために、navcat はワンコールのジェネレーターの基盤となる Recast 風の低レベルなステップも公開しています。ジェネレーターでは必要な表現ができない場合に限り、これらを使用してください。

ナビメッシュのクエリ

すべてのクエリでは、ナビメッシュとクエリフィルター（エリアコスト／フラグを指定しない場合は DEFAULT_QUERY_FILTER）を使用します。経路探索には次の機能があります。

• findPath — 2 点間の完全な経路をウェイポイントとして取得します。曲がりのない、サーフェスに沿った経路には findSmoothPath を使用します。（キャッシュや動的な移動では、ノード経路と直線経路の組み合わせにより、より細かく制御できます。）
• 最も近い歩行可能地点 — ワールド座標上の位置をメッシュ上にスナップします。「ここに到達できるか」の判定や、クエリ失敗の修正の基礎となります。
• ランダムな歩行可能地点（任意の地点、または中心から半径内）— スポーン地点、パトロール先、徘徊目標に使用します。
• サーフェスに沿った raycast — メッシュ上の 2 点間の視線を調べます。ヒットなしの場合の規約に注意してください。レイが遮られていない場合、ヒットパラメーターにはパッケージの「壁なし」センチネル値（1.0 や 0 ではなく、最大値）が返されます。決めつけずに、インストール済みの型定義で確認してください。
• moveAlongSurface — 歩行可能エリア内にとどまりながら、位置を目標に向けて移動します。完全な再経路探索を行わないシンプルなコントローラーです。
• オフメッシュ接続 — メッシュではつながらない隙間を越えるための明示的なリンクです（ジャンプ、はしご、テレポートなど）。

毎フレームの経路追従

findPath はウェイポイントを返します。エージェントの移動は、ループ側で行う必要があります。現在のウェイポイントに向かって移動し、到達したら次に進み、目的地が変わった場合やエージェントが経路から外れた場合は、経路を再計算します。

let waypoints = result.path.map((p) => p.position)
let i = 0

function updateAgent(pos, speed, delta) {
  if (i >= waypoints.length) return // arrived
  const t = waypoints[i]
  const dx = t[0] - pos[0], dz = t[2] - pos[2]
  const dist = Math.hypot(dx, dz)
  if (dist < 0.2) { i++; return }
  pos[0] += (dx / dist) * speed * delta
  pos[2] += (dz / dist) * speed * delta
}

多数のエージェント → crowd ブロック

グループ（敵の群れや一緒に移動するユニットなど）には、経路を手動で追従させる代わりに、navcat/blocks の crowd API を使用してください。フレームに分散した経路探索、エージェント同士や壁との衝突回避、間隔の確保を担います。群れが重なり合ったひと塊にならないようにしてください。

• 各エージェントに、その体格に合った 半径 を設定し、衝突回避によって間隔を確保します。毎フレーム、各エージェントの速度を手動で同じ地点に向けて設定しないでください。衝突回避が無効になり、エージェントが積み重なってしまいます。
• 目標に群がらせるには、各エージェントの目標を、その周囲のリング上で オフセット します（インデックス／角度に応じて分散させます）。そうすれば、中心を奪い合うのではなく、目標を取り囲みます。
• エージェントが互いの周囲を滑らかに移動し、震えたり互いにめり込んだりしないように、衝突回避の強さと最大加速度を調整します。

高度な用途では、crowd ブロックをプロジェクトにコピーして変更してください。

制限事項 — 足りない部分を自分で補うタイミングを把握する

• ナビメッシュは静的です。 生成時点のジオメトリを反映します。歩行可能なジオメトリが変化した場合（ドアが開く、地形が変形するなど）、再生成が必要です。generateSoloNavMesh はエリア全体を再構築し、タイル型ナビメッシュは影響を受けたタイルのみを再構築します。動く障害物が少数であれば、頻繁な再構築よりも、ナビメッシュに独自のローカルな操舵／衝突回避を追加するほうが、多くの場合、負荷を抑えられます。
• 規約： navcat は OpenGL の規約（右手系、反時計回りの巻き順）に従います。データの規約が異なる場合は、座標を変換して入出力してください。インポートした外部ナビメッシュでは、隣接するポリゴン間で頂点を共有し、インデックスを付ける必要があります。
• 衝突判定とナビメッシュは、同じ形状の地形に合わせてください。 起伏のある地面の下に平らな床を置くのではなく、地形に合わせます（world スキルを参照してください）。そうしないと、エージェントが目に見える丘を突っ切って進みます。
• ナビメッシュは通常の JSON です。生成したナビメッシュをシリアライズすれば、読み込み時の再生成を省略できます。