Game AI

What Is Game AI?

Game AI is not about intelligence — it's about the illusion of intelligence that creates engaging gameplay." — Steve Rabin [1]

Game AI ≠ Academic AI. Academic AI seeks optimal solutions; Game AI seeks fun, believable, and performant behaviour. An opponent that always makes the mathematically correct move is often a worse opponent than one that makes human-ish mistakes at human-ish moments — a perfect chess engine is impressive, but a perfect aim-bot in a shooter is simply no fun to play against. The job of a game AI programmer is closer to a magician's than a mathematician's: produce the appearance of a mind making choices, at a fraction of the compute a real decision process would need, within a frame budget measured in milliseconds rather than seconds.

That difference in goals drives real differences in engineering practice, summarised below. Academic AI can spend minutes of compute per decision because the decision matters more than the clock; game AI shares its CPU budget with rendering, physics, and audio, and typically gets only a slice of a single frame — often under two milliseconds — to decide what forty on-screen agents should do next. Academic AI aims to generalise to problems it has never seen; game AI is usually hand-authored and tuned for the specific level, the specific encounter, the specific player experience the designer wants. And where academic AI values being able to explain a decision, game AI is entirely happy to fake it — if the illusion holds up under play, nobody asks how the trick was done.

Academic AI	Game AI
Optimal/rational	Believable/entertaining
Unlimited compute	Strict budget (1-2ms/frame)
General solutions	Specialised, scripted
Learning offline	Authored behaviours
Explainable	"Magic" is fine

A Spectrum of "AI" in Games

AI" is used loosely enough in games discourse to cover almost anything that isn't the player's own input, and it's worth being precise about where a given technique actually sits, because the term spans a huge range of sophistication — and, more importantly, of what it's actually simulating.

At the simplest end sits scripted behaviour: a fixed sequence of actions with no branching and no awareness of the world beyond a trigger condition. A patrol that walks to point A, waits two seconds, walks to point B, and repeats forever is scripted; so is a boss that plays attack animations 1, 2, 3, 1, 2, 3 regardless of what the player does. Scripted behaviour is cheap, perfectly predictable, and easy to author — its weakness is that predictability curdles into staleness the moment the player learns the pattern, which is usually within a couple of encounters.

One rung up are rules-based, trigger-driven systems — the finite state machine is the classic example, and it's the workhorse of the industry for a reason. An enemy is always in exactly one named state (patrol, alert, chase, attack, flee), and named events push it between states: "player enters line of sight" moves patrol to alert; "lost sight for five seconds" moves alert back to patrol. This is still not reasoning about the world in any deep sense — it is a lookup table dressed as behaviour — but branching on real, sensed conditions makes it feel far more responsive than a fixed script, and it stays cheap enough to run for hundreds of agents at once. Its known failure mode, referenced in this page's closing section, is combinatorial: every new nuance the designer wants ("but flee only if health is low and no ally is nearby and it hasn't fled in the last ten seconds") multiplies the number of transitions, until the state machine becomes harder to reason about than the behaviour it was meant to simplify.

Beyond that lies goal-oriented AI, where instead of authoring every transition by hand, the designer describes the actions available to an agent (their preconditions and effects) and the goals it might want, and lets a planner — often A* search over the space of possible action sequences, as in Goal-Oriented Action Planning — work out a path from the current world state to the goal at run time. This is a genuine, if narrow, form of reasoning: the agent can produce a sequence of actions nobody explicitly scripted, provided that sequence is reachable from the actions it knows about. It is also why F.E.A.R.'s soldiers, who plan tactics like "throw grenade, then flank left, then take cover" from a small vocabulary of primitive actions, still feel sharp nearly two decades after release [3] — see GOAP for the mechanics. Utility-based systems, which score every candidate action by a weighted function of the world state and pick the highest-scoring one each tick, sit in similar territory: still narrow, still authored around a fixed set of considerations, but reactive to combinations of circumstance no finite state machine could practically enumerate.

