 Artificial Intelligence
Lecture 02 - Pathfinding
Edirlei Soares de Lima Game AI Model
Pathfinding
Steering behaviours
Finite state machines
Automated planning
Behaviour trees
Randomness
Sensor systems
Machine learning Pathfinding
Game characters usually need to move around their level.
While simple movements can be manually defined by game
developers (patrol routes or wander regions), more complex
movements must be computed during the game. Pathfinding
Finding a path seems obvious and natural in real life. But how
a computer-controlled character can do that?
The computer needs to find the “best” path and do it in real-time. Search Problem
Pathfinding is a search problem: find a sequence of actions
from an initial state to a goal state.
Problem definition:
Initial state
Goal state
State space
Set of actions
Cost functions Search Problem
The process of looking for a sequence of actions that reaches
the goal is called search.
Once a solution is found, the actions it recommends can be
carried out.
Phases:
Goal formulation
Search
Execution Examples of Search Problems
Route-finding:
State space: map;
Initial state: current city;
Goal state: destination city;
Set of actions: go from one city to another (only possible if there is a
path between the cities);
Action cost: distance between the cities; Examples of Search Problems
Vacuum world:
State space: agent location and the dirt
locations (8 possible states);
Initial state: any state;
Goal state: all locations clean (state 7
or 8);
Set of actions: move left, move right,
and suck;
Action cost: 1 per action; Examples of Search Problems
8-Puzzle Game:
State space: 181.440 possible states;
Initial state: any state;
Goal state: Goal State in the figure;
Set of actions: move the blank space left,
right, up, or down;
Action cost: 1 per action;
1
2
5-puzzle (4x4) 1.3 trillion possible states.
4-puzzle (5x5) 10²⁵ possible states. Examples of Search Problems
Chess Game:
State space: approximately 1040 possible
states;
Initial state: start position of a chess game;
Goal state: any checkmate state;
Set of actions: pieces movement rules;
Action cost: examined states; General Pathfinding Problems
State space: waypoint graphs or
tiled-based maps;
A
Initial state: current location (A);
Goal state: destination location (B);
Set of actions: movements;
B
Action cost: distance or terrain
difficulty; Pathfinding algorithms can’t work directly on the level
geometry. They rely on a simplified version of the level,
usually represented in the form of a graph. Exercise 1
1
) Create a maze in Unity. This maze will be used to test the
pathfinding algorithms. Example: General Graph Structure
Edge
G = (V, E)
G: graph;
V: set of vertices;
E: set of edges;
Vertex General Graph Structure
Directed graph: a graph in which edges have orientations. General Graph Structure
Weighted graph: directed on undirected graph in which a
number (the weight) is assigned to each edge. A simplified version of the game level can be represented in
the form of a graph. Tiled-based maps can also be seen as graphs:
A
A
B
B
memory data:
0
0
1
1
0 0 0 1 1 1
0 0 0 1 1 1
0 0 1 0 0 1
1 0 0 0 0 0 Graph Representation
Uses a vector or list Adj with |V| adjacency lists, one for each
vertex v V.
For each uV, Adj[u] contain references for all vertices v such
that (u, v)A. That is, Adj[u] contains all adjacency vertices of u. Graph Representation
Given a graph G = (V, E), we assume that vertices are labeled with
numbers 1, 2, . . . , |V|.
The adjacency matrix is a matrix Aij of dimensions |V| × |V|,
where:
1
0
ꢃꢄ ꢃ, ꢀ
ꢆꢇℎꢈꢉꢊꢃꢋꢈ
ꢂ
= ቊ Graph Representation in Unity
We can easily create an adjacency list by implementing a class
to represent the edges of the graph (called waypoints in the
navigation graph). Each waypoint is connected with a set of
other waypoints (edges):
public class Waypoint : MonoBehaviour {
public Waypoint[] edges;
}
We also need another class to store a reference to all the
vertices of the graph (waypoints):
public class Pathfinding : MonoBehaviour {
public Waypoint[] waypoints;
} Graph Representation in Unity
A waypoint also have a position in the world. But instead of
adding this information to the waypoint class, a better
solution is to associate the class with a game object (such a
sphere) and then create a prefab. Graph Representation in Unity
Now we can place waypoints in the game level and then
connect them.
WP (10)
WP (13)
WP (12) Graph Representation in Unity
To better visualize the connections, we can use gizmos to
draw lines between connected waypoints.
public class Waypoint : MonoBehaviour {
public Waypoint[] edges;
void OnDrawGizmos()
{
Gizmos.color = Color.green;
foreach (Waypoint e in edges)
{
Gizmos.DrawLine(transform.position,
e.gameObject.transform.position);
}
}
} Exercise 2
2
) Place waypoints in the visibility points of the maze created in
the previous exercise. Then, connect all the waypoints to Pathfinding
Now that we have the navigation graph, how can we find the
best path to go from one waypoint to another?
There are many graph search algorithms:
Depth-first search (DFS)
Dijkstra algorithm
A* algorithm
Which algorithm is the best? Strategy:
It starts at the root vertex (any arbitrary vertex of the graph) and
explores the neighbor nodes first, before moving to the next level of
neighbors.
Search Tree:
Graph:
A
F
A
E
C
B
B
C
G
D
D
E
F
G d+1
Complexity: O(b )
*
processor capable of processing 1 million nodes per second.
Considering a ramification factor b = 10, each node using 1KB of memory, and a Depth-first Search (DFS)
Strategy:
It starts at the root vertex (any arbitrary vertex of the graph) and
explores as far as possible along each branch before backtracking.
Search Tree:
Graph:
A
M
A
D
P
B
D
B
C
C
E
F
E
F
N
M
Q
N
P
Q Depth-first Search (DFS)
Consumes less memory than the BFS: once a node has been
expanded, it can be removed from memory as soon as all its
descendants have been fully explored.
In the previous example, at depth d = 16, DFS would require
only 156 KB of memory (instead of 10 exabytes).
Problem: the algorithm may perform long searches when the
solution is simple (when the goal is close to the root vertex). Dijkstra Algorithm
Strategy:
It starts at the root vertex (any arbitrary vertex of the graph) and
explores the neighbor nodes with the lowest path cost.
Search Tree:
Graph:
A
118
A
D
75
118
170
111
170
7
5
99
B
D
B
C
G
H
C
75
71
75
71
99
111
E
F
E
F
G
H Dijkstra Algorithm
The first solution found is always the optimal solution (only if
there are no negative costs).
When all step costs are the same, Dijkstra search is similar to
Dijkstra is better than BFS and DFS algorithms, but it still
searches the entire graph indiscriminately for the shortest
possible route (it doesn't take into consideration the
objective). A* Algorithm
Strategy:
Combines the path cost g(n) with an heuristic value h(n);
g(n) = path cost from the start node to node n;
h(n) = estimated cost of the cheapest path from n to the goal (e.g.
straight-line distance);
The evaluation of a node is given by: f(n) = g(n) + h(n);
Pathfinding in games is synonymous with the A* algorithm.
Almost every pathfinding system uses some variation of the
A* algorithm. A* Algorithm
0+366=366
Sibiu
Timissoara
Zerind
1
40+253=393 118+329=447 75+374=449
Fagaras
Rimnicu Vilcea
220+193=413
2
80+366=646 239+176=415 291+380=671
366
0
Neamt
Pitesti
241
234
380
100
Bucharest
Craiova
Drobeta
Eforie
Sibiu
38+253=591
Bucharest
Craiova
Pitesti
Sibiu
160
242
161
176
77
3
450+0=450
366+160=526 317+100=417 300+253=553
Rimnicu Vilcea 193
Bucharest
418+0=418
Craiova
Rimnicu Vilcea
414+193=607
Fagaras
Giurgiu
Iasi
Sibiu
253
329
199
374
80
455+160=615
Timisoara
Vaslui
226
244
151
Lugoj
Zerind
Hirsova
Urziceni A* Algorithm
The A* algorithm is complete and optimal.
Complexity: is exponential in the depth of the solution (the
d
shortest path) O(b ) , but the heuristic function has a major
effect on the practical performance of the algorithm. A good
d
heuristic prunes away many of the b nodes.
No other algorithm guarantees to expand less nodes than the
A* algorithm. A* Algorithm Pseudocode
function A*(start, goal)
closedSet := {};
openSet := {start}; //priority queue structure
cameFrom := an empty map;
gScore := map with default value of Infinity;
gScore[start] := 0;
fScore := map with default value of Infinity;
fScore[start] := heuristic_cost_estimate(start, goal);
... A* Algorithm Pseudocode
...
while openSet is not empty do
current := the node in openSet having the lowest fScore[] value;
if current = goal then
return reconstruct_path(cameFrom, current);
openSet.Remove(current);
for each neighbor of current do
if neighbor in closedSet then
continue;
if neighbor not in openSet then
tentative_gScore := gScore[current] + dist_between(current,
neighbor);
if tentative_gScore >= gScore[neighbor] then
continue;
cameFrom[neighbor] := current;
gScore[neighbor] := tentative_gScore;
fScore[neighbor] := gScore[neighbor] +
heuristic_cost_estimate(neighbor, goal);
return failure; A* Algorithm Unity
public List<Waypoint> FindPath(Waypoint start, Waypoint goal) {
List<Waypoint> closedSet = new List<Waypoint>();
SimplePriorityQueue<Waypoint> openSet = new
SimplePriorityQueue<Waypoint>();
openSet.Enqueue(start, Heuristic(start, goal));
Dictionary<Waypoint, Waypoint> cameFrom = new Dictionary<Waypoint,
Waypoint>();
Dictionary<Waypoint, float> gScore = new Dictionary<Waypoint,
float>();
foreach (Waypoint wp in waypoints)
{
}
gScore[start] = 0;
... ...
while (openSet.Count > 0){
Waypoint current = openSet.Dequeue();
if (current == goal)
return ReconstructPath(cameFrom, current, start);
foreach (Waypoint neighbor in current.edges){
if (closedSet.Contains(neighbor))
continue;
if (!openSet.Contains(neighbor))
openSet.Enqueue(neighbor, gScore[neighbor] +
Heuristic(neighbor, goal));
float tentative_gScore = gScore[current] + Heuristic(current,
neighbor);
if (tentative_gScore >= gScore[neighbor])
continue;
cameFrom[neighbor] = current;
gScore[neighbor] = tentative_gScore;
openSet.UpdatePriority(neighbor, gScore[neighbor] +
Heuristic(neighbor, goal));
}
}
return new List<Waypoint>();
} A* Algorithm Unity
float Heuristic(Waypoint p1, Waypoint p2){
return Vector3.Distance(p1.gameObject.transform.position,
p2.gameObject.transform.position);
}
List<Waypoint> ReconstructPath(Dictionary<Waypoint,Waypoint> cameFrom,
Waypoint current, Waypoint start){
List<Waypoint> total_path = new List<Waypoint>();
while (current != start){
foreach (Waypoint wp in cameFrom.Keys){
if (wp == current){
current = cameFrom[wp];
}
}
}
total_path.Reverse();
} Exercise 3
3
) Implement the A* algorithm in the Pathfinding class created
in the previous exercises.
a) Execute the FindPath function and
show the resulting path in the
console;
b) Add parameters to define the start
and goal waypoints;
c) Test the algorithm with different
start and goal waypoints; X
(
a)
(
b)
O
1
2
3
4
5
6
. Find closest visible node (a) to current location (X);
. Find closest visible node (b) to target location (O);
. Search for the best path from (a) to (b);
. Move to (a);
. Move to target location (O); Exercise 4
4
) Add an object (e.g. a capsule) to represent an NPC and then
use the pathfinding algorithm to move the NPC from any
place to any goal destination.
a) Create a function to find the
closest waypoint to use as start
and goal waypoints;
b) Move the NPC slowly though the
computed path; World Representations
Pathfinding algorithms do not work directly on the level
geometry. They rely on a simplified world representation.
Most common techniques for world representation:
Tile Graphs;
Points of Visibility;
Finely Grained Graphs;
Expanded Geometry; Tiled-Based Graphs
Tile-based levels split the whole world into regular, usually
square, regions (although hexagonal regions are occasionally
seen in some games).
The whole level can be tiled-based or the tile grid overlays the 3D level;
generated automatically. Easy to estimate
edge’s weights.
Problems: the search spaces can quickly
become extremely large (a 100x100 map
has 10,000 nodes and 78,000 edges!). If no
path smoothing techniques are applied,
character’s movements will be unnatural. Points of Visibility (POV)
A points of visibility navigation graph is created by placing
waypoints at important points in the environment such that
each waypoint has line of sight to at least one other.
Usually, the waypoints are placed by hand (level designer task);
Advantages: easy to implement. Easy to
waypoints (e.g. good sniping, cover, or
ambush positions).
Problems: large maps require a lot of
work to place all waypoints manually.
Problematic if the game includes map
generation features. Blind spots problem. Expanded Geometry
A POV graph can be automatically generated using the
expanded geometry technique.
a) Expand geometry (by a amount proportional to the bounding radius
of moving agents);
b) Connect all vertices;
c) Remove non-line of sight edges; Finely Grained Graphs
Poor paths and inaccessible positions can be improved by
increasing the granularity of the navigation graph.
improves path smoothness. Can be
generated automatically using “flood fill”
algorithm.
Problems: can have similar performance
issues as tiled graphs. Finely Grained Graphs Flood Fill
1. Place a seed node somewhere in
the map;
2
. Expand the nodes and edges
outward from the seed in each
available direction (e.g. 8
directions), and then the nodes on
the fringe of the graph;
Check for collisions with the level
geometry;
3
. Continue until all the navigable
area is filled. Path to an Item Type
What to do when we need a path to an item type (such as a
rocket launcher) that can be found in several locations?
In this situation, Dijkstra’s algorithm is a better choice. Path Smoothing
When the navigation graph is in the shape of a grid or when
the path have unnecessary edges, the movements of the
agent may look unnatural.
Solution: Path Smoothing Simple Path Smoothing Algorithm
Check for the “passability” between adjacent edges. If one of
the edges is superfluous, the two edges are replaced with one.
passability” can be checked thought a ray-cast. If we can cast a ray
between A and C then waypoint B is not needed. Simple Path Smoothing Algorithm
1
2
3
. Grab source E1 (edge);
. Grab destination E2 (edge);
. If the agent can move between the
source of E1 and destination of E2:
E2
E1
E1
a) Assign the destination of E1 to the
destination of E2;
b) Remove E2;
E2
E1
E1
4
. If the agent cannot move between the
source of E1 and destination of E2:
a) Assign E2 to E1;
5
. Repeat until the destination of E1 or destination of E2 is the endpoint of
the path; Simple Path Smoothing Algorithm Tile-based graphs and points of
visibility are useful solutions to
simple problems, but the majority
meshes.
It takes advantage of the fact that
the level designer already needs to
specify the way the level is
connected using polygons/triangles.
Can use level geometry or a new
geometry created specially for network of convex polygons.
anywhere in the polygon);
While waypoints require a lot of points, the navigation mesh needs
only few polygons to cover same area. Example 1:
Waypoints
Graph
Mesh Example 2:
Waypoints
Graph
Mesh Optimization Hierarchical Pathfinding
Hierarchical pathfinding works in a similar way to how humans
move around their environment.
Typically two hierarchical levels, but can be more.
First find a path in high-level, then refine in low‐level. Optimization Pre-Calculated Paths
If the game environment is static and memory usage is not a
problem, a good option to reduce CPU load are pre-calculated
path tables. Optimization Pre-Calculated Costs
Sometimes it’s necessary for a agent to calculate the cost of
traveling from one place to another. For example, to decide
which is easiest item to get. This can be done with pre-
calculated cost tables. Optimization Other Techniques
Time-Sliced Pathfinding: allocate a fixed amount of CPU
resources per update step for all the search requests and
distribute these resources evenly between the searches.
Considerable amount of coding work required!
Store Path Results: save pathfinding results in memory an
reuse then when necessary.
Recompute paths to avoid problematic situations: Unity’s Navigation System allows characters to intelligently
move around the game world. The system uses navigation
meshes automatically created from the scene geometry.
NavMesh data structure that describes
the walkable surfaces of the game world.
NavMesh Agent component to create
moving characters.
holes, floors, or fences).
ꢁꢂꢃꢄꢅꢊꢋꢄꢉꢀꢌꢍꢃ
ꢀꢁꢂꢃꢄꢅꢆꢇꢃꢈꢉ
ꢊꢎꢎꢂꢃꢄꢅꢏꢐꢈꢑ
NavMesh Obstacle component to define
moving obstacles that the agents should
avoid while navigating the world.
ꢁꢂꢃꢄꢅ The process of creating a NavMesh from the level geometry
uses the meshes of all Game Objects that are marked as
mesh that approximates the walkable surfaces of the level. Creating a basic NavMesh:
(Step 1): Select the objects that represent walkable surfaces and mark
them as “Static Geometry” and “Walkable” in the Object tab of the
(Step 2): Select the objects that represent not walkable surfaces and
mark them as “Static Geometry” and “Not Walkable” in the Object tab Creating a basic NavMesh:
(Step 3): Adjust the bake settings to match the agent properties.
Agent Radius: defines how close the agent
center can get to a wall or a ledge.
Agent Height: defines how low the spaces
are that the agent can reach.
Max Slope: defines how steep the ramps
are that the agent walk up.
Step Height: defines how high obstructions
are that the agent can step on.
(Step 4): Click bake to build the NavMesh. The resulting NavMesh will be shown in the scene as a blue
overlay on the underlying level geometry: Creating a NavMesh Agent:
(Step 1): Create an object to represent the agent (e.g. a cylinder).
(Step 2): Add a NavMesh Agent component to the object (Component
(Step 3): If necessary, adjust the agent radius to match the object. The NavMesh Agent component handles both the
pathfinding and the movement of the character.
The simplest way to move the agent towards a destination is
done by setting the desired destination point by script.
public class AgentControl : MonoBehaviour {
public Transform goal;
void Start(){
NavMeshAgent agent = GetComponent<NavMeshAgent>();
agent.destination = goal.position;
}
} NavMesh Obstacle components can be used to describe
obstacles the agents should avoid while navigating.
When an object obstructs the agent path, the Navigation System will
automatically find another path (if there is one). Off-Mesh Links are used to create paths crossing outside the
If the path via the off-mesh link is shorter than via walking along the
NavMesh, the off-mesh link will be used. The Navigation Areas define how difficult it is to walk across a
specific area, the lower cost areas will be preferred during
path finding.
The cost per area type can be set globally in the Areas tab. Exercise 5
5
) Modify the scene created in Exercise 4 to use the Unity
b) Create an agent;
c) Create a set of destination points;
d) Make the agent move through the
destination points;
e) Add different costs to some of the
corridors of the maze. 