Loading presentation...
Prezi is an interactive zooming presentation

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Electronic Games. AI

No description
by

Georgia Papp

on 9 April 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Electronic Games. AI

Pathfinding
Ultra-fast Optimal Pathfinding without
Runtime Search
successfully navigating the game environment
most basic requirement of a game agent AI
agent navigation
movement
planning
Most pathfinding methods search
at the path query time
to compute a path on demand
alternative approach
perform path precomputation and lookup
faster than online search
prohibitive memory
requirements
compressed path database
Optimal paths between any two locations on a map are computed in a pre-processing stage

Fig.1 2D Game labirinth [1]
Fig.2 Game map from
Call of Duty
[2]
We need a technique for compressing path information
use path coherence
Example
We want to travel
MONTREAL, CANADA
SAN DIEGO, CALIFORNIA, intersection
BROADWAY – 10th AVENUE.
Fig.3 Crossroads [3]
Key point
When the
first move
on an optimal path from
a current
location N
to any
target T
in an
area R

is the same
Dynamic Difficulty Adjustment
idea of challenge

difficulty level of the game - adjusted dynamically

player’s skill level

balanced game
store only one move record
corresponding to
(n;R)
References
http://chickswagewar.blogspot.ro/2013/06/skill-challenge-and-flow.html
Computing
Compressed
Path
Databases

[5]
Fig.4 Move Table [4]
Usage
method for adjusting difficulty type of the game
• First Person Shooter (FPS) game

• Platforming game

• Strategy game

• Online multiplayer game

Building a CPD
Compressing a Move Table
Runtime Pathfinding
Approaches
play testing feedback
process can’t be automated mathematical analysis
Improvements
1. DDA by means of automatic level generation - Procedural Content Generation (PCG)
2. DDA by means of AI modification
3. DDA by means of level content adjustment – Hamlet System

right algorithms
Ordering the list L(z)
decreasingly

Average
number of rectangle checks:
1. DDA by means of automatic
level generation

PCG = Procedural Content Generation
Traditionally -> generate content (levels) - before starting to play
saves time and cost
fixes memory limitation issue
reduces the number
of rectangle checks needed to
find a location t

Recent Innovation -> generate content for video-games whilst they are being played
the content generated is dynamically
the content is adapted to the specific user
Conclusion
Compared to a standard
A*-based pathfinding system
average speed-up of up to 700 on realistic
game maps
Steps for generating next level
Future work
multi-agent pathfinding

moving target search

i.e. Infinite Mario Bros - potential unending game
Collect Data
controllable features
gameplay statistics
player's subjective experience
Find features that most affect the user's perception of the game
machine learning tool
Find subjective experience of a player at a given level
multi-layered perceptrons (MLPs)
Implementation of adaptive game
First level - random
Use MLP
inputs = specific features +
controllable features of that level
MLPs decide what kind of level the user
is likely to find most fun.
2. DDA by means of of AI modification
Difficulty level - influenced by the manner in which the opponents play.
Strategy games
Fig.5. Optimal Experience (From [5])
Fig.6. Fun values of optimized vs. random levels for the more human-like agent (From [6])
[6]
http://mms.ecs.soton.ac.uk/2013/papers/dmjc1g10_23990287_finalpaper.pdf
Problem : Select the appropriate algorithm for the AI to use against a specific player, online, and according to the abilities of that player.
= use of machine learning to build intelligent agents
Disadvantages:
rates of learning to accommodate skilled players will be very slow.
in-game agents can only increase - there is no possibility of regression
Genetic Algorithm
Purpose:
keep alive those agents that most closely match the player's abilities
3. DDA by means of level content adjustment. Hamlet System
1. Monitor game data with statistical metrics
2. Predict the player's future state using this data
3. Intervene when an undesirable but avoidable state is predicted

uses statistical metrics to monitor incoming game data.
Aim :
to maintain players in the “Flow Channel"
Hamlet System
Fig.7. Flow diagram, displaying how the challenge that a game provides should be suited to the skill level of the player in order to keep them in the "Flow Channel". (From [7])
Hamlet System
when not enough resources =>
action
Reactive
adjustment of parameters
i.e. health, strength,
accuracy of an attacking enemy
Proactive
adjust game elements not immediately observed by the player
i.e. type, spawning order, accuracy
loops of searching, retrieving, solving and fighting.
new level => new enemies and obstacles are introduced.
Hamlet System
Fig.8. State Transition Diagram (From [8])
[7]
http://mms.ecs.soton.ac.uk/2013/papers/dmjc1g10_23990287_finalpaper.pdf
[8]
http://www.cms.livjm.ac.uk/library/aaa-games-conferences/acm-ace/ACE2005/SS1-5%20(a143).pdf
Conclusion
Hard to apply a suitable DDA for complex games
Unpredictable behavior

Problems:
requirements of domain-specific information in DDA techniques
develop DDA mechanisms -> efficient and cost-effective
produce DDA mechanisms
[4]
http://www.spc-intheworld.com
[3]
[2]
http://wikicheats.gametrailers.com/
[1]
http://sandbox.yoyogames.com/
Adi Botea, Ultra-fast Optimal Pathfinding without Runtime Search,
Proceedings of the Seventh AAAI Conference on Artificial Intelligence
Electronic Games. AI.
[9]
David Michael Jordan Chang,
Dynamic Difficulty Adjustment in Computer Games
Full transcript