Games & AI #1
INTRODUCTION & CASE STUDY : ALIENS VS PREDATOR
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Next 3 Weeks
We will think about AI algorithms for path finding
Context: video games
◦ General requirements for virtual environments / games ◦ How path finding can be applied to games environments ◦ Theoretical and practical aspects
We will do some workshop exercises (project code provided) Assessment: Examination (2 questions)
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Practicalities
Book: Millington & Funge
Workshop tasks will show you how to implement the algorithms we will talk about. Code projects on Blackboard – VS15 & Monogame (VC# Express 15 / Monogame)
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Games&AI:WhatisAI?
Real world AI
Superior AI
Believability
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Games & AI : Requirements?
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Games & AI : Requirements?
Speed (Real-time) Predictable resources Ability to design game play Believability
Not really stupid Not perfect
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
We are going to look at pathfinding
Week
Lecture
Workshop
1
Define our parameters Case Study: AVP
Some theory
The VS15 AI game project : rule-based AI
2
Dijkstra
Implement Dijkstra
3
Dijkstra & A*
Implement A*
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Workshops: Our Simple World
0,0
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Workshops: Rule Based?
0,0
if (targetX > agentX) agent X+=1; else if (targetX < agentX) agent X-=1; else if (targetY > agentY) agent Y+=1; else if (targetY < agentY) agent Y-=1;
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Workshops: Rule Based?
0,0
if (targetX > agentX) agent X+=1; else if (targetX < agentX) agent X-=1; else if (targetY > agentY) agent Y+=1; else if (targetY < agentY) agent Y-=1;
Need more sophisticated rules?
...Need proper planning!
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
A Case Study : Aliens vs Predator (2001)
Requirements:
Start with the game design...
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
A Case Study : Aliens vs Predator (2001)
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Case Study: Aliens vs Predator (2001)
Requirements:
Player can create barriers Aliens can get around them Act as a group
Evident to player
This is all about player experience!
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Case Study
Simplify : Imagine our grid
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Case Study
Code actually quite simple.
Game runs by calling an update loop, every 10-50ms On each update:
1. Visit each location
2. Look at neighbour locations : if scent is higher, set to (neighbour – 1)
3. If location occupied by player: set value to current player scent value
4. Increment player scent value every update
Alien: head for neighbour with highest scent value
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Lets see how it works...
In the game:
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Case Study
Meets our basic requirements:
1. Fast enough
2. Generates believable behaviour
3. Predictable and scalable : O(n) per update – but no idea when converges
4. Easy to design for
But, it is not optimal: we need to take a more theoretical approach...
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Some theory
Path finding or “search” is a generic problem, not only applicable to games: Robots, routing network packets, travel planning,...
Next week we will look at some concrete algorithms. First, need some concepts and terminology:
Searching / path finding works on a “node graph”
3
4
6
1
1 1.4
3
5
4
4
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Breadth first vs depth first
Imagine we have a tree... each nodes represents a value.
We want to find a particular value (or value that fits a particular criteria)
A BCD
E
F
GH
I
What order do we visit them in? (how do we traverse the tree)
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Breadth first vs depth first
Breadth first: Visit each level, one by one - A B C D E F G H I
Depth first: Visit each child node to its maximum depth – A B E F C D G I H
A BCD
E
F
GH I
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Breadth first vs depth first
What difference does it make?
Consider chess
Each node = result of a move
Q: How quickly could black lose all his/her bishops? Q: What is the longest time white can retain his/her queen?
Start
My move
2 4
46
4
6
8
5
Your move
My move
3
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson
Next week
What if we are not looking at trees?
Graphs have loops, and different edge weights...
Games & AI #1: Introduction & Case Study : Aliens vs Predator Patrick Dickinson