Loading presentation...
Prezi is an interactive zooming presentation

Present Remotely

Send the link below via email or IM


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.


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

Georgia Papp

on 9 April 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Electronic Games. AI

Ultra-fast Optimal Pathfinding without
Runtime Search
successfully navigating the game environment
most basic requirement of a game agent AI
agent navigation
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
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
We need a technique for compressing path information
use path coherence
We want to travel
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

Fig.4 Move Table [4]
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
play testing feedback
process can’t be automated mathematical analysis
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)

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
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
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])
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
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
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 =>
adjustment of parameters
i.e. health, strength,
accuracy of an attacking enemy
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])
Hard to apply a suitable DDA for complex games
Unpredictable behavior

requirements of domain-specific information in DDA techniques
develop DDA mechanisms -> efficient and cost-effective
produce DDA mechanisms
Adi Botea, Ultra-fast Optimal Pathfinding without Runtime Search,
Proceedings of the Seventh AAAI Conference on Artificial Intelligence
Electronic Games. AI.
David Michael Jordan Chang,
Dynamic Difficulty Adjustment in Computer Games
Full transcript