Game Development Game AI Syllabus

Give the two most common admissible heuristics used on a grid, and when each applies.

Manhattan distance $h = |x_1 - x_2| + |y_1 - y_2|$ for 4-directional movement, and Euclidean distance $h = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$ (or Chebyshev/octile) for movement allowing diagonals.

What does A* reduce to when the heuristic is $h(n) = 0$ for all nodes?

It reduces to Dijkstra's algorithm — an uninformed uniform-cost search that expands nodes purely by accumulated path cost $g(n)$.

What problem does Dijkstra's algorithm solve and what is its key non-negativity requirement?

It finds shortest paths from a single source to all other nodes in a weighted graph; it requires all edge weights to be non-negative.

What is the time complexity of Dijkstra's algorithm using a binary min-heap (priority queue)?

$O((V + E)\log V)$, where $V$ is the number of vertices and $E$ the number of edges.

Compare A* and Dijkstra in terms of nodes expanded and use case.

Dijkstra explores uniformly in all directions (more nodes) and finds paths to all targets; A* uses a goal-directed heuristic to expand far fewer nodes toward a single goal, making it faster when one destination is known.

What is a Navigation Mesh (NavMesh)?

A data structure representing the walkable surface of a game world as a set of convex polygons (cells); agents can move in a straight line within any cell, and pathfinding is done over the graph of adjacent polygons.

Why are NavMeshes generally preferred over uniform grids or waypoint graphs for pathfinding?

They cover open areas with far fewer, larger convex polygons (less memory, fewer search nodes), represent walkable space accurately, and allow smooth any-angle movement instead of constraining agents to grid cells or fixed waypoints.

Why must the polygons (cells) of a navigation mesh be convex?

Convexity guarantees that a straight line between any two points inside the same polygon stays within the walkable area, so an agent can cross a cell directly without hitting an obstacle.

What is path smoothing, and why is it needed after grid/NavMesh pathfinding?

Path smoothing removes unnecessary intermediate waypoints and jagged turns from a raw computed path to produce a more natural, direct route; it is needed because grid A* paths are blocky/zig-zagged and follow cell boundaries.

Describe the "string-pulling" (funnel) idea used in path smoothing.

Treat the corridor of adjacent portals as a funnel and pull the path taut like a string, so it hugs inside corners; the funnel algorithm produces the shortest turning path through a sequence of NavMesh portals.

What is a simple line-of-sight (raycast) path smoothing technique?

Starting from a node, cast a ray to the farthest subsequent waypoint that is still directly visible (unobstructed), skip the intermediate nodes, and repeat — reducing the path to the minimal set of turning points.

What is local avoidance (a.k.a. collision avoidance) in movement AI?

A reactive, short-horizon technique where an agent adjusts its steering in real time to avoid colliding with dynamic obstacles or other moving agents, complementing the global path from pathfinding.

What is Reciprocal Velocity Obstacles (RVO/ORCA), a common local-avoidance method?

A velocity-space technique where each agent chooses a new velocity outside the set of velocities that would lead to collision, assuming other agents share the avoidance effort reciprocally, yielding smooth oscillation-free crowd movement.

In Reynolds' steering framework, what is the Seek behavior and its desired velocity?

Seek steers an agent toward a static target position; the desired velocity points from the agent to the target at maximum speed: $\vec{v}_{desired} = \hat{d}\, v_{max}$ where $\hat{d}$ is the unit vector toward the target.

How is the steering force computed from a desired velocity in Reynolds' model?

$\vec{f}_{steer} = \vec{v}_{desired} - \vec{v}_{current}$, typically truncated to a maximum steering force; this force is applied to the velocity each frame.

What is the Flee behavior and how does its desired velocity relate to Seek?

Flee steers the agent directly away from a target; its desired velocity is the negation of Seek's: $\vec{v}_{desired} = -\hat{d}\, v_{max}$, pointing from the target toward the agent at max speed.

What is the Arrival behavior, and how does it differ from Seek?

Arrival seeks a target but decelerates within a defined slowing (braking) radius so the agent smoothly stops at the target instead of overshooting, unlike Seek which approaches at full speed.

Give the desired-speed formula used by Arrival inside the slowing radius.

$v_{desired} = v_{max}\,\dfrac{\text{distance}}{r_{slow}}$ (clamped to $v_{max}$), so speed scales linearly with distance and reaches zero at the target; $r_{slow}$ is the slowing radius.

What is the Departure behavior in steering AI?

The opposite of Arrival: the agent flees a target but with speed that increases as it gets closer to the target (strongest repulsion near the target) and diminishes with distance, giving a smooth push-away that fades with range.

How does the Pursuit behavior improve on plain Seek when chasing a moving target?

Pursuit predicts the target's future position and seeks that predicted point rather than its current position, intercepting the target instead of trailing behind it.

Give a common formula for the predicted interception point used in Pursuit.

$\vec{p}_{predict} = \vec{p}_{target} + \vec{v}_{target}\, T$, where the prediction time is often $T = \dfrac{\lVert \vec{p}_{target} - \vec{p}_{agent} \rVert}{v_{max}}$ (distance divided by pursuer's max speed); the agent then seeks $\vec{p}_{predict}$.

What is the Evasion behavior and how does it relate to Pursuit?

Evasion is the inverse of Pursuit: the agent predicts the pursuer's future position and flees from that predicted point rather than the pursuer's current position, to escape more effectively.

What is the Wander steering behavior meant to produce?

Aimless yet smooth, non-jittery random movement — the agent appears to roam naturally rather than jerk randomly each frame.

Describe the classic circle-based method for implementing Wander.

Project a circle ahead of the agent, place a target on the circle's circumference, and each frame perturb that target's angle by a small random amount (a random walk on the circle); then seek that point. The small per-frame jitter with forward projection yields smooth wandering.

What is the Obstacle Avoidance steering behavior (as distinct from local/agent avoidance)?

A behavior that avoids static obstacles by projecting a detection box or feelers ahead of the agent along its velocity, detecting the nearest obstacle in that path, and generating a lateral (sideways) steering force to steer around it.

How does Obstacle Avoidance differ from Flee?

Flee moves directly away from a point regardless of heading, whereas Obstacle Avoidance only reacts to obstacles lying ahead in the agent's path (using a look-ahead probe) and steers laterally to slip past them while continuing forward.

What is the Path Following steering behavior?

A behavior that makes an agent travel along a predefined path (sequence of waypoints or a spline), by predicting its future position, finding the nearest point on the path, and seeking a target slightly ahead along the path if it strays outside a path radius.

In Path Following, what determines whether a corrective steering force is applied?

The agent projects its future position and measures its distance to the path's centerline; if that distance exceeds the path radius (tube width), it seeks a target a bit further along the path to get back on it, otherwise it continues unchanged.

How can multiple steering behaviors be combined for complex movement, and what are the two main methods?

By combining their steering forces: weighted (linear) sum — add each behavior's force scaled by a weight — or prioritized/blended arbitration where higher-priority behaviors (e.g., collision avoidance) can dominate or truncate lower-priority ones.

Compare FSMs, Behavior Trees, and Utility Systems as decision-making techniques.

FSMs are simple and fast but suffer state/transition explosion; Behavior Trees are modular, hierarchical, and reusable, scaling better for complex reactive logic; Utility Systems give smooth, context-weighted, continuous decisions but are harder to debug and tune. Choice depends on complexity and desired nuance.