Past that — and this is speculative territory, not a shipped technique — lies the idea of AI that models something like a mind: an opponent with persistent goals of its own, a model of what the player believes, something resembling memory, anticipation, or even a rudimentary theory of mind about other agents in the world. Language-model-driven NPCs are the closest anything in games has come to this in practice, and even those are, so far, closer to a very fluent script generator wired to a rules layer than to anything that plans or wants in the way a goal-oriented planner does — genuine, persistent, self-directed agency in a shipped game character remains, as far as anyone can point to, not yet demonstrated. Whether it's even desirable is a separate question from whether it's achievable. An opponent that plans tactically, like a GOAP agent, is fun because its behaviour is legible in retrospect — a skilled player can look back at an encounter and see the logic, and use that understanding to get better. An agent that pursued genuinely open-ended goals, remembered grudges across sessions, or negotiated rather than simply executed might make for a more unsettling toy than an enjoyable opponent — game AI's whole value proposition rests on producing an experience that's satisfying to beat, and it isn't obvious that "more mind-like" and "more satisfying to beat" point in the same direction past a certain point. It's a design question as much as a technical one, and the honest answer today is that nobody has shipped enough of it to know.

Steering Behaviours (Reynolds, 1999)

Steering behaviours, introduced by Craig Reynolds in his 1999 GDC talk [2] (and building on his earlier boids flocking work), are the foundation almost every moving game agent sits on. The idea is deliberately simple: rather than plotting an exact trajectory, each behaviour computes a single desired steering force for the current instant, based only on the agent's own position and velocity and a target. seek asks for the fastest straight line toward a target; flee is the same calculation pointed away from a threat. arrive is seek with a deceleration zone bolted on, so the agent slows smoothly as it nears its destination instead of overshooting and snapping back — without it, an agent will visibly oscillate around its target. wander produces convincing, non-repeating idle movement by steering toward a point that drifts randomly around a circle projected out in front of the agent, which is why wandering NPCs don't all walk in the same predictable loop.

The real payoff is combine: because every behaviour reduces to the same small SteeringOutput shape, several can be blended by a weighted average to get compound behaviour for free — an agent that both avoids obstacles and pursues a target does so by summing an avoid force and a seek force, each with its own weight, with no bespoke code for the combination. This composability is exactly why steering behaviours have survived as a technique for over two decades: a handful of a few dozen lines of arithmetic, reused and combined, covers most of the locomotion a game needs. The four implementations below are functionally identical — worth comparing to see how each language's idioms (dataclasses and operator overloading in Python, static methods and structs in C++/C#, records in Java, module functions in Ruby) express the same handful of vector operations.

import math
import random
from dataclasses import dataclass

@dataclass(frozen=True)
class Vec3:
    x: float = 0.0
    y: float = 0.0
    z: float = 0.0

    def __add__(self, o): return Vec3(self.x + o.x, self.y + o.y, self.z + o.z)
    def __sub__(self, o): return Vec3(self.x - o.x, self.y - o.y, self.z - o.z)
    def __mul__(self, s): return Vec3(self.x * s, self.y * s, self.z * s)
    def length(self): return math.sqrt(self.x**2 + self.y**2 + self.z**2)

    def normalised(self):
        l = self.length()
        return self * (1.0 / l) if l > 0 else Vec3()

@dataclass(frozen=True)
class SteeringOutput:
    linear: Vec3 = Vec3()
    angular: float = 0.0

_wander_angle = 0.0

def seek(pos, target, max_speed, velocity):
    desired = (target - pos).normalised() * max_speed
    return SteeringOutput(desired - velocity)

def flee(pos, target, max_speed, velocity):
    desired = (pos - target).normalised() * max_speed
    return SteeringOutput(desired - velocity)

def arrive(pos, target, max_speed, slow_radius, velocity):
    to_target = target - pos
    dist = to_target.length()
    if dist < 0.01:
        return SteeringOutput()
    speed = max_speed * (dist / slow_radius) if dist < slow_radius else max_speed
    desired = to_target.normalised() * speed
    return SteeringOutput(desired - velocity)

def wander(pos, forward, radius, distance, jitter, max_speed, velocity):
    global _wander_angle
    circle_centre = pos + forward * distance
    offset = Vec3(math.cos(_wander_angle) * radius, 0.0,
                  math.sin(_wander_angle) * radius)
    _wander_angle += (random.random() * 2 - 1) * jitter
    return seek(pos + offset, circle_centre + offset, max_speed, velocity)

def combine(behaviours):
    """behaviours: list of (weight, SteeringOutput) pairs."""
    linear, angular, total_weight = Vec3(), 0.0, 0.0
    for weight, b in behaviours:
        linear = linear + b.linear * weight
        angular += b.angular * weight
        total_weight += weight
    if total_weight > 0:
        linear = linear * (1.0 / total_weight)
        angular /= total_weight
    return SteeringOutput(linear, angular)

#include <cmath>
#include <cstdlib>
#include <utility>
#include <vector>

