Game Development Reference
In-Depth Information
data set, we get a path that is identical to the one generated by A*. Provided that
the heuristic used for A* was admissible, Dijkstra's algorithm will always return
the same path as A*. However, Dijkstra's algorithm typically ends up visiting
more nodes, which means it's less efficient than A*.
The only scenario where Dijkstra's might be used instead of A* is when there are
multiple valid goal nodes, but you have no idea which one is the closest. But that
scenario is rare enough that most games do not use Dijkstra's; the algorithm is
mainly discussed for historical reasons, as Dijkstra's algorithm actually predates
A* by nearly ten years. A* was an innovation that combined both the greedy best-
first search and Dijkstra's algorithm. So even though this topic covers Dijkstra's
through the lens of A*, that is not how it was originally developed.
State-Based Behaviors
The most basic AI behavior has no concept of different states. Take for instance
an AI for Pong : It only needs to track the position of the ball. This behavior never
changes throughout the course of the game, so such an AI would be considered
stateless . But add a bit more complexity to the game, and the AI needs to behave
differently at different times. Most modern games have NPCs that can be in one of
many states, depending on the situation. This section discusses how to design an
AI with states in mind, and covers how these state machines might be implemen-
ted.
State Machines for AI
A finite state machine is a perfect model to represent the state-based behavior of
an AI. It has a set number of possible states, conditions that cause transitions to
other states, and actions that can be executed upon entering/exiting the state.
When you're implementing a state machine for an AI, it makes sense to first plan
out what exactly the different behaviors should be and how they should be inter-
connected. Suppose we are implementing a basic AI for a guard in a stealth-based
game. By default, we want the guard to patrol along a set path. If the guard detects
the player while on patrol, it should start attacking the player. And, finally, if in
either state the guard is killed, it should die. The AI as described should therefore
have three different states: Patrol, Attack, and Death.
Next, we need to determine which transitions are necessary for our state machine.
The transition to the Death state should be apparent: When the guard's killed, it'll
enter the Death state. As for the Attack state, the only time it should be entered is
Search WWH ::




Custom Search