Path Planning – Introduction & Grid Lattice

Motivation for Path Planning

Basic movement behaviours (e.g., Seek) get an agent to a target position only if nothing blocks the route.
Games inevitably contain static or dynamic obstacles (walls, pits, other units, terrain height, etc.).
Pure steering can attempt to hug obstacles by following the gradient of an avoidance field, but:
- The agent may orbit an obstacle endlessly.
- It can become trapped at local minima/maxima of the potential field.
Therefore we require an explicit search through alternative routes until a viable path is located.

Obstacles, Local Minima & the Need for Search

Gradient-following behaviours fail when the local gradient provides no improving direction.
A planner must remember which places have already been tried and systematically explore new ones.
Formal solution: represent the movement problem as a graph search.

Graph Theory Foundations

A graph $G$ is defined as $G = {N,E}$ where:
- $N$ – the set of nodes (a.k.a. vertices, states).
- $E$ – the set of edges (connections or operators between nodes).
Edges may be weighted; weight often stores traversal cost (distance, time, danger, resource usage, etc.).
- Slide example shows a weighted graph with edge costs: $0.6,\;1.2,\;2.1,\;0.35,\;\ldots$
Common graph categories used in AI:
- Directed acyclic graph (DAG)
- Directed cyclic graph (digraph)
- Undirected graph
- Binary tree (specialised directed acyclic)

Game-Centric Graph Examples

Risk world-map: continents = nodes, adjacency = edges, each continent labelled with reinforcement value (Asia 7, Europe 5, etc.).
Civilization tech tree: gigantic dependency graph where each technology node unlocks new structures/units (e.g., Pottery → Granary → Code of Laws → Courthouse; Magnetism → Frigate Unit; Nuclear Fission → Nuclear Power → Fusion Power). Illustrates:
- Directed edges (prerequisite relationships).
- Non-spatial graphs still benefit from AI search.

Uniform Spatial Graphs & Grid Overlay

Many 2-D adventure or RPG titles (e.g., Zelda) overlay a uniform lattice on top of the map geometry; every cell is an implicit node.
Important design question: "Is a simple rectangular grid sufficient to capture the true geometry of rooms & corridors?"
Sometimes additional doorway nodes or portal edges improve fidelity.

Classical Planning Terminology

State: a distinct configuration of the world. In navigation, state ≈ "agent at position X".
Operator: an action converting one state to another (e.g., step north, teleport, open door).
Goal state: any state satisfying the victory predicate (agent is at destination, perhaps with extra conditions such as still alive).

Path-Planning Workflow in Games

1 • Create a graph data structure. If world is continuous, discretise first.
2 • Snap (quantise) the agent’s current position and the goal’s position to graph nodes.
3 • Run a search algorithm to produce an ordered list of nodes (the path).
4 • Optionally post-process (smoothing, string-pulling) to look natural.
5 • Move the in-game entity along the smoothed path until the goal is reached.

Quality & Complexity Metrics

Path planners are assessed on:

Completeness – guarantees to find a solution if one exists.
Optimality – returns the best path (minimum cost) if found.
Time complexity – worst-case CPU steps.
Space complexity – peak memory footprint.

Search Strategy Categories

Blind / uninformed search – only knows the goal test (e.g., DFS, BFS). No domain knowledge.
Heuristic / informed search – leverages approximations like Euclidean distance, terrain penalty, crowd density, etc., to guide expansion.
- Video games provide prodigious heuristic information (height map, nav-mesh area costs, scripted hints).

Depth-First Search (DFS)

Always expands the deepest uncovered node first.
Pros: low memory ( $O(b\,d)$ where $b$ = branching factor, $d$ = depth).
Cons: can become lost down an endless branch; first path found may be highly sub-optimal.
Not recommended as final path finder but useful for generating mazes or exploring all reachable nodes offline.

Breadth-First Search (BFS)

Expands root, then all children, then grandchildren, etc.
Finds optimal path only if all edge weights are equal or unweighted.
Memory heavy: needs to store frontier of width $O(b^d)$ .