struct Vec3 {
    float x = 0, y = 0, z = 0;
    Vec3 operator+(const Vec3& o) const { return {x + o.x, y + o.y, z + o.z}; }
    Vec3 operator-(const Vec3& o) const { return {x - o.x, y - o.y, z - o.z}; }
    Vec3 operator*(float s) const { return {x * s, y * s, z * s}; }
    float length() const { return std::sqrt(x*x + y*y + z*z); }
    Vec3 normalised() const {
        float l = length();
        return l > 0 ? (*this) * (1.0f / l) : Vec3{};
    }
};

struct SteeringOutput {
    Vec3 linear{};
    float angular = 0;
};

class SteeringBehaviours {
    static inline float wanderAngle = 0.0f;
public:
    static SteeringOutput seek(Vec3 pos, Vec3 target, float maxSpeed, Vec3 velocity) {
        Vec3 desired = (target - pos).normalised() * maxSpeed;
        return {desired - velocity, 0};
    }

    static SteeringOutput flee(Vec3 pos, Vec3 target, float maxSpeed, Vec3 velocity) {
        Vec3 desired = (pos - target).normalised() * maxSpeed;
        return {desired - velocity, 0};
    }

    static SteeringOutput arrive(Vec3 pos, Vec3 target, float maxSpeed,
                                 float slowRadius, Vec3 velocity) {
        Vec3 toTarget = target - pos;
        float dist = toTarget.length();
        if (dist < 0.01f) return {};
        float speed = dist < slowRadius ? maxSpeed * (dist / slowRadius) : maxSpeed;
        Vec3 desired = toTarget.normalised() * speed;
        return {desired - velocity, 0};
    }

    static SteeringOutput wander(Vec3 pos, Vec3 forward, float radius, float distance,
                                 float jitter, float maxSpeed, Vec3 velocity) {
        Vec3 circleCentre = pos + forward * distance;
        Vec3 offset{std::cos(wanderAngle) * radius, 0, std::sin(wanderAngle) * radius};
        wanderAngle += (static_cast<float>(std::rand()) / RAND_MAX * 2 - 1) * jitter;
        return seek(pos + offset, circleCentre + offset, maxSpeed, velocity);
    }

    static SteeringOutput combine(const std::vector<std::pair<float, SteeringOutput>>& behaviours) {
        Vec3 linear{};
        float angular = 0, totalWeight = 0;
        for (const auto& [weight, b] : behaviours) {
            linear = linear + b.linear * weight;
            angular += b.angular * weight;
            totalWeight += weight;
        }
        if (totalWeight > 0) {
            linear = linear * (1.0f / totalWeight);
            angular /= totalWeight;
        }
        return {linear, angular};
    }
};

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

public final class Vec3 {
    public final float x, y, z;

    public Vec3() { this(0, 0, 0); }
    public Vec3(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
    public Vec3(float v) { this(v, v, v); }

    public Vec3 add(Vec3 o) { return new Vec3(x + o.x, y + o.y, z + o.z); }
    public Vec3 sub(Vec3 o) { return new Vec3(x - o.x, y - o.y, z - o.z); }
    public Vec3 mul(float s) { return new Vec3(x * s, y * s, z * s); }
    public Vec3 div(float s) { return new Vec3(x / s, y / s, z / s); }
    public float length() { return (float)Math.sqrt(x*x + y*y + z*z); }
    public Vec3 normalized() { float l = length(); return l &gt; 0 ? div(l) : new Vec3(); }
}

public final class SteeringOutput {
    public final Vec3 linear;
    public final float angular;
    public SteeringOutput() { this(new Vec3(), 0); }
    public SteeringOutput(Vec3 linear, float angular) { this.linear = linear; this.angular = angular; }
}

public class SteeringBehaviors {
    private static final ThreadLocalRandom RNG = ThreadLocalRandom.current();
    private static final ThreadLocal&lt;Float&gt; WANDER_ANGLE = ThreadLocal.withInitial(() -&gt; 0.0f);

    public static SteeringOutput seek(Vec3 pos, Vec3 target, float maxSpeed, Vec3 velocity) {
        Vec3 desired = target.sub(pos).normalized().mul(maxSpeed);
        return new SteeringOutput(desired.sub(velocity), 0);
    }

    public static SteeringOutput flee(Vec3 pos, Vec3 target, float maxSpeed, Vec3 velocity) {
        Vec3 desired = pos.sub(target).normalized().mul(maxSpeed);
        return new SteeringOutput(desired.sub(velocity), 0);
    }

