Transcript Interactive video games - Winona State University

Computational theory techniques in interactive
video games
•Video games began with “Tennis for
Two” in 1958
• In the 1970’s Atari produced the
console game Pong
• Pac Man was released in 1980
• Since then the video game industry
has grown to a 20+ billion dollar a
year industry
(Dec 2008, World of Warcraft hits
11.5 million subscriptions)
•Today’s games have become increasingly
complex, engaging and intelligent
• Computer controlled Artificial Intelligence
has had to evolve in order for this to
happen
What is “Artificial Intelligence” or “AI” in
terms of a video game?
Academic AI vs. Game AI
• Academic AI is trying to create
a real intelligence through
artificial means
• Game AI seeks to be believable
and fun
• Academic AI focuses on solving a problem optimally
• Game AI is actually written to be sub-optimal
(Who wants to play a game that is impossible to win?)
Goals of Game AI then are:
• Simulate intelligent behavior
• Provide a believable challenge (that can then be
overcome by the player)
• Be fun!
No →
Two areas that deal directly with computational
theory
• Movement – The A* Algorithm
• Behavior – Finite State Machines
The A* algorithm
• NPC (Non-Player Characters) need to be able to
move through their environment in an
intelligent way i.e. don’t get stuck on a tree,
take the shortest path to their destination
• Highly limited computational resources
The Search Area
• Divide the search area into a square grid
• This method uses a 2-dimensional array
• Record the status of each square as
walkable or un-walkable
• Path is found by figuring out which
squares we should take to get from A
to B
Starting the Search
• Begin at A, add it to an “open list”. This is a list
of squares that need to be checked
• Find all reachable squares adjacent to the start
point, ignore un-walkable squares. Add each
to open list and save point A as its “parent
square”
• Drop A from open list and add to closed list
• Choose adjacent square on the open list and repeat
Which square to choose? – Lowest F cost
Path Scoring
F=G+H
• G = cost to move from A to a given square
following the path to get there
ex. 10 for ↕ or ↔, 14 for diagonal
• H = estimated cost to move from a given square
to the final destination
H is an estimate that can be calculated several ways.
This example uses the “Manhattan Method” which
calculates the total number of squares moved
horizontally or vertically to reach the target square
and multiplies that number by 10 (G value)
• Choose the lowest F score square from the open
list
• Drop chosen square from open list and add to
closed
• Check adjacent squares, add squares to open list
if they are not there already. Make selected
square the parent of new squares
• If adjacent square is already on open list, recompute G value to see if it is lower. If it is,
re-compute F
• Once the target square is added to the closed list
we are ready to determine the path
• Just have to start at the red target square and
work backwards moving from one square to
its parent following the arrows
Finite State Machine
• Provide illusion of intelligence
• Powerful tool for modeling NPC behavior
• Quick to code
• Easy to debug
• Little computational overhead
• Intuitive
• Very flexable
•The ghosts in Pac-Man could easily be implemented
as a finite state machine
• Evade state common to all ghosts
• Chase state unique to each ghost i.e. One
takes all lefts, one rights, one goes
straight, and the last heads for the player
• Player eating a power pill is the transition
from the Chase state to the Evade state.
A simple timer running down is used to
trigger the transition back
Code example:
enum StateType{state_RunAway, state_Patrol,
state_Attack};
void Agent::UpdateState(StateType
CurrentState)
{
switch(CurrentState)
{
case state_RunAway:
EvadeEnemy();
if (Safe())
{
ChangeState(state_Patrol);
}
break;
case state_Patrol:
FollowPatrolPath();
if (Threatened())
{
if (StrongerThanEnemy())
{
ChangeState(state_Attack);
}
else
{
ChangeState(state_RunAway);
}
}
break;
case state_Attack:
if (WeakerThanEnemy())
{
ChangeState(state_RunAway);
}
else
{
BashEnemyOverHead();
}
break;
}//end switch
}
FSM’s can easily be created for more complex behavior
Questions
References
Buckland, Mat. Programming game AI by example. Wordware, 2005. Print.
Funge, John. Artificial intelligence for computer games. A K Peters, Ltd., 2004. Print.
Kehoe, Donald. "Designing Artificial Intelligence for Games (Part 1)." Intel
Software Network (2009): n. pag. Web. 29 Apr 2010.
<http://software.intel.com/en-us/articles/designing-artificial-intelligencefor-games-part-1/>.
Lester, Patrick. "A* Pathfinding for Beginners." Policy Almanac. N.p., Jul 2005.
Web. 29 Apr 2010.
<http://www.policyalmanac.org/games/aStarTutorial.htm>.
Nareyek, Alexander. "AI in Computer Games." Queue (2004): 59-65. Web. 29 Apr
2010. <http://queue.acm.org/detail.cfm?id=971593>.