Real-World Demonstrations & Pitfalls

YouTube references show:
- "Pathfinding" (general demonstration) – classic A* visualiser.
- Sim City traffic pathfinding (cars choose roads based on cost).
- Half-Life 2 navigation graph mis-alignments (waypoints don’t match new prop layout).
- theHunter: Call of the Wild – crowd navigation in outdoor terrain.
Lesson: a correct path on the abstract graph may be impossible in the physics engine if geometry changed or was authored incorrectly.

Tile-Based Games

Many strategy/RPG titles (Jagged Alliance, X-Com, Mechwarrior Tactics, Anno 1800) already are grids, so graph = map.
Grid properties:
- Square cells (4-way or 8-way connectivity) or hex cells (6-way).
- Often one entity per cell; each cell stores terrain type (traversable, forest, water, etc.).

Discretisation of Continuous Space

Generation steps:

Identify obstacle boundaries and terrain gradients (uphill, downhill, water depth).
Convert continuous positions to integer cell indices (quantisation).
Mark cells obstructed, slow, dangerous, etc.

Grid lattice slide shows:

Yellow/orange polygons = static obstacles.
Black square = a single grid cell.
Red circles/segments = point or edge intersection tests.

Point Containment (Axis-Aligned Cells)

Because cells are axis-aligned rectangles, inside test simplifies to range checks:
$\text{inside} \;\Leftrightarrow\; (min<em>x < x < max</em>x) \wedge (min<em>y < y < max</em>y)$
Using integer coordinates multiplied by 1000 ⇒ shrinking bounds by 1 maintains robustness without visible loss.

Designer-Friendly Shrinking

Shrink traversability test by 1 unit so that obstacle polygons flush with cell edges do not incorrectly mark adjacent cells as blocked.

Validity Between Adjacent Cells

Validity: For any start point in cell $A$ and any end point in adjacent cell $B$ , can an agent move in a straight line without collision?
- If YES ⇒ edge is valid.
- If partial blockage ⇒ may treat as weighted edge or restrict depending on gameplay needs.

When the Agent Is "Off-Grid"

Options:

Short local steering using physics (ray-cast, slide) to regain the nearest valid cell.
Store metadata on blocked cells describing which border segments are passable.
Teleport (cheat) if completely stuck and player can’t see.

Smoothing, String-Pulling & Steering

Raw grid path looks stair-stepped.
"String pulling" simplifies by iteratively testing visibility between non-adjacent nodes and removing unnecessary intermediate nodes.
Runtime steering layer (Seek + Avoid) can blend continuous orientation with discrete waypoints.
May add invisible colliders (e.g., around pits) to steer characters away even if nav path is straight.

Efficiency on Large Grids

Node count on an $N \times N$ grid: $N^2$ .
4-way edge count:
$E_4 = ((N-1)\times N) \times 2$ (horizontal + vertical, each bidirectional).
8-way adds diagonals:
$E_8 = ((N-1)\times(N-1)) \times 2$ .
Nodes and edges can be generated lazily (on-the-fly) to cut memory.
For extremely sparse maps, a grid is wasteful; alternatives include waypoint graphs or nav-meshes.

Grid Lattice Pros & Cons

Pros

Conceptually simple, easy to debug and visualise.
Perfect fit for inherently discrete games.
Temporary obstacles (other units) handled by toggling cell costs.
Supports multi-unit path planning (e.g., flow fields for RTS).
Implicit representation – no need to pre-store every node.

Cons

Poor fit for wide-open continuous worlds (search space explodes).
Memory/time cost proportional to area, not complexity of obstacles.
Paths are longer (Manhattan detours, stair-step artefacts).

Reference Mentioned in Slides

Davis, I. L., “Warp Speed: Path Planning for Star Trek: Armada,” AAAI Spring Symposium on AIIDE, 2000.
Ian Millington & John Funge, Artificial Intelligence for Games (multiple figure citations).