Game Development Reference
In-Depth Information
in pathfinding, to search through the action space for the sequence of actions that
would satisfy the world state. Considering that we
'
re literally looking for a
“
path
”
through a graph of actions, this one makes total sense.
A full implementation of GOAP is beyond the scope of this topic, but there are a
number of texts written on the subject. The best I
'
ve read is in AI Game Program-
ming Wisdom 2. The article is called
“
Applying Goal-Oriented Action Planning to
Games,
”
written by Jeff Orkin. I highly recommend you check it out.
I get a lot of questions about pathfinding with regards to AI. I find this a little strange
since I honestly don
'
t consider pathfinding to be an AI problem. Pathfinding is really
just an optimized search algorithm across a data structure, typically a graph. The
same algorithm can apply to many classifications of problems, including generating
an action plan from a GOAP model. On The Sims, pathfinding is handled by a
completely different team called MoTech (Motion Technology; they handle things
like animation programming), while the sim behavior AI is handled by me on the
gameplay team. This is fairly common in most companies where I
ve worked: A sys-
tems engineer handles a lot of the pathing, while someone on the gameplay team
handles the behaviors.
The problem of finding a valid path through terrain is one of simplification. The
world itself is simplified into a graph of nodes (or a mesh with edges; either way,
the principle is the same) that is then traversed with a search algorithm to find a
good path between two nodes in that graph. This graph or mesh represents the
walkable terrain. This is the technique we used at Super-Ego Games in Rat Race
(see Figure 18.4).
So how do you go about creating such a system? Let
'
s start with the nodes. A node
describes a point in space that the agent must reach. Nodes are connected by arcs,
which are essentially straight lines. For most pathing graphs, an agent may freely
move between any two nodes directly connected by an arc. Thus, in order to move
from one node to its neighboring node, all you need to do is rotate to face the correct
direction and move in a straight line as described earlier in this chapter.
There
'
'
s a slight problem with this method. Since the nodes are all connected by
straight lines, it
'
s possible that the agent
'
s motion will look a bit robotic, especially
if the graph is laid out like a grid. If the agent wanted to move onto a perpendicular
arc, it would walk to the node, make a 90-degree turn, and then walk to the next
point. This doesn
t look natural at all. There are two things you can do to combat
this problem. The first is to ensure that the nodes are not placed in an obvious
'