    public static SteeringOutput arrive(Vec3 pos, Vec3 target, float maxSpeed, float slowRadius, Vec3 velocity) {
        Vec3 toTarget = target.sub(pos);
        float dist = toTarget.length();
        if (dist &lt; 0.01f) return new SteeringOutput();
        float speed = (dist &lt; slowRadius) ? maxSpeed * (dist / slowRadius) : maxSpeed;
        Vec3 desired = toTarget.normalized().mul(speed);
        return new SteeringOutput(desired.sub(velocity), 0);
    }

    public static SteeringOutput wander(Vec3 pos, Vec3 forward, float radius, float distance, float jitter, float maxSpeed, Vec3 velocity) {
        float angle = WANDER_ANGLE.get();
        Vec3 circleCenter = pos.add(forward.mul(distance));
        Vec3 offset = new Vec3(
            (float)Math.cos(angle) * radius,
            0,
            (float)Math.sin(angle) * radius
        );
        WANDER_ANGLE.set(angle + (float)(ThreadLocalRandom.current().nextDouble() * 2 - 1) * jitter);
        return seek(pos.add(offset), circleCenter.add(offset), maxSpeed, velocity);
    }

    public static SteeringOutput combine(List&lt;Map.Entry&lt;Float, SteeringOutput&gt;&gt; behaviors) {
        Vec3 linear = new Vec3();
        float angular = 0, totalWeight = 0;
        for (var entry : behaviors) {
            float weight = entry.getKey();
            SteeringOutput b = entry.getValue();
            linear = linear.add(b.linear.mul(weight));
            angular += b.angular * weight;
            totalWeight += weight;
        }
        if (totalWeight &gt; 0) {
            linear = linear.mul(1.0f / totalWeight);
            angular /= totalWeight;
        }
        return new SteeringOutput(linear, angular);
    }
}

using System;
using System.Collections.Generic;

public readonly struct Vec3
{
    public readonly float X, Y, Z;
    public Vec3(float x, float y, float z) { X = x; Y = y; Z = z; }

    public static Vec3 operator +(Vec3 a, Vec3 b) => new(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
    public static Vec3 operator -(Vec3 a, Vec3 b) => new(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
    public static Vec3 operator *(Vec3 a, float s) => new(a.X * s, a.Y * s, a.Z * s);
    public float Length() => MathF.Sqrt(X * X + Y * Y + Z * Z);
    public Vec3 Normalised() { var l = Length(); return l > 0 ? this * (1f / l) : default; }
}

public readonly struct SteeringOutput
{
    public readonly Vec3 Linear;
    public readonly float Angular;
    public SteeringOutput(Vec3 linear, float angular) { Linear = linear; Angular = angular; }
}

public static class SteeringBehaviours
{
    private static readonly Random Rng = new();
    private static float _wanderAngle;

    public static SteeringOutput Seek(Vec3 pos, Vec3 target, float maxSpeed, Vec3 velocity)
    {
        var desired = (target - pos).Normalised() * maxSpeed;
        return new SteeringOutput(desired - velocity, 0);
    }

    public static SteeringOutput Flee(Vec3 pos, Vec3 target, float maxSpeed, Vec3 velocity)
    {
        var desired = (pos - target).Normalised() * maxSpeed;
        return new SteeringOutput(desired - velocity, 0);
    }

    public static SteeringOutput Arrive(Vec3 pos, Vec3 target, float maxSpeed,
                                        float slowRadius, Vec3 velocity)
    {
        var toTarget = target - pos;
        var dist = toTarget.Length();
        if (dist < 0.01f) return default;
        var speed = dist < slowRadius ? maxSpeed * (dist / slowRadius) : maxSpeed;
        var desired = toTarget.Normalised() * speed;
        return new SteeringOutput(desired - velocity, 0);
    }

    public static SteeringOutput Wander(Vec3 pos, Vec3 forward, float radius, float distance,
                                        float jitter, float maxSpeed, Vec3 velocity)
    {
        var circleCentre = pos + forward * distance;
        var offset = new Vec3(MathF.Cos(_wanderAngle) * radius, 0,
                              MathF.Sin(_wanderAngle) * radius);
        _wanderAngle += ((float)Rng.NextDouble() * 2 - 1) * jitter;
        return Seek(pos + offset, circleCentre + offset, maxSpeed, velocity);
    }

    public static SteeringOutput Combine(IEnumerable<(float Weight, SteeringOutput Output)> behaviours)
    {
        var linear = default(Vec3);
        float angular = 0, totalWeight = 0;
        foreach (var (weight, b) in behaviours)
        {
            linear = linear + b.Linear * weight;
            angular += b.Angular * weight;
            totalWeight += weight;
        }
        if (totalWeight > 0)
        {
            linear = linear * (1f / totalWeight);
            angular /= totalWeight;
        }
        return new SteeringOutput(linear, angular);
    }
}

Vec3 = Struct.new(:x, :y, :z) do
  def self.zero
    new(0.0, 0.0, 0.0)
  end

  def +(other)
    Vec3.new(x + other.x, y + other.y, z + other.z)
  end

  def -(other)
    Vec3.new(x - other.x, y - other.y, z - other.z)
  end

  def *(scalar)
    Vec3.new(x * scalar, y * scalar, z * scalar)
  end

  def length
    Math.sqrt(x * x + y * y + z * z)
  end

  def normalised
    l = length
    l > 0 ? self * (1.0 / l) : Vec3.zero
  end
end

SteeringOutput = Struct.new(:linear, :angular) do
  def self.none
    new(Vec3.zero, 0.0)
  end
end

module SteeringBehaviours
  module_function

  def seek(pos, target, max_speed, velocity)
    desired = (target - pos).normalised * max_speed
    SteeringOutput.new(desired - velocity, 0.0)
  end

  def flee(pos, target, max_speed, velocity)
    desired = (pos - target).normalised * max_speed
    SteeringOutput.new(desired - velocity, 0.0)
  end

  def arrive(pos, target, max_speed, slow_radius, velocity)
    to_target = target - pos
    dist = to_target.length
    return SteeringOutput.none if dist < 0.01

    speed = dist < slow_radius ? max_speed * (dist / slow_radius) : max_speed
    desired = to_target.normalised * speed
    SteeringOutput.new(desired - velocity, 0.0)
  end

  def wander(pos, forward, radius, distance, jitter, max_speed, velocity)
    @wander_angle ||= 0.0
    circle_centre = pos + forward * distance
    offset = Vec3.new(Math.cos(@wander_angle) * radius, 0.0,
                      Math.sin(@wander_angle) * radius)
    @wander_angle += (rand * 2 - 1) * jitter
    seek(pos + offset, circle_centre + offset, max_speed, velocity)
  end

  # behaviours: array of [weight, SteeringOutput] pairs
  def combine(behaviours)
    linear = Vec3.zero
    angular = 0.0
    total_weight = 0.0
    behaviours.each do |weight, b|
      linear += b.linear * weight
      angular += b.angular * weight
      total_weight += weight
    end
    if total_weight > 0
      linear *= 1.0 / total_weight
      angular /= total_weight
    end
    SteeringOutput.new(linear, angular)
  end
end

Steering behaviours are reactive and local — they don't know a wall is in the way until the agent is nearly touching it. Getting an agent reliably across a whole level, around obstacles it can't yet see, needs a different structure: a navigation mesh, which carves the walkable area of a level into a set of convex polygons and records which polygons are adjacent to which. That turns "find a route across the level" into a graph search — A* over polygons rather than over a fine grid, which is both cheaper (a level might be a few hundred polygons instead of tens of thousands of grid cells) and produces paths that hug the geometry naturally rather than in awkward grid-aligned steps.

The sketch below deliberately leaves the geometric heavy lifting as placeholders — point_in_poly, poly_distance, and the heuristic all return fixed dummy values — because the point of the example is the search structure itself, not the computational geometry. What matters is the shape: locate_poly answers "which region is this position inside?", find_path runs a textbook A* where the graph's nodes are polygons instead of grid squares, and the flags field on each polygon lets the same mesh serve several kinds of agent — a small enemy might walk through a gap a large one can't, or only a flying agent can cross a chasm — by filtering out neighbours the current agent can't actually traverse. That's also why the algorithm is closer to a lookup than to reasoning: it finds the shortest reachable route through pre-authored geometry, and knows nothing about the level beyond what shape it was baked with.

from dataclasses import dataclass, field
from typing import List, Optional
import heapq

@dataclass
class NavPoly:
    vertices: List[Vec3] = field(default_factory=list)  # CCW order
    neighbors: List[int] = field(default_factory=list)  # Adjacent poly indices
    flags: int = 0    # Walk, jump, climb, water
    area: int = 0     # Ground, road, grass, etc.

@dataclass
class NavMesh:
    polys: List[NavPoly] = field(default_factory=list)
    vertices: List[Vec3] = field(default_factory=list)

    def locate_poly(self, point: Vec3) -&gt; int:
        """Find which polygon contains the point (simplified)."""
        for i, poly in enumerate(self.polys):
            if self._point_in_poly(point, poly):
                return i
        return -1

    def _point_in_poly(self, point: Vec3, poly: NavPoly) -&gt; bool:
        # Simplified 2D point-in-polygon test (assumes flat polys)
        # Real implementation would use proper 3D test
        return True  # Placeholder

    def find_path(self, start: Vec3, end: Vec3, agent_flags: int) -&gt; List[int]:
        start_poly = self.locate_poly(start)
        end_poly = self.locate_poly(end)
        if start_poly &lt; 0 or end_poly &lt; 0:
            return []

        # A* on polygon graph
        @dataclass(order=True)
        class Node:
            f: float
            poly: int = field(compare=False)
            g: float = field(compare=False)
            parent: int = field(compare=False)

        open_set = [Node(0, start_poly, 0.0, -1)]
        closed = {}
        g_scores = {start_poly: 0.0}

        while open_set:
            current = heapq.heappop(open_set)
            if current.poly == end_poly:
                return self._reconstruct_path(closed, current)

            if current.poly in closed:
                continue
            closed[current.poly] = current

            for neighbor in self.polys[current.poly].neighbors:
                # Filter by agent capabilities
                if self.polys[neighbor].flags &amp; agent_flags:
                    continue

                g = current.g + self._poly_distance(current.poly, neighbor)
                if neighbor not in g_scores or g &lt; g_scores[neighbor]:
                    g_scores[neighbor] = g
                    h = self._heuristic(neighbor, end_poly)
                    heapq.heappush(open_set, Node(g + h, neighbor, g, current.poly))

        return []  # No path

    def _poly_distance(self, a: int, b: int) -&gt; float:
        # Distance between polygon centroids
        return 1.0  # Placeholder

    def _heuristic(self, a: int, b: int) -&gt; float:
        return 1.0  # Placeholder

    def _reconstruct_path(self, closed: dict, node) -&gt; List[int]:
        path = [node.poly]
        while node.parent != -1:
            node = closed[node.parent]
            path.append(node.poly)
        return list(reversed(path))

#include <queue>
#include <unordered_map>
#include <vector>

struct NavPoly {
    std::vector<Vec3> vertices;   // CCW order
    std::vector<int> neighbours;  // Adjacent poly indices
    int flags = 0;                // Walk, jump, climb, water
    int area = 0;                 // Ground, road, grass, etc.
};

class NavMesh {
public:
    std::vector<NavPoly> polys;
    std::vector<Vec3> vertices;

    // Find which polygon contains the point (simplified).
    int locatePoly(const Vec3& point) const {
        for (int i = 0; i < static_cast<int>(polys.size()); ++i)
            if (pointInPoly(point, polys[i])) return i;
        return -1;
    }

    std::vector<int> findPath(const Vec3& start, const Vec3& end, int agentFlags) const {
        int startPoly = locatePoly(start);
        int endPoly = locatePoly(end);
        if (startPoly < 0 || endPoly < 0) return {};

        struct Node { float f; int poly; float g; int parent; };
        auto cmp = [](const Node& a, const Node& b) { return a.f > b.f; };
        std::priority_queue<Node, std::vector<Node>, decltype(cmp)> open(cmp);
        std::unordered_map<int, Node> closed;
        std::unordered_map<int, float> gScores;

        open.push({0, startPoly, 0.0f, -1});
        gScores[startPoly] = 0.0f;

        while (!open.empty()) {
            Node current = open.top();
            open.pop();
            if (current.poly == endPoly) return reconstructPath(closed, current);
            if (closed.count(current.poly)) continue;
            closed[current.poly] = current;

            for (int neighbour : polys[current.poly].neighbours) {
                // Filter by agent capabilities
                if (polys[neighbour].flags & agentFlags) continue;

                float g = current.g + polyDistance(current.poly, neighbour);
                auto it = gScores.find(neighbour);
                if (it == gScores.end() || g < it->second) {
                    gScores[neighbour] = g;
                    float h = heuristic(neighbour, endPoly);
                    open.push({g + h, neighbour, g, current.poly});
                }
            }
        }
        return {};  // No path
    }

private:
    bool pointInPoly(const Vec3&, const NavPoly&) const { return true; }  // Placeholder
    float polyDistance(int, int) const { return 1.0f; }                   // Placeholder
    float heuristic(int, int) const { return 1.0f; }                      // Placeholder

    std::vector<int> reconstructPath(const std::unordered_map<int, Node>& closed, Node node) const {
        std::vector<int> path{node.poly};
        while (node.parent != -1) {
            node = closed.at(node.parent);
            path.push_back(node.poly);
        }
        return {path.rbegin(), path.rend()};
    }
};

import java.util.*;

public class NavPoly {
    public List<Vec3> vertices = new ArrayList<>();   // CCW order
    public List<Integer> neighbours = new ArrayList<>(); // Adjacent poly indices
    public int flags = 0;   // Walk, jump, climb, water
    public int area = 0;    // Ground, road, grass, etc.
}

public class NavMesh {
    public List<NavPoly> polys = new ArrayList<>();
    public List<Vec3> vertices = new ArrayList<>();

    private record Node(float f, int poly, float g, int parent) {}

    /** Find which polygon contains the point (simplified). */
    public int locatePoly(Vec3 point) {
        for (int i = 0; i < polys.size(); i++)
            if (pointInPoly(point, polys.get(i))) return i;
        return -1;
    }

    public List<Integer> findPath(Vec3 start, Vec3 end, int agentFlags) {
        int startPoly = locatePoly(start);
        int endPoly = locatePoly(end);
        if (startPoly < 0 || endPoly < 0) return List.of();

        PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparingDouble(Node::f));
        Map<Integer, Node> closed = new HashMap<>();
        Map<Integer, Float> gScores = new HashMap<>();

        open.add(new Node(0, startPoly, 0f, -1));
        gScores.put(startPoly, 0f);

        while (!open.isEmpty()) {
            Node current = open.poll();
            if (current.poly() == endPoly) return reconstructPath(closed, current);
            if (closed.containsKey(current.poly())) continue;
            closed.put(current.poly(), current);

            for (int neighbour : polys.get(current.poly()).neighbours) {
                // Filter by agent capabilities
                if ((polys.get(neighbour).flags & agentFlags) != 0) continue;

                float g = current.g() + polyDistance(current.poly(), neighbour);
                Float best = gScores.get(neighbour);
                if (best == null || g < best) {
                    gScores.put(neighbour, g);
                    float h = heuristic(neighbour, endPoly);
                    open.add(new Node(g + h, neighbour, g, current.poly()));
                }
            }
        }
        return List.of();  // No path
    }

    private boolean pointInPoly(Vec3 point, NavPoly poly) { return true; }  // Placeholder
    private float polyDistance(int a, int b) { return 1f; }                 // Placeholder
    private float heuristic(int a, int b) { return 1f; }                    // Placeholder

    private List<Integer> reconstructPath(Map<Integer, Node> closed, Node node) {
        List<Integer> path = new ArrayList<>(List.of(node.poly()));
        while (node.parent() != -1) {
            node = closed.get(node.parent());
            path.add(node.poly());
        }
        Collections.reverse(path);
        return path;
    }
}

using System.Collections.Generic;

public class NavPoly
{
    public List<Vec3> Vertices { get; } = new();     // CCW order
    public List<int> Neighbours { get; } = new();    // Adjacent poly indices
    public int Flags { get; set; }                   // Walk, jump, climb, water
    public int Area { get; set; }                    // Ground, road, grass, etc.
}

public class NavMesh
{
    public List<NavPoly> Polys { get; } = new();
    public List<Vec3> Vertices { get; } = new();

    private readonly record struct Node(float F, int Poly, float G, int Parent);

    // Find which polygon contains the point (simplified).
    public int LocatePoly(Vec3 point)
    {
        for (var i = 0; i < Polys.Count; i++)
            if (PointInPoly(point, Polys[i])) return i;
        return -1;
    }

    public List<int> FindPath(Vec3 start, Vec3 end, int agentFlags)
    {
        var startPoly = LocatePoly(start);
        var endPoly = LocatePoly(end);
        if (startPoly < 0 || endPoly < 0) return new List<int>();

        var open = new PriorityQueue<Node, float>();
        var closed = new Dictionary<int, Node>();
        var gScores = new Dictionary<int, float> { [startPoly] = 0f };

        open.Enqueue(new Node(0, startPoly, 0f, -1), 0);

        while (open.Count > 0)
        {
            var current = open.Dequeue();
            if (current.Poly == endPoly) return ReconstructPath(closed, current);
            if (closed.ContainsKey(current.Poly)) continue;
            closed[current.Poly] = current;

            foreach (var neighbour in Polys[current.Poly].Neighbours)
            {
                // Filter by agent capabilities
                if ((Polys[neighbour].Flags & agentFlags) != 0) continue;

                var g = current.G + PolyDistance(current.Poly, neighbour);
                if (!gScores.TryGetValue(neighbour, out var best) || g < best)
                {
                    gScores[neighbour] = g;
                    var h = Heuristic(neighbour, endPoly);
                    open.Enqueue(new Node(g + h, neighbour, g, current.Poly), g + h);
                }
            }
        }
        return new List<int>();  // No path
    }

    private bool PointInPoly(Vec3 point, NavPoly poly) => true;  // Placeholder
    private float PolyDistance(int a, int b) => 1f;              // Placeholder
    private float Heuristic(int a, int b) => 1f;                 // Placeholder

    private List<int> ReconstructPath(Dictionary<int, Node> closed, Node node)
    {
        var path = new List<int> { node.Poly };
        while (node.Parent != -1)
        {
            node = closed[node.Parent];
            path.Add(node.Poly);
        }
        path.Reverse();
        return path;
    }
}

NavPoly = Struct.new(:vertices, :neighbours, :flags, :area) do
  def initialize(vertices: [], neighbours: [], flags: 0, area: 0)
    super(vertices, neighbours, flags, area)
  end
end

Node = Struct.new(:f, :poly, :g, :parent)

class NavMesh
  attr_reader :polys, :vertices

  def initialize
    @polys = []
    @vertices = []
  end

  # Find which polygon contains the point (simplified).
  def locate_poly(point)
    polys.each_with_index do |poly, i|
      return i if point_in_poly?(point, poly)
    end
    -1
  end

  def find_path(start, finish, agent_flags)
    start_poly = locate_poly(start)
    end_poly = locate_poly(finish)
    return [] if start_poly.negative? || end_poly.negative?

    # A* on the polygon graph (open list kept sorted by f; a heap
    # such as the pqueue gem would be the production choice)
    open_set = [Node.new(0.0, start_poly, 0.0, -1)]
    closed = {}
    g_scores = { start_poly => 0.0 }

    until open_set.empty?
      current = open_set.min_by(&:f)
      open_set.delete(current)

      return reconstruct_path(closed, current) if current.poly == end_poly
      next if closed.key?(current.poly)

      closed[current.poly] = current

      polys[current.poly].neighbours.each do |neighbour|
        # Filter by agent capabilities
        next unless (polys[neighbour].flags & agent_flags).zero?

        g = current.g + poly_distance(current.poly, neighbour)
        if !g_scores.key?(neighbour) || g < g_scores[neighbour]
          g_scores[neighbour] = g
          h = heuristic(neighbour, end_poly)
          open_set << Node.new(g + h, neighbour, g, current.poly)
        end
      end
    end

    []  # No path
  end

  private

  def point_in_poly?(_point, _poly) = true  # Placeholder
  def poly_distance(_a, _b) = 1.0           # Placeholder
  def heuristic(_a, _b) = 1.0               # Placeholder

  def reconstruct_path(closed, node)
    path = [node.poly]
    while node.parent != -1
      node = closed[node.parent]
      path << node.poly
    end
    path.reverse
  end
end

Where Next: From Reacting to Planning

Steering and pathfinding make agents move convincingly; the next step is making them decide convincingly. When state machines start sprouting transitions faster than you can test them, it is time to let the agent plan its own action sequences: see Goal-Oriented Action Planning (GOAP), the technique behind the AI of F.E.A.R.

References

Rabin, S. (2017). "The Illusion of Intelligence." In Game AI Pro 3: Collected Wisdom of Game AI Professionals. CRC Press. https://www.gameaipro.com/GameAIPro3/GameAIPro3_Chapter01_The_Illusion_of_Intelligence.pdf
Reynolds, C.W. (1999). "Steering Behaviors For Autonomous Characters." Game Developers Conference 1999 Proceedings, 763–782. https://www.red3d.com/cwr/papers/1999/gdc99steer.html
Orkin, J. (2006). "Three States and a Plan: The A.I. of F.E.A.R." Game Developers Conference 2006. https://www.gamedevs.org/uploads/three-states-plan-ai-of-fear.pdf