程序代写代做代考 AI case study algorithm Games & AI #1

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