Transcript Application of AI techniques for Computer Games

GAMES ARTIFICIAL
INTELLIGENCE
Application of AI techniques
for Computer Games
BSc Computer Games Programming,
2006
Julien Delezenne
Overview of the demo
In-game editor
Pathfinding demo
Design
• The AI component is part of the game
engine
• Contains a generic pathfinding system
• Object-oriented state machines
• Data-driven with the reflection system
AI and architecture
• AI can be divided in two parts
– The game object system
– The AI techniques
• The object system becomes very complex
in commercial games
• AI techniques need to be integrated in a
flexible way
Game system
Object
-TypeInfo
World
1
GameEntity
-Editor
-Name
-Design
1
ActorDef
Map
11
-Player
Tileset
-CellSize
-Divisions
*
-Type
-FileName
*
Actor
-Position
-Orientation
1
1
*
Cell
*
-Position
-Depth
Tile
* 1
-Type
-FileName
Character
-WalkSpeed
-RunSpeed
-ViewConeAngle
-ViewDistance
Placeable
Spawn
Goal
WayPoint
-Next
1
1
Reflection
• For each game entity:
– Instantiation from its name
– Exposition of its properties
– (De)Serialization including with files such as
XML (used in the demos)
– Editable attributes in the editor. The property
grid of the editor is generated automatically
Abstract controller
• Two types of controllers
– Player
– AI
• Only the input is different
• The game logic should only know about
the abstract controller
AI techniques
• Game developers always have:
– A* for pathfinding
– FSM for decision-making
• They are the two techniques of the stealth
demo in a game environnment
Pathfinding
F.E.A.R.
C&C Generals
• Environnment represented as a graph
• A* is independent of the environnment
Pathfinding
• A* is divided in three modules
– Map
– Goal
– Storage
• The client application implement these
objects
• The A* algorithm will send request to them
Pathfinding
1
PathfinderNode
-Parent
PathfinderGoal
-ID
1
*
AStarPathfinderNode
Pathfinder
-Goal
-Heuristic
-Fitness
-SourceNode
-DestinationNode
-CurrentNode
+Run()
AStarPathfinderGoal
1
-DestinationNode
1
+GetHeuristic()
+GetCost()
AStarPathfinderStorage
+CreateNode()
+DestroyNode()
+Reset()
+AddToOpenList()
+AddToClosedList()
+RemoveFromOpenList()
+RemoveFromClosedList()
+FindInOpenList()
+FindInClosedList()
+RemoveBestOpenNode()
CustomPathfinderStorage
+IsNodeValid()
+IsSearchFinished()
CustomPathfinderGoal
PathfinderMap
1
1 1
+GetNeighbourCount()
+GetNeighbour()
AStarPathfinder
AStarPathfinderMap
CustomPathfinderMap
State machine
• Object-oriented
• States are independent of each others
• State changes are requested
• In the demo, the state machine is mostly
driven by the the field of view of the
characters
State machine
FOV = Player in
the field of view
Has no
waypoint
Idle
Combat
ended
Guard
Has a
waypoint
Combat
Timer
In
FOV
At
destination
Search
Goto
Target
Lost
In
FOV
Collision
Follow
In
FOV
Not in
FOV
In
FOV
Patrol
Results
• Actual game demo achieved using the two
most common AI tehcniques: A* and FSM
in a game scenario
Conclusion
• Pros
– Objectives achieved
– Overall methodology
– Reflection system
• Cons
–
–
–
–
Data-driven system not complete
Some performance issues
Need different behaviours
Need an event-system
Future enhancements
•
•
•
•
•
•
•
Scripting
More behaviours
Agents’ memory
Dynamic pathfinding
Navigational meshes
More advanced Toolsets
…