It would be impossible to begin talking about the ins-and-outs of A.I.
without a brief background in 'Graph Theory'. Almost all A.I. techniques using games rely on the programmers
having an understanding of graphs. Graphs in this context refer to a collection of nodes and edges.
Nodes are represented graphically as circles...and edges
are the lines that connect them. A graph can be visualized as nodes representing locations and edges as
paths connecting them.
A graph can be undirected (which means that the paths between nodes can be traversed in both directions)
or directed (in which case the paths are one way).
Think of this as a difference between two-way streets
and one-way streets. Nodes and edges can be drawn where nodes represent coordinates, such as those on
a flight plan, or as symbolic states where the physical location in the graph is meaningless.
Both nodes and edges can have associated values.
These values could be the distance between nodes (such as those representing distances in the flightplan)
or the time it takes to complete an action (such as a node in the action plan).
The ways in which graphs are useful in game A.I. will become evident as we progress through this course.
If you think graphs look familiar, it's because they are.
We've already made a graph of waypoints and had our NPC traverse between them. Graphs are so flexible that
they can be used for a plethora of applications where you need to traverse from one state to another, whether
that be a real state or a conceptual state.
In this example, a graph is being used to define the locations in a tile-based game and the amount of
effort to move from one tile to another. Values placed on the edges are generally referred to as
'Utility Values', whether they represent times, distances,
effort, costs or any other value an NPC might use to make a decision. Let's consider the situation where
an NPC wants to move from tile C2 to A2.
There are 2 possible paths. To decide which path to take,
the NPC can add up all the utility values along each path.
In this case, the utility values aren't about distance, they are about terrain difficulty. Adding up the
values along each path reveals that the longer path (over the bridge) will be less effort. In order to work
with a graph, there needs to be an efficient method of searching through the nodes.
There are two basic high level algorithms for searching through nodes.
The first is called a 'Breadth-First Search'. In a breadth-first search, the NPC marks its current location
(or node) as 1, then it numbers all adjacent nodes to that as 2, then all the adjacent nodes to them
as 3 etc. until the destination node has been reached.
It then counts backwards, in 1s, to the start, to find a path to the goal.
Breadth-first search examines all possible nodes in the graph to find the best path, but due to its thoroughness,
it's time consuming and not optimal. A 'Depth-First Search' is much simpler and quicker, but less effective.
Instead of finding the BEST path, it finds A path. Beginning at the NPC position, an adjacent node is found
and numbered. Then an adjacent node
to this is found and numbered.
This continues until a dead-end is reached, at which time we return to the last node where there was
another direction to try and we head off in THAT direction.
It's like the approach you might take to get out of a labyrinth. When the destination is found, the nodes
are then counted backwards again, to give the path. The most popular algorithm used to find paths in graphs
that is used in games because of its efficiency in being able to find the shortest path, is the
A* algorithm.
It's a little more complex than the other two methods and works like this...
First, all the nodes in the graph are numbered.
We then create two lists: an 'open' list and a 'closed' list.
These will keep track of the nodes that we've visited and processed.
Each node is given 4 values that are used in calculating the path.
First they are given a 'Heuristic' value represented by 'H'.
The 'heuristic' is the estimated cost of getting from an individual node to the destination.
You can use any method you like for calculating that value.
You might use a 'linear distance' or count the 'number of rows and columns'.
The second value is 'Movement Cost' represented by 'G'.
This value is essentially the utility in moving to the node from another node.
This could be based on the actual distance from one node to another
or the cost of traversing a train type, like the tile example we looked at with the bridge. We then store
a calculation that adds together the H and G values and call that 'F' and store the nodes parent, which
is the closest node along the path.
Let's take a look at an example.
We begin by placing the starting node
(in this case, 50) into the 'Closed' list, as this is the location we have visited. We then look for any neighbors
that aren't blocked and aren't in the closed list and add them to the 'Open' list.
We then calculate the heuristic for each node in the open list. In this case, we will use the linear distance
from the node to the destination.
Then we work out our movement cost to go from the starting node to the neighbor.
Again, we use a linear distance. Horizontal and vertical neighbors are a distance of 1 away, with diagonal
neighbors a distance of 1.4. The cost of moving to those nodes becomes their G value. From that,
'F', which is H+G, is calculated.
Whilst we're doing this, all the neighbors are linked back to the current node, thus making the starting
node their parent. With no more nodes to examine in the open list, we now get the node in the open list with
the lowest F value.
This becomes a new location to start searching the neighbors again. The new location node is added to
the closed list as having been visited. Any neighbors not blocked, closed or already on the open list are added
to the open list.
The H value is calculated for any new nodes in the open list.
The G value is also calculated but this time it is the 'cost of movement+the previous cost of movement'.
So in this case, node 32 gets the 'G movement' of 41 + the 'cost of moving' from 41 to 32, which is also
1.
This gives a final G value of 2...and for 32, its F value will be 7. For any of the neighbors of the current
location still in the open list (in this case, 40) a new G value is calculated. If the new G value is less
than the current G value,
the nodes G value is changed and its parent is updated to the current location.
In this example, a new G value coming from node 41 would be 1, plus a horizontal
movement cost of 1, thus resulting in a value of 2.
2 is not less than 40s current G value
and so the node remains unchanged.
Any neighbor without a parent is assigned to the current location and the process begins again, by looking
for the node with the smallest F value in the open list to visit
next. The process ends when we are one node away from the end.
At this point, we have a link of parents that lead all the way back to the start, which when reversed,
provide a path from the start location to the destination. Unity uses the A* algorithm for pathfinding
in its navmesh.
This construct provides a powerful way for us to program navigation and avoidance into our projects.
When you think about it, graphs and their nodes and edges are really a very simple thing. As we progress
through the course, you're going to see them pop up all over the place as they are a staple in artificial
intelligence.
While there are numerous algorithms to traverse graphs, when it comes to games, nothing beats A*
and you'll find plenty of resources to support it.