game-ai

ゲーム AI：意思決定、ステアリング、経路探索

互いに分離できる 3 つのレイヤーから、説得力のある NPC の動作を構築します。意思決定（何をするか）、ステアリング（どう移動するか）、経路（マップ内をどう進むか）です。これらは分離しておきます。ビヘイビアツリーが目標を選び、経路探索がウェイポイントを生成し、ステアリングがそれに従います。このスキルではエンジンに依存しないアルゴリズムを解説します。以下の関連スキルを使って、使用するエンジンに組み込んでください。

使用する場面

• 敵や NPC のロジック（パトロール、追跡／逃走、警備状態、集団移動、「プレイヤーへの経路を探す」など）を実装するときに使用します。
• FSM（明確な状態が少数の場合）、ビヘイビアツリー（優先順位のある反応的な動作が多数ある場合）、ステアリング（滑らかな局所移動）のどれを選ぶか判断するときに使用します。
• 経路探索（グリッド／グラフ上の A*、またはエンジンのナビメッシュエージェントの操作）を組み込むときに使用します。

使用しない場面： エンジン固有のナビメッシュ／エージェント API やベイク処理には、unity-navmesh、unreal-behavior-trees、または Godot の NavigationAgent2D/3D を使用してください（該当するエンジンのスキルを参照）。移動や衝突の感触を調整するには、physics-tuning を使用してください。レーンに沿ってウェーブを出現させるには、ジャンルスキルの tower-defense を参照してください。

基本的なワークフロー

1. 複雑さに応じて意思決定モデルを選びます。 明確な遷移を持つ状態が 2～5 個 → FSM。動作、優先順位、中断、再利用が多数 → ビヘイビアツリー。「各選択肢をどれくらい強く望むか」を連続的に扱う → 効用スコアリング。
2. 意思決定と移動を分離します。 意思決定レイヤーは 意図（目標位置、アクション）を出力します。ステアリングまたは経路探索が、意図を移動に変換します。
3. 適切なグラフ上で経路を探索します。 グリッドタイル、ウェイポイントグラフ、またはベイク済みナビメッシュを使います。ノードが少ないほど A* は高速になります。3D ではエンジンのナビメッシュを、タイルゲームではグリッド上の A* を優先してください。
4. 目標へまっすぐ進むのではなく、経路に沿ってステアリングします。次のウェイポイントに従い、近づいたら次へ進むことで、エージェントが角を回れるようにします。
5. 経路の再計算は必要最小限にします。 毎フレームではなく、タイマーに基づくか、目標がタイル 1 つ分移動したときに経路を探索します。経路をキャッシュし、ウェイポイントのインデックスだけを進めます。
6. 観察して確認します。 エージェントを見て、目標に到達するか、角で詰まるか、状態間で振動するかを確認します。調整中は経路と現在の状態を画面に描画します。

パターン

1. 有限ステートマシン（1 つの状態オブジェクト、明示的な遷移）

# Each state is a small object with enter/update/exit. The machine owns "current".
class_name State
func enter(agent): pass
func update(agent, dt) -> State: return null   # return a new state to transition
func exit(agent): pass

# --- Chase state: returns Patrol when the player escapes sight range ---
class Chase extends State:
    func update(agent, dt) -> State:
        if not agent.can_see(agent.target):
            return Patrol.new()                 # transition by returning next state
        agent.move_toward(agent.target.position, dt)
        return null                             # null = stay in this state

# --- Driver: call once per frame ---
func tick(dt):
    var next = current.update(self, dt)
    if next != null:
        current.exit(self); next.enter(self); current = next

遷移ロジックは状態の内部（またはテーブル内）に置きます。if フラグを際限なく増やして実装しないでください。1 つの状態が 1 つの動作を担うことが、FSM の読みやすさを保ちます。

2. ビヘイビアツリーのティック（複合ノードはステータスを返す）

# A node's tick() returns SUCCESS, FAILURE, or RUNNING (still working this frame).
enum Status { SUCCESS, FAILURE, RUNNING }

# Sequence: run children in order; stop at the first non-SUCCESS (logical AND).
func sequence_tick(children, agent, dt) -> int:
    for child in children:
        var s = child.tick(agent, dt)
        if s != Status.SUCCESS:
            return s                 # FAILURE or RUNNING short-circuits the sequence
    return Status.SUCCESS

