COMP 3200 - Intro to Artificial Intelligence - Lecture 06 - Grid Representations and Vector Fields

Overview

Dave Churchill explains how grid representations trade spatial precision for simpler storage, fast lookups, and efficient pathfinding, using examples from StarCraft, Dragon Age, Unity navigation meshes, and game-world movement. He develops vector fields from breadth-first-search distance maps to route many entities toward one goal, then covers grid limitations, influence maps, and queue and visited-state optimizations.

Key takeaways

A grid representation makes obstacle checks a constant-time array lookup, but smaller cells increase the number of pathfinding states quadratically in two dimensions.
StarCraft II illustrates why one environment may need multiple spatial resolutions: 32-by-32-pixel build tiles, 8-by-8-pixel walk tiles, and pixel-level collision checks.
For many entities moving to one destination, BFS can build a distance map once and each cell can point to a lower-distance neighbor, creating a reusable vector field.
A distance-map value of -1 can serve both as an unreachable marker and as an unvisited marker during BFS, eliminating the need for a separate closed-list structure.
Grid paths can support continuous-looking movement: convert cell paths to unobstructed waypoints, remove unnecessary turns, and apply steering or smoothing.
Naive grids can be costly for large or sparse worlds; a 1,000-by-1,000 map has one million cells, so hierarchical or sparse representations may be preferable.

Chapters

0:00 Why Space Representation Shapes Pathfinding

A space representation determines how locations and movement actions are modeled, and which pathfinding algorithms apply.
A one-meter grid would be impractical for giving human-readable directions across Newfoundland; a graph of towns and roads is more suitable.
The same grid techniques can apply to games, robotics, and simulations.

3:36 Choosing a Representation: Precision, Memory, and Change

Representation decisions involve localization, construction cost, memory, pathfinding time, and how easily obstacles or road closures can be updated.
Arbitrary-precision positions allow flexible movement but can imply infinitely many possible actions, making search impractical without discretization.
Grid movement usually limits actions to adjacent cells, while graph representations can connect meaningful locations such as towns.

4:36 From Grid Cells to Convex Polygons and Navigation Meshes

Convex polygons support hierarchical pathfinding: search between polygons first, then travel directly within a polygon because any two points inside are mutually visible.
StarCraft II uses a triangular environment representation for pathfinding; some algorithms specifically require triangular meshes.
Unity navigation meshes describe regions where characters may walk and can be represented as grids or more general graphs.

11:23 Why Games Use Grids Under the Hood

A grid abstracts the world into equally sized cells that can be stored in a 2D array, simplifying visualization and computation.
StarCraft uses different spatial resolutions for different tasks: 32-by-32-pixel build tiles, 8-by-8-pixel walk tiles, and pixel-level unit collision boxes.
Grids can represent height-map terrain as well as flat surfaces, provided the environment has no overhangs.

17:17 Mapping World Coordinates to Square, Hex, and Triangle Grids

For equal-sized square cells, convert a world coordinate to a cell by dividing each coordinate by the grid-cell size and taking integer indices.
Chess and checkers already define positions on a grid, while Civilization-style hex maps can still use 2D arrays internally.
Grid shape determines available neighbors and actions; triangular and hexagonal grids do not use the same adjacency pattern as square grids.

21:28 Task Grids and Fast Obstacle Lookups

A task grid can encode whether actions such as walking or building are allowed at each location.
Initialize cells as traversible, then mark cells overlapped by obstacles as blocked to create a constant-time lookup table.
Smaller cells improve geometric accuracy but increase memory use and pathfinding work; halving cell width and height creates four times as many cells.

31:15 Grid Movement, Eight-Direction Actions, and Height Maps

Four-directional movement uses up, down, left, and right; octile movement also permits diagonals.
The COMP 3200 assignments progress from four-directional pathfinding to eight-directional movement.
A height-map grid can encode elevation per cell and restrict movement according to allowable height differences.

33:12 Turning Grid Paths into Smooth Game Movement

A grid path can look robotic when an entity follows every cell transition as a sequence of 90-degree turns.
The workflow is to rasterize obstacles, map start and goal positions to cells, select grid actions, and run a search such as BFS, DFS, or UCS.
Convert the resulting path into unobstructed waypoints, skip reachable intermediate waypoints, and apply steering or smoothing for natural movement.

40:54 Grid Benefits, Precision Costs, and Sparse-Map Limits

Grids are easy to modify when obstacles change, work with graph-search algorithms, and store data contiguously in cache-friendly arrays.
Grid abstraction loses localization precision and may misrepresent small gaps or complex geometry.
A naive grid wastes memory on sparse spaces; a 1,000-by-1,000 map already contains one million cells, motivating hierarchical or sparse-grid methods.

47:43 Vector Fields for Many-to-One Pathfinding

A vector field assigns a direction vector to each grid cell, telling an entity which way to move toward a goal.
Flow fields are especially useful when many NPCs share one destination, such as zombies pursuing a player in Diablo-like games.
Compute the field once per goal instead of running a separate A* search for every entity.

52:04 Building a Distance Map with Breadth-First Search

Initialize distance-map cells to -1, set the goal cell to 0, and run BFS outward through traversible cells.
Each newly reached cell receives its predecessor's distance plus one, giving the four-directional shortest-path distance to the goal.
Cells left at -1 are unreachable, so an entity on one can be identified immediately as having no path to the destination.

57:35 Deriving and Following the Vector Field

For each reachable cell, point toward an adjacent cell with a lower distance value; combine directions into a diagonal when allowed.
An entity follows the field by looking up its current cell's vector and applying that direction to its position.
Recompute the field when the goal changes, then share it among all entities traveling to that goal.

59:55 Making BFS Queues Efficient with an Index Pointer

Removing the first item from an array-backed queue can take O(n) time because every remaining element shifts left.
Keep queued items in the array and advance a front index instead of deleting elements; the queue is empty when the front reaches the end.
This avoids repeated shifting while using storage proportional to the number of items ever enqueued during the search.

1:06:36 Using the Distance Grid as a BFS Visited Set

In a distance map, the initial -1 value doubles as an unvisited marker, so any nonnegative value means BFS has already reached the cell.
This lets the distance grid serve as the closed list without allocating a second structure.
For other grid searches, a Boolean 2D array can provide constant-time visited checks, although retrieving every visited state then requires scanning the grid.

1:09:26 Influence Maps and the Half-Million-Particle Demo

Influence maps modify movement costs to express preferences, such as avoiding a shoreline or steering clear of an enemy turret.
Positive or negative influences can guide agents away from threats or toward defensive objectives, alongside ordinary pathfinding costs.
Churchill's demo routes 500,000 particles using a shared vector field at about 76 frames per second; a 235,000-cell grid's computation takes about 0.4 milliseconds.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Dave Churchill.