# Selector: try children until one succeeds or is RUNNING (logical OR / fallback).
func selector_tick(children, agent, dt) -> int:
    for child in children:
        var s = child.tick(agent, dt)
        if s != Status.FAILURE:
            return s                 # SUCCESS or RUNNING stops the search
    return Status.FAILURE

警備 AI は上から順に評価します。Selector[ Sequence[CanSeePlayer?, Chase], Patrol ] — プレイヤーが見えていれば追跡し、そうでなければパトロールします。リーフノード、デコレーター（Inverter、Cooldown）、ブラックボードについては、references/behavior-trees.md を参照してください。

3. ステアリング：シークと到着（滑らかで、フレームレートに依存しない）

# Seek: accelerate toward a target at full speed. Steering = desired - current.
func seek(pos, vel, target, max_speed, max_force) -> Vector2:
    var desired = (target - pos).normalized() * max_speed
    return (desired - vel).limit_length(max_force)   # a force, not a teleport

# Arrive: like seek, but ramp speed down inside slow_radius so it stops cleanly.
func arrive(pos, vel, target, max_speed, max_force, slow_radius) -> Vector2:
    var offset = target - pos
    var dist = offset.length()
    if dist < 0.001: return -vel                      # already there: kill drift
    var ramped = max_speed * min(dist / slow_radius, 1.0)
    var desired = offset / dist * ramped
    return (desired - vel).limit_length(max_force)

# Per frame: vel += steering * dt; pos += vel * dt   (always scale by dt)

4. A* のヒューリスティックは過大評価してはいけません（そうしないと最短経路が得られなくなります）

# Match the heuristic to the movement. An ADMISSIBLE heuristic (never larger
# than the true remaining cost) keeps A* optimal.
def heuristic(a, b):
    dx, dy = abs(a.x - b.x), abs(a.y - b.y)
    # return dx + dy             # Manhattan: 4-direction grids (no diagonals)
    return (dx + dy) + (1.414 - 2) * min(dx, dy)   # octile: 8-direction grids
# f(n) = g(n) + h(n): g = cost from start, h = heuristic to goal.
# Overestimating h is faster but no longer guarantees the shortest path.

A* のループ全体（優先度付きキュー、came_from による経路の再構築、グリッドとウェイポイントグラフ）については、references/pathfinding.md を参照してください。

落とし穴

• 毎フレームのパスファインディングはフレームレートを大幅に低下させます。タイマーで再計算するか、ターゲットが新しいタイルに移動したときだけ再計算し、それ以外の間はキャッシュされたウェイポイントに従います。
• 次のウェイポイントではなく、ゴールへ直進すると、エージェントは壁や角に沿って進んでしまいます。パスに従い、半径内に入ったらウェイポイントを次へ進めます。
• 許容的でない A* ヒューリスティック（例：ユークリッド距離を大きくスケーリングしたもの、または斜め移動可能なグリッドでのマンハッタン距離）を使うと、探索は速くなりますが、最短ではないパスが返されます。許可されている移動に合ったヒューリスティックを選びます。
• 複数フレームにわたるアクション（歩行やアニメーションの再生など）で、RUNNING を返さないビヘイビアツリーのリーフがあると、ツリーはティックごとにアクションを再開します。アクションが完了するまで RUNNING を返します。
• FSM の遷移がスパゲッティ化すること：あらゆる場所に if state == ... チェックを散在させると、FSM が防ぐはずの混乱を再び招きます。遷移はステート内にまとめます。
• 視線判定やスタック判定がないと、エージェントは延々と壁に向かって進み続けます。タイムアウトを追加し、パスの再探索やステート変更を強制します。

参考資料

• references/pathfinding.md — A* の全体像（優先度付きキュー、パスの再構築）、グリッドとウェイポイントのグラフ、エンジンのナビメッシュに任せるタイミング。
• references/behavior-trees.md — ノードの分類、リーフ／デコレーターの実装、ブラックボード、FSM と BT の選び方。

関連スキル

• unity-navmesh、unreal-behavior-trees — エンジン固有の AI／ナビゲーション API。
• physics-tuning — 移動、衝突応答、エージェントの半径。
• procedural-gen — AI が移動するグラフ／レベルの生成。
• tower-defense、fps-shooter — このスキルを組み合わせて使うジャンル。