|
All Articles Sorted By Date
Near Optimal Hierarchical Path-Finding
Abstract: The article presents HPA* (Hierarchical Path-Finding A*), a hierarchical approach for reducing problem complexity in path-finding on grid-based maps. This technique abstracts a map into linked local clusters. At the local level, the optimal distances for crossing each cluster are precomputed and cached. At the global level, clusters are traversed in a single big step. A hierarchy can be extended to more than two levels. Small clusters are grouped together to form larger clusters. Computing crossing distances for a large cluster uses distances computed for the smaller contained clusters. Our method is automatic and does not depend on a specific topology. Both random and real-game maps are successfully handled using no domain-specific knowledge. Our problem decomposition approach works very well in domains with a dynamically changing environment. The technique also has the advantage of simplicity and is easy to implement.
An Architecture for Integrating Plan-Based Behavior Generation with Interactive Game Environments
Abstract: In this article, we describe an architecture called Mimesis, designed to integrate a range of intelligent components with conventional game engines. The architecture is designed to bridge the gap between game engine design and development and much of the work in AI that focuses on the automatic creation of novel and effective action sequences. Users of the system construct two parallel models of the game world, one using extensions to existing game engine code, the other using techniques for explicit modeling of actions in terms of their requirements for execution and their effects on the game world. When integrated with a game engine, Mimesis acts as a runtime behavior generator, responsible for both generating plans--coherent action sequences that achieve a specific set of in-game goals--and maintaining the coherence of thos plans as they execute in the face of unanticipated user activity. In this article, we describe the architecture, its main components, and the APIs available for integrating it into existing or new game engines.
Efficient Navigation Mesh Implementation
Abstract: This article describes an efficient implementation to provide a solution to the path-finding problem, while taking into account memory storage and runtime requirements for use on current video game hardware, including the Xbox, PlayStation 2, and Nintendo GameCube. The in-game usuage allows for containment of AI-controlled characters and navigation against the static environment with minimal overhead and computation time per object.
Third-Person Camera Navigation
Topics: Camera; Genres: Action
Abstract: For complex scenes, we must overcome some significant technical challenges to make a third-person camera interact smoothly with the world. While this problem can be solved by simply limiting the camera to fixed positions or predetermined paths, these solutions restrict the user's ability to explore freely. To allow unrestricted exploration of complex environments, it's necessary to design a dynamic and user-controllable camera. In this article, we outline a basic set of steps for building a dynamic third-person camera system, and describe a number of solutions for the trickier problems of scene-bounding and occlusion that arise in the camera's navigation of the scene.
Narrative Combat: Using AI to Enhance Tension in an Action Game
Topics: General; Genres: General
Abstract: This article discusses the creation of an AI system that can modulate difficulty and pacing for an action game. In addition to combining strongly paced elements wtih replayability and more freeform gameplay, it becomes much easier for a designer to create a well-paced level. This is because the system only requires a designer's guidelines for the overall difficulty of a particular area, while in most games, designers must extensively tweak enemy positions, spawn points, weapons, timing issues, and more to accomplish the same task. Adjusting for the player's skill level also avoids the common problem in which designers tune gameplay to their own skill level, rather than the typical user's skill level. As a result, the game becomes much too difficult for the average player. Adjusting for a player's skill allows for more seamless transitions between difficulty levels when the pacing changes.
NPC Decision Making: Dealing with Randomness |  |
Topics: Randomness; Genres: General
Abstract: In this article, we describe an algorithm for solving multistep decision problems with randomness. The basic algorithm is called dynamic programming, or DP. Various versions of DP have been successfully used to build an excellent Tetris player and train a world-class backgammon player.
An Object-Oriented Utility-Based Decision Architecture
Topics: Architecture; Genres: General
Abstract: This article presents an object-oriented utility-based decision architecture that has signficant advantages over explicit decision tree architectures in terms of flexibility and maintainability. The principles described in this article derive from decision theory literature and have been applied in many situations, including the weapon selection AI in the real-time strategy game Star Wars: Obi-Wan. Like traditional AI expert systems, this architecture often derives its intelligence by encoding human knowledge in the form of heuristic rules.
A Distributed-Reasoning Voting Architecture
Topics: Architecture; Genres: General
Abstract: This article discusses an alternative AI architecture composed of multiple independent reasoning modules, henceforth called advisors, plus an arbiter that performs command fusion on the inputs from the advisors. This voting-based architecture is easy to use, easy to implement, and easy to maintain.
Attractors and Repulsors
Topics: Pathfinding, Movement, Flocking; Genres: General
Abstract: Helping your AI-controlled entities know what to stay close to and what to avoid can go a long way in helping to generate realistic simulated behaviors. A large part of tasks such as walking through a crowd, racing down a track, or flying through space consists of staying close to some objects and avoiding others. Attractors and repulsors can be used for many purposes, including simulating flocking behaviors, collision avoidance for racing, and tracking opponents in 2D or 3D environments. We can build attraction curves - functions that determine the level of push and pull between objects - to influence the movement of our AI-controlled objects. We can also combine simple curves into more complex composite curves to build interesting emergent behaviors.
Advanced Wall Building for RTS Games
Topics: General; Genres: RTS
Abstract: Most real-time strategy (RTS) games include walls or similar passive defensive structures that act as barriers against enemy unit movement. Having an automated wall-building algorithm increases the competitiveness of nonplayer character opponents and provides a useful addition to random map generation. The original wall-building article presented a basic algorithm and discussed a few potential improvements. In this article, we will implement all of the suggested improvements and deal with more advanced issues like walling off cities, reusing existing walls, destructible natural barriers, and walling off shorelines.
Artificial Neural Networks on Programmable Graphics Hardware
Topics: Neural Networks; Genres: General
Abstract: This article shows how an artificial neural network can be implemented using a GPU-based BLAS level 3 style single-percision general matrix-matrix product (SGEMM) and an activation function pixel shader under Direct3D, version 9.
AI and Design: How AI Enables Designers
Abstract: Whether you�re a programmer who�s always wanted to work on the game design or a designer who thinks there might be something to this "programming" thing, here�s your chance to talk with someone who has worked both sides of the fence. We�ll focus on AI and the ways in which AI development does (or should) overlap with the game design process, drawing case studies from the presenter�s experiences as Lead Designer for Rise of Nations, Alpha Centauri, and Civilization II. We�ll talk about why delaying AI development �until the design docs are final� is a wasted opportunity, and how both AI and Design benefit from simultaneous prototyping. We�ll explore not only the traditional use of AI to determine goals and strategy for computer players, but also the critical role of AI in supplying �personality� to computer-controlled characters. Perhaps most importantly we�ll talk about the sometimes-unexpected ways AI techniques can be invaluable in content generation.
AI: Gameplay & Design: A Marriage of Heaven or Hell?
Abstract: As AI becomes ever more complex, does this open the door for more or less gameplay? Lionhead's Jonty Barnes and Peter Molyneux will demonstrate the benefits and drawbacks AI can have on gameplay and design, by looking at games from the past, present, and future. Technology advances are always exciting and it is tempting as a developer to incorporate cutting edge technology wherever and whenever possible but a designer must always remember that the gameplay experience must be the primary consideration in any game design. However, used well, sophisticated AI can open up innumerable gameplay and design possibilities. This session looks at what has now become possible in the field of AI and what impact and effect it will have on the games of the future.
Artificial Potential Fields for the Control of Navigation and Animation
Abstract: This lecture summarizes the major ideas in the use of artificial potential fields (APFs) over the past quarter century, and show how they can be applied to games. The major topics include the theory behind APFs; designing appropriate potential and/or force functions; algorithms for using APFs in both navigation and animation; avoiding or escaping from deadends and other local minima; enforcing stability in motion; conforming to dynamic constraints; vortex fields and other APF variations; application to avoiding collisions with moving obstacles; and application to multi-agent movement in flocks or formations.
Beyond Finite State Machines: Managing Complex, Intermixing Behavior Hierarchies
Abstract: This lecture discusses the design and implementation idioms for structuring complex, hierarchical, character behavior. This includes idioms for authoring tightly coordinated multi-character behavior, such as conversation behavior. Techniques include the use of meta- behaviors to monitor and modify the execution state of other behaviors, and the use of joint behaviors to manage multi-character coordination (avoiding ad hoc communication). Finally, advantages and challenges of moving away from imperative programming (C++) to behavioral programming are discussed.
The Full Spectrum Warrior Camera System
Abstract: This lecture focuses on the details of the camera system technology used in the game Full Spectrum Warrior (FSW). The lecture covers the camera motion system, which is based on a modified version of the proportional controller often used in game camera systems. The lecture also covers the unique "autolook" feature that gives players a better view of the battlefield in situations where the view would normally be largely obstructed. Collision avoidance and high-level architecture considerations are also discussed, as well as techniques for providing feedback to programmers and designers, who need to "tune" the system for optimal performance. The lecture concludes with a discussion of the limitations of the FSW camera system, a summary of recommended practices, and ideas for future investigation.
The Making of the Official Counter-Strike Bot
Abstract: This lecture addresses the technical and design issues critical to the success of the official Counter- Strike bot, the most advanced FPS tactical multiplayer AI to date. The official Counter-Strike bot has received an enthusiastic reception from both newbies and veterans of the Counter-Strike community, largely due to the fact that it plays the game in a very believable, human-like fashion. The bots put on a "performance" that results in players feeling they are fighting against (and with) "worthwhile" opponents. Achieving this level of suspension of disbelief requires more than technical AI coding ability. It requires a thorough understanding of the game, insight into human limitations such as reaction times and attention prioritization, and a holistic sense of how to create a fun and believable "performance" from these disparate parts.
True Crime: Streets of L.A.-Bringing Crime to the City of Angels
Abstract: In the recently released game, True Crime: Streets of L.A., we created a 240 square mile city that players could explore from end to end. We then had to fill it with citizens and not a small amount of criminal activity. This session discusses the techniques we used and the problems we encountered in bringing the city to life. We needed to create a character system that would seamlessly blend innocent character behaviors with a complete fighting and shooting techniques. The design also relied heavily on both scripted and emergent behavior as a core part of gameplay both out in the city and in the interior set pieces. Showing the action also depended on the interaction of a variety of camera models. Key topics in the session will be character animation and behavioral AI, interaction between kinematic objects and the physics system, real-time cinematography, and collision detection and testing.
2003
Common Game AI Techniques
Topics: History, General; Genres: General
Abstract: This article provides a survey of common game AI techniques that are well known, understood, and widely used. Each technique is explained in simplest terms along with references for delving deeper. Techniques include A* Pathfinding, Command Hierarchies, Dead Reckoning, Emergent Behavior, Flocking, Formations, Influence Mapping, Level-of-Detail AI, Manager Task Assignment, Obstacle Avoidance, Scripting, State Machines, Stack-Based State Machines, Subsumption Architectures, Terrain Analysis, and Trigger Systems.
Promising Game AI Techniques
Topics: History, General; Genres: General
Abstract: This article provides a survey of promising game AI techniques that are on the forefront of game AI. Each technique is explained in simplest terms along with references for delving deeper. Techniques include Bayesian Networks, Blackboard Architectures, Decision Tree Learning, Filtered Randomness, Fuzzy Logic, Genetic Algorithms, N-Gram Statistical Prediction, Neural Networks, Perceptrons, Planning, Player Modeling, Production Systems, Reinforcement Learning, Reputation Systems, Smart Terrain, Speech Recognition and Text-to-Speech, and Weakness Modification Learning.
New Paradigms in Artificial Intelligence
Topics: General; Genres: General
Abstract: This article introduces some new ideas in the field of Artificial Intelligence (AI). Many researchers are looking more toward nature for inspiration, finding many useful design solutions to the problem of behaving in a dirty, noisy world. While traditional AI techniques (OldAI) have had much success in formal domains, such as chess, they often do not scale well and are sometimes impossible to apply in less discrete domains.
A better understanding of the techniques inspired by natural intelligence (NewAI) in addition to OldAI techniques will lead to a much more complete toolbox for an AI designer. This will allow agents to be designed to behave more naturally and a better understanding of why they fail in particular situations, leading to more believable motions and behaviors in games.
Artificial Stupidity: The Art of Intentional Mistakes
Topics: General; Genres: General
Abstract: What makes a game entertaining and fun does not necessarily correspond to making its opponent characters smarter. The player is, after all, supposed to win. However, letting a player win because of badly programmed artificial intelligence is unacceptable. Fun can be maximized when the mistakes made by computer opponents are intentional. By finely tuning opponent's mistakes, one can prevent computer opponents from looking dumb, while ensuring that the player is still capable of winning. Additionally by catching, identifying and appropriately handling genuine problems with an AI system, one can turn situations in which computer opponents would otherwise look dumb into entertainment assets. Surprisingly many game developers pay scant attention to such ideas. Developers' efforts are often so concentrated on making their computer opponents smart that they neglect to adequately address how the AI makes the game fun.
Arcade AI Doesn't Have to Be Dumb
Topics: General; Genres: General, Action
Abstract: Good game AI is tricky no write no matter what your resources are. When you're faced with limited CPU and RAM, such as with an arcade game or on a handheld, it can be nearly impossible. Arcade AI Doesn't Have to be Dumb covers various techniques used in the development of the Sega arcade game Behind Enemy Lines which helped give its AIs a bit more spontaneity and seeming intelligence than found in most shooters while not using up much memory or CPU in the process.
The Statistics of Random Numbers | |
Topics: General; Genres: General
Abstract: Random numbers are used most heavily by Artificial Intelligence and games in general. To ignore their potential is to make the game predictable and boring. Using them incorrectly can be just as bad as ignoring them outright. Understanding how random numbers are generated, their limitations and their capabilities, can remove many difficulties of using them in your game. This article offers insight into random numbers, their generation, and methods to separate good ones from bad.
Filtered Randomness for AI Decisions and Game Logic | |
Topics: General; Genres: General
Abstract: Conventional wisdom suggests that the better the random number generator, the more unpredictable your game will be. However, according to psychology studies, true randomness over the short term often looks decidedly unrandom to humans. This article shows how to make random AI decisions and game logic look more random to players, while still maintaining strong statistical randomness. Full source code, ready to drop into your game, is supplied on the book's CD-ROM.
Search Space Representations
Topics: Pathfinding; Genres: General
Abstract: Navigation in games is about much more than the search algorithm used. An equally important (and often overlooked) consideration is the way the game represents the game world to allow agents to perform a search on it (the "search space representation"). Different games have used nearly every kind of search space representation imaginable. This article discusses the relative strengths and weaknesses of square and hexagonal grids, quadtrees, corner graphs, waypoint graphs, circle/cylinder-based waypoint graphs, space-filling volumes, and triangle-based and N-sided-convex-poly-based navigation meshes for navigating in different types of games. We also discuss additional issues that may change the relative merits of different representations, such as the different movement capabilities of different units and the need to interact with a local pathfinding / dynamic obstacle avoidance system.
Inexpensive Precomputed Pathfinding Using a Navigation Set Hierarchy
Topics: Pathfinding; Genres: General
Abstract: The increasing use of precomputed navigation data in today's computer games has led developers to experience both the joys of lightning-fast best path determination and the agony of the memory cost associated with storing all that information. Often, the memory requirements are prohibitive - especially on console platforms - and much slower traditional solutions are required. In this article we present a hierarchical scheme that retains virtually all of the processing speed of the typical precomputed solutions, while dramatically reducing the memory requirements.
Path Look-up Tables - Small is Beautiful | |
Topics: Pathfinding; Genres: General
Abstract: The fastest way to "find" a path from waypoint A to B is not to search. It is much faster to look up a path from a pre-computed table. Being able to find paths ten to two hundred times faster than with A* may make a big difference. This frees up CPU budget for other AI decisions. It allows the use of paths and travel times in a much larger portion of the AI's reasoning. However, path lookup tables are not without disadvantages. The amount of memory required for the tables often prohibit their use for anything other than small levels.
This article discusses optimizations of path lookup tables, and takes a look at two designs that offer the performance benefits at lower costs. First, a path lookup matrix using indices that consumes only one fourth of traditional path lookup tables. Second, an area-based path lookup table which consumes even less, and scales much better, at the costs of a more complex lookup.
An Overview of Navigation Systems
Topics: Movement, Pathfinding; Genres: General
Abstract:
Jumping, Climbing, and Tactical Reasoning: How to Get More Out of a Navigation System
Topics: Movement, Pathfinding; Genres: General
Abstract: Few AI related systems are more common and pervasive in games than character navigation. As 3D game engines become more and more complex, characters will look best if they too adapt with equally complex behavior. From opening a door, to hopping over an errant boulder and crouching behind it, keeping AI tied to the environment of your game is often one of the most difficult and important challenges.
Typically these complex behaviors are handled by scripts or a hand coded decision maker. However, we will show that the points and edges within a navigation system are a natural place to store environment specific information. It is possible to automatically detect many properties about the area around a point or edge. This approach allows an AI character to make use of embedded environment information for tactical reasoning as well as low level animation and steering.
Hunting Down the Player in a Convincing Manner
Topics: Movement, Pathfinding; Genres: General
Abstract: This article is concerned with how to make a game character convincingly hunt or search towards a goal. Gamers expect intelligent behavior from opponents but sometimes it's all too easy to let the AI cheat a little too much. In order to bring about believable searching behavior it is often not sufficient to simply route a game character directly towards its goal; the path will be too direct, too contrived and generally afford little in the way of gameplay possibilities. We must ensure that the character explores and looks like it's trying to find its goal by a process of search rather than direct, shortest-path route following. This article shows how to do this effectively and with low processing cost. The end result is convincing searching and/or hunting behavior that gradually homes in on a goal.
Simple parameters are available to control how quickly goal discovery is likely to happen and also the directness of the resultant path. The method assumes the existence of a working pathfinding/routing system with the described technique being equally suited to 2D and 3D environments. The discussion will show the benefits and scope of indirect paths in terms of the opportunities offered for gameplay, perceived character intelligence and believability.
Avoiding Dynamic Obstacles and Hazards
Topics: Movement, Pathfinding; Genres: General
Abstract: Static obstacle avoidance is, barring efficiency considerations, a solved problem in games. The A* algorithm is generally used to search a graph data structure representing the navigable terrain in the level to find a route to a goal. However, many game agents still cope badly with dynamic obstacles encountered along the route, often relying entirely on collision code to get them out of trouble. Bumping into entities not only looks unintelligent, it can also have negative game-play implications, especially if the entity is a hazard.
This article outlines a pragmatic approach to solving this problem at the level of short-range movement. Inspired by flocking algorithms, the method involves taking an agent's desired velocity and adding "repulsion" vectors from nearby entities in the agent's memory. The resulting velocity will tend to send the agent around dynamic obstacles and hazards. A nice feature is that two agents on a collision course will intelligently sidestep in opposite directions in order to avoid each other. Moreover, the situation in which a short-range destination is completely blocked by an entity is detected early, so that a new long-range route can be found well before a collision has taken place. The approach is fast and produces very convincing avoidance behavior.
Intelligent Steering Using PID Controllers | |
Topics: Movement; Genres: Racing
Abstract: In order to achieve the realism demanded by many of today's games, physics simulations have become more complex and accurate. Although realistic physics simulations are often rewarding for human players to control, they can be frustrating from an AI programmer's perspective. As these simulations become more complex, the effects of a given input to the system become less clear, and it becomes more difficult to write a simple if...then...else logic tree to cope with every possible circumstance. Thus, new methods of controlling objects operating under these rules must be developed.
In the context of game AI, the primary use for such control is in the steering of objects operating under the constraints of a physics system. The article will detail a solution to this problem by applying an engineering algorithm known as a Proportional-Integral-Derivative (PID) Controller that has been used for over 50 years. The article comes with full source code to a demo that let's you interactively play with the PID variables that control a rocket steering toward a moving target.
An AI Approach to Creating an Intelligent Camera System
Topics: Movement, Camera; Genres: Action
Abstract: In this article, we will attempt to outline one method of implementing a camera system capable of handling a diverse and dynamic three-dimensional environment. We will detail the approaches taken during development of a to-be-released title, outlining the issues we encountered and how these were overcome.
Constraining Autonomous Character Behavior with Human Concepts
Topics: General; Genres: General, FPS
Abstract: A current trend in Game AI is the move from scripted to autonomous character behavior. Autonomous behavior offers several benefits. Autonomous characters can handle unexpected events that a script might not have anticipated, producing emergent gameplay. Level designers can focus on creating worlds packed with opportunities for characters to showcase their behaviors, rather than getting bogged down scripting the actions of individual characters. Various articles have described how to design goal-based autonomous behavior, where characters select the most relevant behavior based on their desires, sensory input, and proximity to objects of interest. In theory it sounds simple enough to drop a character with a palette of goals into a level filled with tagged objects, and let him take care of himself. In practice, there are many additional factors that need to be considered to get believable behavior from an autonomous character. This article presents a number of factors that should be considered as inputs into the relevancy calculation of a character's goals, in order to produce the most believable decisions. These factors are based on findings encountered during the developement of Monolith Production's No One Lives Forever 2: A Spy in H.A.R.M.'s Way.
Simple Techniques for Coordinated Behavior
Topics: Strategy, Tactical, Coordinated Movement, Cooperation; Genres: FPS, Action
Abstract: There are a number of common problems that arise when developing AI systems for combat with multiple enemies. Agents block each other�s line of fire. Agents follow the exact same path to a target, and often clump up at a destination. Some agents are oblivious to a threat while others nearby are getting shot or even killed. Multiple agents decide to do the exact same action or animation simultaneously. It would seem that a group behavior layer of complex higher-level reasoning would be needed to solve these problems. In fact, these problems can be solved with simple techniques that use existing systems and leverage information that individual agents already have. This article describes simple techniques that can be used to solve coordination problems, using examples from Monolith Productions' "No One Lives Forever 2: A Spy in H.A.R.M.'s Way."
Team Member AI in an FPS |  |
Topics: Strategy, Tactical, Coordinated Movement, Cooperation; Genres: FPS, Action
Abstract: The use of teammates has become very popular among the first and third person action genres in recent years, in both the simulation and arcade sub-genres. However, implementing convincing teammates who will not run in your path while you are shooting, nor disappear into a far corner of the map, is quite an involved process. By implementing some key rules it is possible to create teammates who can usefully back you up in the thick of the action, follow instructions reliably, and survive with you until the end of the game.
Applying Goal-Oriented Action Planning to Games
Topics: Strategy, Planning; Genres: Strategy, RTS, FPS, Action
Abstract: A number of games have implemented characters with goal directed decision-making capabilities. A goal-directed character displays some measure of intelligence by autonomously deciding to activate the behavior that will satisfy the most relevant goal at any instance. Goal-Oriented Action Planning (GOAP) is a decision-making architecture that takes the next step, and allows characters to decide not only what to do, but how to do it. A character that formulates his own plan to satisfy his goals exhibits less repetitive, predictable behavior, and can adapt his actions to custom fit his current situation. In addition, the structured nature of a GOAP architecture facilitates authoring, maintaining, and re-using behaviors. This article explores how games can benefit from the addition of a real-time planning system, using problems encountered during the development of Monolith Production's No One Lives Forever 2: A Spy in H.A.R.M.'s Way to illustrate these points.
Hierarchical Planning in Dynamic Worlds
Topics: Strategy, Planning; Genres: Strategy, RTS, FPS, Action
Abstract:
Goal Directed Behavior using Composite Tasks
Topics: Strategy, Planning; Genres: Strategy, RTS, FPS, Action
Abstract: This article will introduce the reader to goal directed behavior and offers several examples of games that have used it to increase the believability of the agents in those games. The article then goes on to discuss the implementation of the Composite Task concept that was designed and developed to provide goal directed behavior for the agents in a military tactical combat training simulator. Finally, the simulator itself is briefly discussed and references to additional information on goal directed behavior are provided.
Simplified Animation Selection
Topics: Animation; Genres: General
Abstract: This article describes an animation selection mechanism for determining the active animations of an arbitrary number of animation channels, based on a narrow set of discrete inputs and events, in a manner that's easy to manipulate for both artists and AI programmers. The system allows for just a few simple inputs (such as a character's cardinal movement direction, posture, weapon type, etc) and isolated triggered events (such as waves or taunts) to determine the entire animation state of a character at a given time, even in the presence of hundreds of animations.
The animation channels, input names and values, and control-flow "actions" are all configurable via a simple artist-friendly scripting language, allowing the artist to take nearly full control over the animation selection pipeline. In addition, the AI programmer's job is made easier due to the simplified conduit between a character's abstract behavior and its animation inputs. The result is an animation selection scheme that gives the artist a level of control usually only available to programmers, without losing the simplicity and flexibility of other data-driven approaches.
Pluggable Animations
Topics: Animation; Genres: General
Abstract: This article discusses an extensible plug-in based animation pipeline that combines the handling of pre-built and dynamically-generated animation facilities into a single unified mechanism. This allows artists and AI programmers to take advantage of procedural animation effects in the same manner as regular animations, adding an additional level of flexibility and control to the look of your characters.
Animations are created based on a set of "abilities" that activate and deactivate at different points in time within the animation's length. These abilities can perform any number of effects on the character, from a simple application of pre-built animation frame data, to a complex on-the-fly Inverse Kinematics operation using external "satellite" points in space provided by an external source, to esoteric visual effects like bone attachment manipulation and vertex deformation. The abilities themselves are provided as plug-ins, and new abilities can be added during the development process (or in some cases even afterward, by "mod" authors) without changing the core of the animation pipeline. The process of creating of these kinds of animations can be made friendly to artists without much effort, via a simple GUI dialog box based primarily around a single list view control.
Intelligent Movement Animation for NPCs
Topics: Animation; Genres: General
Abstract: This article describes an intelligent movement animation system for non-player characters (NPCs). This system is used in the PC and PS2 versions of Fellowship of the Ring and two upcoming games from Surreal Software. First, the article briefly explains steering behaviors and animation systems. Next, it describes the middle layer between them. This layer includes a system for NPC movement, a movement animation behavior, and an animation controller. The movement animation behavior ensures that the animation being played and the way it is being played are appropriate, given the NPC's current movement. The animation controller provides a simple high-level interface to the underlying animation system. Finally, the article also gives some tips on gotchas that can come up during implementation of the middle layer and some ideas for further enhancements.
The Ultimate Guide to FSMs in Games | |
Topics: State Machines; Genres: General
Abstract: The intention of this article is to give a comprehensive overview of FSMs in games. This article examines various FSM architectures and discusses the systems that surround them. The FSM is studied at the game integration level, the update scheme, and efficiency/optimization. Extensions are discussed for extending state functionality (OnEnter, OnExit), extending the structure into hierarchical and fuzzy state machines, and coordinating multiple FSMs. Various FSM schemes are compared and contrasted.
Stack-Based Finite-State Machines
Topics: State Machines; Genres: General
Abstract: Finite-state machines are a very popular technique for developing game AI, but they lack any intrinsic capability for remembering the way a client has traversed the state graph. We discuss a technique for extending the traditional finite-state machine with a state stack in order to allow it to remember previous states, thereby allowing AI agents to resume the execution of behaviors that were previously interrupted. In some cases, such as modeling behaviors with an FSM, this can often allow us to create much simpler and more concise finite-state machines than would be possible with a standard FSM.
Implementing a Data-Driven Finite-State Machine | |
Topics: State Machines; Genres: General
Abstract: This article describes an implementation of a data-driven Finite State Machine (FSM) class. Using a data-driven design allows quick tweaking of state transition logic without having to recompile any source code, as well as the ability to associate different character behavior to different AI characters through external data files. The FSM class presented in this article instantiates FSMs as defined in external data files, automates the evaluation of state transition logic and provides the functionality to define functions to be executed when entering, updating, and exiting states.
Finite-State Machine Scripting Language for Designers | |
Topics: State Machines, Scripting; Genres: General
Abstract: AI is often implemented with finite state machines (FSM's) or layers of finite state machines, which are difficult for game designers to edit. Looking at typical AI FSM's, there are design patterns that occur repeatedly. We can use these patterns to make a custom scripting language that is both powerful and approachable. The technique can be further extended into a "stack machine" (pushdown automata) so that characters have better memory of previous behaviors.
A Subsumption Architecture For Character-Based Games
Topics: Architecture; Genres: Action
Abstract: The Subsumption Architecture was invented in 1986 by Rodney Brooks to give robust real-world behavior to robots. The technique works equally well for the "virtual robots" of the video game world. It cleanly decomposes the implementation of an AI driven character into concurrently executing layers of finite state machines (FSMs). Lower layers take care of immediate goals; upper layers take care of long-term goals. The architecture solves three major problems with character AI: minor setbacks causing a character to lose focus on a long term goal, characters getting stuck on a goal that is no longer relevant, and robust handling of animation and character physics.
An Architecture for A-Life | |
Topics: Architecture, A-Life; Genres: General
Abstract: This chapter presents Insect AI, a straight forward architecture, notation, and design methodology for artificial life. The principles and techniques are derived from neuroethology, the study of neural control of behavior. Simple computational units are introduced and examined, and the creation of Insect AI agents is demonstrated. Insect AI agents exhibit a number of interesting properties which satisfy the characteristics of motivated behavior as defined in the ethological literature - behaviors can be grouped and sequenced, the agents are goal directed, behavior can change based on the internal state of the agent, and behaviors can persist if stimuli are removed. A number of agents are created as examples, ranging from a simple light follower to an artificial insect that shows all the characteristics of motivated behavior.
A Flexible Tagging System for AI Resource Selection
Topics: Architecture, NLP; Genres: General
Abstract: As game designs increasingly evolve away from linear, scripted gameplay experiences and toward open-ended worlds and gameplay based on emergent behaviors, gameplay has become much less predictable, and it has become increasingly difficult to create content that exactly matches the specific situation the user will experience at any given moment. Although in an ideal world, it would be possible to create content that responds to all of the different possible game states, open-ended game designs present far too many unpredictable situations, and one can never hope to create enough audio or animation content to handle all of them. However, it is possible to fit some of the specifics of the situation some of the time, and create content at varying levels of specificity. We present a flexible tagging system that allows you to create art and audio content across a wide spectrum from the most general to the most specific, along with a simple resource-selection algorithm that allows you to select the most situation-specific piece of content to use in any given situation. We also discuss potential applications of this system for audio and animation assets in detail.
Motivational Graphs: A New Architecture for Complex Behavior Simulation | |
Topics: Architecture; Genres: General
Abstract: Recent research in cognitive science and ethology has led to the development of biologically-inspired autonomous behavior models. Such models differ from classical AI models since they account for both internal state and environmental constraints. They define a new generation of systems, closer to Artificial Life and situated cognition than to classical AI.
In the present article, we introduce a new architecture based on such models. Applied to game development, this architecture enables designers and developers to easily describe, model and implement realistic autonomous software agents. This architecture, called a motivational graph, is a hybrid between rule-based approaches and connectionist systems. Especially, it uses concepts such as activity propagation to trigger modules within a hyperconnected graph. In this article, we demonstrate the benefits of this approach: multitasking, opportunism, tradeoff and emergence.
Minimizing Agent Processing in Conflict Desert Storm
Topics: Architecture; Genres: General
Abstract:
Using a Spatial Database for Runtime Spatial Analysis
Topics: Architecture; Genres: FPS
Abstract: AI developers have employed a number of different techniques for performing spatial reasoning about a game world using precomputed "hints" placed by level designers or automated game-world analysis tools. However, as game worlds increasingly feature larger numbers of AI characters and moveable physically-modeled objects, it becomes increasingly important to model the ways that the dynamic aspects of the ever-changing game world influence an AI's spatial reasoning. We discuss a spatial database technique that allows you to perform spatial reasoning about any number of different factors that can potentially affect an AI agent's reasoning about the game environment and techniques for combining multiple factors together to construct desirability heuristics. A spatial database can also allow you to implicitly coordinate the activities of multiple AI agents simply by virtue of sharing the same data structure.
Performing Qualitative Terrain Analysis in Master of Orion 3 | |
Topics: Strategy, Tactical, Terrain Analysis; Genres: Strategy, RTS
Abstract: One challenge for many strategy game AIs is the need to perform qualitative terrain analysis. By qualitative we mean that the analysis is based on fundamental differences between different types of locations - for instance areas that are visible to our opponents, areas that are impassible, or areas vulnerable to enemy fire. In Master of Orion 3 we identify stars that are inside or outside of our empire's borders, those that are threatened by our opponents, and those that are contested (shared with an opponent). This information is used to identify locations where we need to concentrate our defenses and to help us expand into areas that minimize our defensive needs while maximizing the territory we control.
In this article we will present the algorithms used to make the qualitative distinctions given above and the ways in which the AI uses that information. The lessons we would most like the reader to take away from this article are not the specifics of the algorithms used but rather the thought processes involved in applying qualitative reasoning to terrain analysis. The important questions to address are: what are the qualitative distinctions we should look for, how can we recognize them, and what uses can the AI make of that information. Our algorithms are but a single example of how these questions can be answered.
The Unique Challenges of Turn-Based AI
Topics: Strategy, Tactical; Genres: Strategy
Abstract: Writing a turn-based AI presents a number of unique programming and game design challenges. The common thread uniting these challenges is the user's complete control over the game's speed. Players willing to invest extreme amounts of time into micro-management and players looking to streamline their gaming experience via automated decision-making present two very different problems for the AI to handle. Further, the ability to micro-analyze turn-based games makes predictability, cheating, and competitive balance extremely important issues. This article outlines how the Civilization III development team dealt with these challenges, using specific examples to illuminate some practical solutions useful to a programmer tasked with creating an AI for a turn-based game.
Random Map Generation for Strategy Games
Topics: Strategy; Genres: Strategy, RTS
Abstract: While there are numerous articles dedicated to the generation of random maps for games, there is little published information on random maps for strategy games in particular. This subset of map generation presents distinct challenges as evident by the relatively few games that implement them. While the techniques described here can be used to create maps suitable for any type of game, this system is specifically designed to create a variety of successful random maps for real-time strategy games. This article describes the random map generation implementation as found in the RTS game Empire Earth (EE) developed by Stainless Steel Studios.
Transport Unit AI for Strategy Games
Topics: Strategy, Tactical; Genres: Strategy, RTS
Abstract: Unit AI refers to the micro-level artificial intelligence that controls a specific unit in a game and how that unit reacts to input from the player and the game world. Transports present a particular challenge for unit AI as many units must work together to achieve their common goal, all the while attempting to minimize player frustration. This article discusses the general transport unit AI challenge and a successful solution. Land, air, naval, and building transports (such as fortresses and town centers) will be discussed and a class hierarchy implementation will be suggested. Algorithms for the loading (including the calculation for rendezvous points) and unloading of transports will be presented as well as warnings for particular pitfalls.
This article assumes some sort of finite-state-machine-based unit AI system and is applicable to any game in which there are multiple units in need of transporting. This article details the transport unit AI as found in the Real-Time Strategy (RTS) game Empire Earth (EE) developed by Stainless Steel Studios.
Wall Building for RTS Games | |
Topics: Strategy, Tactical; Genres: RTS
Abstract: Most real-time strategy games include walls or similar defensive structures that act as barriers for unit movement. Having a general-purpose wall-building algorithm increases the competitiveness of computer opponents and provides a new set of options for the random mission generation. The article discusses a wall building algorithm that uses the greedy methodology to build a wall that fits the definition, protects the desired location, and meets the customizable acceptance criteria. The algorithm takes advantage of the natural barriers and map edges to minimize the cost of building a wall. The algorithm discussion focuses on importance of traversal and heuristic functions, details of implementation, and various real world problems. Advanced topics such as minimum/maximum distance requirements, placement of gates and an unusual wall configurations are elaborated on. Full source code and a demo are supplied.
Strategic Decision-Making with Neural Networks and Influence Maps | |
Topics: Strategy, Tactical; Genres: Strategy, RTS
Abstract: Influence maps provide a strategic perspective in games that allows strategic assessment and decisions to be made based on the current game state. Influence maps consist of several layers, each representing different variables in the game, layered over a geographical representation of the game map. When a decision needs to be made by the AI player, some or all of these layers are combined via a weighted sum to provide an overall idea of the suitability of each area on the map for the current decision. However, the use of a weighted sum has certain limitations.
This article explains how a neural network can be used in place of a weighted sum, to analyze the data from the influence map and make a strategic decision. First, this article will summarize influence maps, describe the current application of a weighted sum and outline the associated advantages and disadvantages. Following this, it will explain how a neural network can be used in place of a weighted sum and the benefits and drawbacks associated with this alternative. Additionally, it will go into detail about how a neural network can be implemented for this application, illustrated with diagrams.
Multi-Tiered AI Layers and Terrain Analysis for RTS Games
Topics: Strategy, Tactical, Terrain Analysis; Genres: Strategy, RTS
Abstract: RTS games tend to handle soldier AIs individually, giving each unit specific tasks from the computer player. Creating complicated, cooperative tactics are impossible for such systems without an immense effort in coding. To develop complex, large-scale plans, a mechanism is needed to reduce the planning devoted to the individual units. Some games already collect individual soldiers into squads. This reduces the planning necessary by a factor of ten, as one hundred soldiers can be collected into ten squads. However, this concept can be taken farther, with squads collected into platoons, platoons into companies, and so on. The versatility such groupings give an AI system are immense. This article will explore the implementation of a multi-tiered AI system in RTS-type games, including the various AI tiers, a set of related maps used by the AI tiers and an example to illustrate the system.
Designing a Multi-Tiered AI Framework | |
Topics: Strategy, Tactical; Genres: Strategy, RTS
Abstract: The MTAIF allows an AI to be broken up into three concrete layers, strategic, operational and a tactical layer. This allows for an AI programmer to have various AIs focus on specific tasks, while at the same time having a consistent overall focus. The MTAIF allows for the strategic layer to be focused exclusively on matters that can affect an empire on a holistic scale, while at the operational level the AI is in tune with reports from the tactical level. A differing factor from many other architectures is that the MTAIF does not allow decisions to be made on a tactical scale that would violate the overall strategic policies. This in turn forces highlevel strategic policies to be enforced in tactical situations, without the AI devolving into a reactionary based AI.
Racing Vehicle Control using Insect Intelligence
Topics: A-Life; Genres: Racing
Abstract: Despite their simplicity and inability to adapt by learning, insects and other simple animals manage to survive and navigate in the complex and unpredictable real world very well. Since evolution tends to find very efficient solutions to the problems faced by living creatures a lot of the mechanisms used by simple animals are relatively efficient, and in addition often have a potential for behavioral richness far beyond the extra processing power it takes to model them.
This article presents a robust and extensible system architecture which is based around emergent behaviors, and several techniques which utilize principles derived from the results of academic AI research into modeling insect level intelligence - in particular vision based steering behavior utilizing simple compound eye-like sensors.
Fast and Efficient Approximation of Racing Lines | |
Topics: General; Genres: Racing
Abstract: Racing game AI has developed to the point where it is able to challenge even the best players. To do this, an AI usually relies heavily on information stored along the length of a track, which provides it with instructions on how it should approach upcoming sections. Critically, this information is derived during a game's development, almost always from the way in which human players drive each track, and will therefore not be available for random or player created tracks. This prevents random track generators and track editors being shipped with many racing games, because it would not also be possible to provide a challenging AI that could compete against the player on all the resulting tracks. This article presents an algorithm that can be used to quickly and efficiently derive approximations to racing lines, thus providing information vital to an AI. A demonstration implementation of the algorithm in C++ is included with the article.
The Art of Surviving a Simulation Title
Topics: General; Genres: Racing
Abstract: This article aims to simplify the task of writing simulation AI by providing a number of guidelines. These were adopted after working on the space simulation, "Independence War 2" (I-War 2) and continue to bring success to the futuristic racing game, "Powerdrome". The guidelines cover many aspects from higher-level design and keeping it simple to diagnostic support and impressing the user. While they far from guarantee a successful and stress free implementation, they at least put the developer on the right path.
Dead Reckoning in Sports and Strategy Games
Topics: General; Genres: Sports, Strategy, RTS
Abstract: Dead reckoning is a set of techniques used to calculate the motion of objects not entirely within an agent's control. This article explores the equations required to implement dead reckoning, and shows how it can apply in a variety of game contexts, for example the calculation of the optimal trajectory for a pass or a shot in a sports simulation, as well as multiple wargame problems.
Building a Sports AI Architecture
Topics: General; Genres: Sports, Basketball
Abstract: This article focuses on the sport of basketball; however, the concepts presented in the article are applicable to a wide variety of games. The goal of the article is to give the reader a solid understanding about the things to consider when designing an architecture for a sports game. The article also describes the concepts and critical components necessary to successfully design an AI system that is easy to understand, build, maintain and extend.
The article covers, in detail, the concepts of agent plans, team management, agent AI, and touches on the critical points of agent mechanics. The architecture presented in the article serves as the foundation for Microsoft's NBA Inside Drive franchise and has been used in three shipped versions of the game.
Optimized Script Execution
Topics: Scripting; Genres: General
Abstract: The slow speed with which script languages are executed (compared to native code) places many limitations on a script language's potential applications. Previously only infrequently executed code placed outside of the game's inner loops has been deemed suitable for scripting, and for this reason script languages have typically only been used for story telling or customizable event-handling purposes.
Using optimization techniques presented in this article, it possible to increase script execution efficiency to near-native performance levels, enabling the use of scripting in the game's core logic, or even in a high performance 3D rendering system. The flexibility gained from switching to script-based logic means that even modifying a program's innermost mechanics is trivial, and does not come with the performance penalties one would expect.
Three stages of script execution are individually examined, and optimizations for each are presented. The techniques and principles presented can be easily applied to any existing scripting engine.
Advanced Script Debugging
Topics: Scripting; Genres: General
Abstract: Poor or missing script debugging facilities are among the principal reasons for scripts not being fully exploited in a development environment. Often, errors encountered during script execution result in crashes of the game or a "screen of death" style representation of the virtual machine's internal state just after the crash has occured.
In-depth knowledge of the virtual machine is required to interpret such information, and often the virtual machine's source code needs to be examined in order to identify the problem, which may have been caused by a virtual machine command executed long before the crash. Because all external developers (including the mod community) and most in-house script programmers lack this in-depth information, they will restrict their programming style to simple constructs that can be fixed using a trial and error process in case of a problem. Therefore even the most powerful script languages are doomed to be misused if they do not support proper debugging mechanisms.
This article shows how to incorporate known debugging capabilities from common development environments into your script system, giving your script designers and the mod community the ability to create complex scripts and use the language to its full extent, while also shortening the development period because of improved debugging capabilities for scripts.
Adding Error Reporting to Scripting Languages | |
Topics: Scripting; Genres: General
Abstract: Custom scripting languages are a controversial game development tool. Scripting languages empower non-programmers by moving game AI logic out of the C++ code. While this empowerment certainly comes with some risks, the benefits are that additional team members can create behaviors, designers can tweak AI more directly, and the AI logic is more accessible to the mod community. The most common complaint about scripting languages is that they are difficult to debug. This concern is exacerbated if non-programmers intend to write scripts. If the scripting language compiler or interpreter only gives feedback like "syntax error," non-programmers are not going to get very far. Fortunately, this problem is easily solved. The same techniques used to define the grammar of valid syntax can be used to identify and report scripting errors in plain English. This article describes how to harness the power of Lex and Yacc to generate meaningful errors when compiling scripts. The article includes C++, Lex, and Yacc code for a simplistic language called Simple.
Empowering Designers: Defining Fuzzy Logic Behavior through Excel-Based Spreadsheets | |
Topics: Scripting, Fuzzy Logic; Genres: Sports, Baseball
Abstract: Putting game development back into the hands of the game's designers is critical to keeping a project on schedule. How does that happen? What is the easiest way to let a game designer work on their own with a minimum amount of interaction from a technical source? Using Visual Basic for Applications and some basic applications, it is possible to design an interface which does both of these things, as well as having the added benefit of letting finished code stay finished.
A Modular Camera Architecture for Intelligent Control | |
Topics: Scripting, Camera; Genres: General
Abstract: Cameras play a vital role in the user experience of any game. A robust camera solution can make the difference between a game that is awkward to play and a game that plays smoothly and feels great. Unfortunately, cameras tend to be a low priority item in many game development schedules and the effort is limited to the point where the cameras stop being a nuisance. One of the reasons that the efforts stop early is the lack of a solid architecture that allows rapid, data driven experimentation with camera behaviors.
This article presents a component based camera architecture that allows non-programmers to take over the development of cameras at the point where they make the transition between technical coding and creative effort. The architecture will demonstrate the use of common AI techniques to enhance the robustness and creativity of the camera solution for any game. The techniques presented in the article will primarily benefit games that have a third-person perspective, but will also provide useful tips for other types of games.
Player Modeling for Adaptive Games
Topics: Learning; Genres: General
Abstract: This article describes a lightweight, flexible machine learning technique we call player modeling, designed to help add adaptivity to your game AI. The basic idea is simple: the game maintains a profile of each player that captures the skills, weaknesses, preferences, and other characteristics of that player. This model is updated by the game as it interacts with the player. In turn, the game AI can query the player model to determine how best to adapt its behavior to that particular player - for example, by asking which of several possible tactics will be most challenging to the player. Using player modeling, a game's AI can adapt both during the course of a single play as well as over multiple sessions, resulting in a computer opponent that changes and evolves with time to suit the player.
The article first defines the player model concept in more detail and then discusses strategies for designing a model to suit your game. It then presents a basic player model implementation. Subsequent sections describe how to actually integrate the modeling system with your game, including both how to update the model and how to make use of the information that it contains. The remainder of the article presents several advanced concepts, including a hierarchical player model, alternate model update methods, and other uses for the player model.
Constructing a Decision Tree Based on Past Experience | |
Topics: Learning, Decision-Trees; Genres: General
Abstract: In recent years, decision trees have gained popularity within the game development community as a practical learning method that can help an AI adapt to a player. Instead of picking from a canned set of reactions to player action, the AI has the opportunity to do something much more powerful: anticipate the player's action before he acts. In this article, we discuss a decision tree learning algorithm called ID3, which constructs a decision tree that identifies the telltale features of an experience to predict its outcome. We then establish ID3's role in Black & White, building on an earlier article in the first edition of AI Game Programming Wisdom. Finally, we consider some important aspects and extensions to the approach, and provide s ample code which implements a simple form of ID3.
Understanding Pattern Recognition Methods
Topics: Learning; Genres: General
Abstract: The task of pattern recognition is to abstract relevant information from the game world and, based on the retrieved information, construct concepts and deduce patterns for the use of higher level reasoning and decision-making systems. We view pattern recognition in computer games from two perspectives: functional and methodological. In the functional approach, we analyze what is required from pattern recognition. We conclude that it can act in different roles, which in turn affect the choice of a method and its implementation. These roles depend on the level of decision-making, the stance toward the player, and the use of the modeled knowledge. In the methodological approach, we review a branch of pattern recognition techniques arising from soft computing. We discuss methods related to optimization, adaptation, and uncertainty. Our intention is to clarify where these methods should be used.
Using Reinforcement Learning to Solve AI Control Problems | |
Topics: Learning; Genres: General
Abstract: During the development of a game's AI many difficult and complex control problems often have to be solved. How should the control surfaces of an aircraft be adjusted so that it follows a particular path? How should a car steer to follow a racing line? What sequences of actions should a real time strategy AI perform to maximize its chances of winning? Reinforcement learning (RL) is an extremely powerful machine learning technique that allows a computer to discover its own solutions to these types problems by trial and error. This article assumes no prior knowledge of RL and introduces the fundamental principles of it by showing how it can be used to allow a computer to learn how to control a simulated racing car. C++ source code for RL and a skeleton implementation of racing game AI are included with the article.
Getting Around the Limits of Machine Learning
Topics: Learning; Genres: General
Abstract: To some AI programmers, the Holy Grail of AI would be a game that learns in the field and gets better the more it is played. Multiplayer network games especially would become challenging to the most skillful players as the AI learns and uses the best plays from the best players. This article examines some of the limitations of machine learning and some of the ways around them. It analyzes learning in three current games. It considers technical and gameplay issues with learning in games.
How to Build Neural Networks for Games | |
Topics: Neural Networks, Learning; Genres: General
Abstract: Neural networks are a machine learning technique inspired by the human brain. They are a flexible technique that has a wide range of applications in a variety of industries. This article will first introduce neural networks, describing their biological inspiration. Then, it will describe the important components of neural networks and demonstrate how they can be implemented with example code. Next, it will explain how neural networks can be trained, both in-game and prior to shipping, and how a trained neural network can be used for decision-making, classification and prediction. Finally, it will discuss the various applications of neural networks in games, describing previous uses and giving ideas for future applications. Each of these sections will be illustrated with relevant game examples and sample code where appropriate.
How to Build Evolutionary Algorithms for Games | |
Topics: Genetic Algorithms, Learning; Genres: General
Abstract: Evolutionary algorithm is the broad term given to the group of optimization and search algorithms that are based on evolution and natural selection, including genetic algorithms, evolutionary computation and evolutionary strategies. Evolutionary algorithms have many advantages, in that they are robust search methods for large, complex or poorly-understood search spaces and nonlinear problems. However, they also have many disadvantages, in that they are time-consuming to develop and resource intensive when in operation. This article will introduce evolutionary algorithms, describing what they are, how they work, and how they are developed and employed, illustrated with example code. Finally, the different applications of evolutionary algorithms in games will be discussed, including examples of possible applications in different types of games.
Adaptive AI: A Practical Example | |
Topics: Genetic Algorithms, Learning; Genres: General
Abstract: Because most game AIs are either hared-coded or based on pre-defined scripts, players can quickly learn to anticipate how the AI will behave in certain situations. While the player will develop new strategies over time, the AI will always act as it did when the box was opened, suffering from strategic arrested development. This article describes the adaptive AI of a simple turn-based game called "Advanced Protection."
This practical example of an adaptive AI displays a number of advantages over a static AI. First, the system can dynamically switch between strategies depending on the actual performance of the player - experts will be treated like experts, and novices will be treated like novices. Next, the rules and parameters of the game will be exactly the same for all strategies, which means the AI will not need to "cheat" in order to challenge expert players. Finally, the system can ensure that the AI's "best" strategies truly are the best for each individual player.
Building Better Genetic Algorithms | |
Topics: Genetic Algorithms, Learning; Genres: General
Abstract: Genetic algorithms are slowly but surely gaining popularity with game developers. Mostly as an in-house tool for tweaking NPC parameters such as ID used in the development of the bots for Quake3, but we are also beginning to see genetic algorithms used in-game, either as an integral part of the gameplay or as an aid for the user.
Unfortunately, many of today's programmers only know the basics of genetic algorithms, not much beyond the original paradigm devised by John Holland back in the mid sixties. This article will bring them up to date with some of the tools available to give improved performance. Techniques discussed will include various scaling techniques, speciation, fitness sharing, and other tips designed to help speedy convergence whilst retaining population diversity. In short, showing you how to get the most from your genetic algorithms.
Advanced Genetic Programming: New Lessons From Biology
Topics: Genetic Algorithms, Learning; Genres: General
Abstract: Genetic programming is a powerful evolutionary mechanism used to create near-optimal solutions to difficult problems. One of the major issues with traditional GP paradigms has been the relative brittleness of the organisms generated by the process: many source code organisms do not compile at all, or produce other kinds of nonsensical results. Recent advances in genetic programming, namely the grammatical evolution scheme based on such biological concepts as degenerate and cyclical DNA and gene polymorphism, promise ways to eliminate this problem and create programs that converge on a solution faster. This article explains grammatical evolution, its biological underpinnings, and a handful of other ways to refine evolutionary computing schemes, like co-evolution
The Importance of Growth in Genetic Algorithms
Topics: Genetic Algorithms, Learning; Genres: General
Abstract: The purpose of this article is to introduce some newer concepts relating to the field of Genetic Algorithms (GA). GAs can introduce variability and adaptability into a game leading to non-linear gameplay and opponents who tailor their strategies to that of the player. Many limitations of mainstream GA implementations can be overcome with some simple additions. Using growth, co-evolution, speciation and other new techniques can alleviate limitations on complexity, designer bias, premature convergence and many more handicaps. These additions can reduce the disadvantages of current GAs and allow the advantages to make games much more unpredictable and challenging.
SAPI: An Introduction to Speech Recognition | |
Topics: NLP; Genres: General
Abstract: This article looks at providing newcomers to SAPI an easy-to-follow breakdown of how to get a simple SAPI application working. It looks briefly at setting up SAPI, how to construct the XML grammar files, handling SAPI messages and using the SAPI text-to-speech functionality. All these concepts are tied together using an demonstration application designed to make learning SAPI simple yet entertaining.
SAPI: Extending the Basics | |
Topics: NLP; Genres: General
Abstract: This article extends upon the previous one by discussing concepts like dynamic grammar, additional XML grammar tags, altering voices and more SAPI events. The chapter uses a simple implementation of Go Fish! to demonstrate the concepts presented.
Conversational Agents: Creating Natural Dialogue between Players and Non-Player Characters
Topics: NLP; Genres: General
Abstract: The quality of interactions between non-player characters (NPCs) and the player is an important area of Artificial Intelligence in games that is still in need of improvement. Game players frequently express that they want to see opponents and NPCs that appear to possess intelligence in games. However, most dialogue between players and NPCs in computer games is currently scripted, which does not add to the appearance of intelligence in the NPC. This article addresses these problems by giving an overview of NPCs in current games and presents a method called conversational agents, for improving dialogue between players and NPCs. Conversational agents are software agents that consist of models of personality and emotion, which allow them to demonstrate believable conversational behavior. The advantages of conversational agents include their ability to portray emotions and personality through dialogue. However, they also have disadvantage, in that they can be time consuming to develop.
This article will begin by discussing the conversational behavior of NPCs in current games. We will not be looking at the artificial intelligence (AI) capabilities of NPCs, only their ability to interact with the player. We will then discuss the components of a conversational agent - how to give it the appearance of personality and emotion. We will also look at the input that the agent needs to get from the environment, and what we want the agent to say to the player. We will conclude with the advantages and disadvantages of using conversational agents in games.
An Introduction to Lua
Ash Matheson (Center for Digital Imaging and Sound (CDIS), Burnaby, BC, Canada)
GameDev.net, 2003.
Topics: Scripting; Genres: General
Abstract: This article describes how to add the scripting language Lua to your game engine. Lua is becoming
more popular for game scripting in commercial games and this article attempts to break down the barriers
to getting it working within your own codebase.
Game Balance and AI using Payoff Matrices
John M. Olsen (Microsoft)
Massively Multiplayer Game Development, 2003.
Topics: General; Genres: RTS, RPG, MMP
Abstract: Game balance can be a very thorny issue and can require a huge investment of time to get right.
In an MMP game environment, there is little margin for error; players have an amazing ability to work
together to find and use even the smallest of advantages. In this environment, there are as many approaches
to game balance as there are games. This article will present a way to use statistical analysis and some
straightforward mathematics to simplify the job of balancing certain portions of games, and use the same
techniques to make sure your Artificial Intelligence (AI) routines are taking advantage of the opportunities
available to them.
Building a Reputation System: Hatred, Forgiveness, and Surrender in Neverwinter Nights
Mark Brockington (Bioware Corp.)
Massively Multiplayer Game Development, 2003.
Topics: General; Genres: RPG, MMP
Abstract: The designers and programmers of Neverwinter Nights (NWN), a multiplayer Dungeons and Dragons type
role-playing game for IBM PC-compatible machines, had grandiose goals when it came to the AI engine. This article
discusses the evolution of our reputation system into the sub-system that throbs deep inside the bowels of NWN
today. The article will cover four topics in the chronological order that they were addressed: friendship and hatred,
forgiveness, surrender, and player-versus-player settings.
Creating a 'Safe Sandbox' for Game Scripting
Matthew Walker (NCsoft Corporation)
Massively Multiplayer Game Development, 2003.
Topics: Scripting; Genres: General, MMP
Abstract: The technical and support demands of Massively Multiplayer (MMP) games require a robust server
architecture. Yet, the nature of regular, dynamic content development risks introducing bugs that can
open opportunities for exploits or can unbalance the game. One way to mitigate this risk is to build
a 'safe sandbox' within which game designers can write code that realizes their creative intent while
insulating them from sensitive subsystems. This article explores how to create such a sandbox using the
high-level programming language, Python, to implement an encapsulated, event-driven environment that lets
designers safely focus on gameplay as their first priority.
Parallel-State Machines for Believable Characters
Thor Alexander (Hard Coded Games)
Massively Multiplayer Game Development, 2003.
Topics: State Machines; Genres: General
Abstract: This article focuses on the use of parallel sets of state machines in order to control an AI character.
The three parallel state machines include a movement layer, a posture layer, and an action layer.
Screaming at the Machine: Using Speech Recognition as a Complement to Traditional Game Input Technique
Dave Bartolomeo (Microsoft)
Game Developers Conference Proceedings, 2003.
Topics: NLP; Genres: General
Abstract: Advances in speech recognition technology, gigahertz CPUs, and the offloading of graphics
processing to the GPU have made it practical to use speech recognition in commercial-quality
games. The characteristics of speech recognition make it a unique input device, significantly
different from a mouse, keyboard, or joystick. Speech is more flexible than keyboard commands,
easier to use than multi-level menus, and it enables players to issue commands without moving
their focus away from the primary game interface. This talk demonstrates how to incorporate
speech recognition into your game in a way that complements traditional input devices, rather
than trying to replace them.
Sandbox Strategy Learning in Sports Games
Topics: Learning; Genres: Sports
Abstract: The illusion of intelligence is most easily destroyed by predictable or static behaviour. The ability for game characters to learn and adapt to the game player's actions will become increasinly important as the AI in games develops. Yet in many games, specifically in all sports simulation games, the AI must be kept in a "sandbox": It should not potentially evolve into nonsensical territory. This lecture focuses on a strategy learning experiment as part of an AI architecture under design in collaboration with Electronic Arts for their series of sports games.
Representational AI Planning Techniques
Charles Martin (University of Chicago)
Game Developers Conference Proceedings, 2003.
Topics: Architecture, Planning; Genres: General
Abstract: This talk presents representational AI planning techniques and how they can be layered on top
of existing game AI. These techniques explicitly manipulate representations of the world to
simulate and choose between alternative behaviors. This is contrasted with situational AI
techniques, in which behaviors depend directly on the current state. The exciting work in
game AI over the past couple of years remains primarily situational. These techniques will
always be crucial to maintaining a satisfying real-time play experience. By layering
representational planning over situational AI, we can hope to develop a more satisfying
through-line, more strategic behavior, better in-game understanding of the player experience,
and richer design vocabularies for building better games. This talk covers the essential
elements of representational planning techniques, motivated by specific game examples,
and documented with references and resources for further exploration.
Pathematics: Routing for Autonomous Agents
Alex J. Champandard (AI-Depot)
Game Developers Conference Proceedings, 2003.
Topics: Pathfinding, Movement; Genres: General
Abstract: As game AI becomes more complex, both its dependency and expectations of the navigation system
will increase. Dynamic conditions, moving obstacles and changing terrains are slowly becoming
commonplace, which the standard A* model has trouble coping with. These flaws are pointed out,
giving reasons for discarding the awkward single-pair paradigm along with the inflexible concept
of search. In this lecture, dynamic navigation systems are studied, with an especial focus on
planning. A radically new solution is proposed, redefining the way paths are requested and followed
as well as the underlying process. The result is a simple, flexible solution that can provide
dynamic level of detail path-planning with incredibly human-like motion in a surprisingly efficient
fashion.
Building AI Sensory Systems
Tom Leonard (Valve Software)
Game Developers Conference Proceedings, 2003.
Topics: Sensory, General; Genres: General
Abstract: This presentation examines the process and value of constructing AI sensory systems from gathering
requirements from game design to delivery. Efficient, high-fidelity AI sensory models can be an
invaluable tool for improving a game player's experience, enabling game designers and programmers
to construct more interesting gameplay scenarios. A well-designed sensory system can be leveraged
as central location for the tuning and optimization of information gathering, as a knowledge propagation
tool, and as a replacement for spatial triggering mechanisms. Such systems can also be a nest of tuning
problems from sensitivity issues to overly subtle behavioral shifts. Using examples from several games,
the discussion examines the design and implementation of a vision and hearing model. The presentation
then explores how the basic implementations presented can be tuned and controlled by game programmers
and designers. From there, the discussion examines the optimization problems present in these systems
and a set of available solutions. The challenges and opportunities of integrating the senses into the
rest of an AI system are considered, including limitations that may be imposed larger game architectures,
communicating to the player the state of non-binary sense states, the leveraging a sensory system to
augment team and squad behaviors, and the limits of the senses metaphor as a game construction tool.
Creating a Scripting System in C++
Greg Rosenblatt
Part 1: Introduction, GameDev.net, 2003.
Part 2: Data Manipulation, GameDev.net, 2003.
Part 3: Dynamic Loading, GameDev.net, 2003.
Part 4: The Stack and Program Flow, GameDev.net, 2003.
Part 5: Functionality, GameDev.net, 2003.
Topics: Scripting; Genres: General
Abstract: This series is intended to give the reader the information necessary to create a scripting system
of his/her own from the ground up. The reasons one would choose to create such a system from scratch
are many, most of which are analogous to reasons one would create anything else from scratch, such
as a 3D engine. Most importantly, in my opinion, is that it's a valuable learning experience.
Neural Networks in Plain English
Mat Buckland (AI-Junkie)
AI-Junkie.com, 2003.
Topics: Learning, Neural Networks; Genres: General
Abstract: I�ll start off by describing what a neural net actually is and what it�s architecture is, then I�ll
do a little theory on how we get it to perform for us but I�ll try to use as little maths as possible.
(Having some understanding of mathematics is impossible to avoid however and the deeper you get into
this topic the more mathematics you are going to have to learn). Finally, we�ll get to the fun bit.
I�ll come up with a little project I will program and take you through one step at a time. It will
be in this last phase of the tutorial where I hope you get the same "eureka" feeling for neural nets
as I did back in rainy old Scotland. Until then just sit back, absorb and be patient.
Genetic Algorithms in Plain English
Mat Buckland (AI-Junkie)
AI-Junkie.com, 2003.
Topics: Learning, Genetic Algorithms; Genres: General
Abstract: The aim of this tutorial is to explain genetic algorithms sufficiently for you to be able to use
them in your own projects. This is a stripped-down to-the-bare-essentials type of tutorial. I'm not
going to go into a great deal of depth and I'm not going to scare those of you with math anxiety by
throwing evil equations at you every few sentences. In fact, I'm not going to throw any nasty equations
at you at all!
Interactive Navigation in Complex Environments using Path Planning
Brian Salomon, et al. (University of North Carolina at Chapel Hill)
Symposium on Interactive 3D graphics, 2003. (direct link to paper)
Topics: Pathfinding; Genres: General
Abstract: We present a novel approach for interactive navigation in complex 3D synthetic environments using path planning. Our algorithm precomputes a global roadmap of the environment by using a variant of randomized motion planning algorithm along with a reachability-based analysis. At runtime, our algorithm performs graph searching and automatically computes a collision-free and constrained path between two user specified locations. It also enables local user-steered exploration, subject to motion constraints and integrates these capabilities in the control loop of 3D interaction. Our algorithm only requires the scene geometry, avatar orientation, and parameters relating the avatar size to the model size. The performance of the preprocessing algorithm grows as a linear function of the model size. We demonstrate its performance on two large environments: a power plant and a factory room.
2002
Toward Better Scripting: Part 1
Jonathan Blow
Game Developer Magazine, October 2002.
Topics: Scripting; Genres: General
Abstract: This article deals with design issues and features when architecting a scripting language. Games
require domain-specific issues to incorporated into the language, so they differ greatly from general purpose
languages. The article references code samples found at the www.gdmag.com site. One example is of a commentator
from a game like Dance Dance Revolution. The other example is a mortar unit from a real-time strategy game.
Toward Better Scripting: Part 2
Jonathan Blow
Game Developer Magazine, November 2002.
Topics: Scripting; Genres: General
Abstract: This article deals with design issues and features when architecting a scripting language. Games
require domain-specific issues to incorporated into the language, so they differ greatly from general purpose
languages. The article references code samples found at the www.gdmag.com site. One example is of a commentator
from a game like Dance Dance Revolution. The other example is a mortar unit from a real-time strategy game.
Game AI: The State of the Industry 2001-2002
Steven Woodcock (Wyrd Wyrks)
Game Developer Magazine, July 2002.
Topics: History, General; Genres: General
Abstract: In the last year, AI game programmers have been focused on one thing - building their AIs with a
more straightforward and elegant approach. Developers are primarily focused on the tried and true. This
article covers the state of the industry for game AI from anecdotes and statistical data gathered at the
2002 Game Developers Conference.
The Evolution of Game AI
Topics: History, General; Genres: General
Abstract: This article provides a big-picture summary of game AI: what it is, where it's going, where it's been, how it can grow, and what makes it so different from any other discipline. We give a broad overview of the evolution of AI in games since the birth of the videogame, as well as the evolution of a game AI within the scope of a game's development. We also describe many of the academic AI techniques that have been applied to games, explain the important distinctions between the needs and approaches mainstream AI and game AIs of various genres, and discuss some of the ways that game AI technologies are likely to grow in the future.
The Illusion of Intelligence
Topics: General; Genres: General
Abstract:
Solving the Right Problem
Topics: General; Genres: General
Abstract: This article will talk about going back to first principles: What is the problem we are trying to solve? Why is that important - what are we really trying to do? Too early programmers settle on an answer to the first when they should more carefully examine the second. A clear example comes from the AI Roundtables at the GDC. At first the company fixated on trying to do speech input. In a world where the NPCs talk, they should be able to listen as well. This left them with the huge mountain of work to do speech recognition, and even if they could climb that mountain, the bigger mountain of natural language processing was waiting hidden behind it. After all, even if Dragon Dictate parses everything you say as well as your officemate does, it surely does not have the ability to make sense of it and respond intelligently. Instead of trying to climb these two large mountains of work, the company stepped back to the question of why it is important. It was important to give a more immersive and natural experience. So instead of doing speech, they implemented gestures. Large motion gestures are universally understood. The shrug that means "I don't know" means "I don't know" to just about everybody. They got a much better result by solving a different problem! While this article won't give people the easier problem to solve, it should help get them thinking about the process. It will also give a number of things other designers do to inspire them to "think outside the box."
12 Tips from the Trenches
Topics: General; Genres: General
Abstract: This article is intended to give developers who are new to Game AI a head start. It gives an overview of many techniques professional Game AI developers have found useful, that may not be immediately obvious to a novice. Topics covered include precomputing navigation, building a world with AI hints, providing fallbacks, finite-state machine organization, and data-driven approaches. Many tips reference other articles in AI Game Programming Wisdom for more detail.
Building an AI Diagnostic Toolset
Topics: General, Tools; Genres: General
Abstract: This article describes invaluable techniques that real developers use to tweak, test, and diagnose their AI during the development cycle. We describe literally dozens of specific ways you can instrument your AI to help you tweak and test it more quickly and figure out what's wrong when your AI breaks.
A General Purpose Trigger System | |
Topics: Architecture, Trigger System; Genres: General
Abstract: This article describes the implementation of a general-purpose centralized Trigger System. A Trigger System is used to keep track of events in the game world, and to optimize processing agents need to perform to recognize these events. Centralizing the Trigger System allows for culling by priority and proximity before delivering Trigger events to agents. The article and companion CD include working code for a stimulus-response Trigger System. Enhancements are discussed to extend the system to handle processing a grouping hierarchy of agents, in addition to individual agents.
A Data-Driven Architecture for Animation Selection | |
Topics: General, Animation; Genres: General
Abstract: Animation selection is a common task for AI systems. Due to advances in animation technology, it is now common to provide a much wider range of animations for characters, including specific animations for specific situations. Rather than simply playing a "Run" animation, characters may play a specific "RunWithSword", "AngryRun", or "InjuredRun" animation. The Action Table is a simple data-driven approach to animation selection. This article describes the implementation of the Action Table, and goes on to describe how this technique can be extended to handle randomization and dynamic animation lists.
Realistic Character Behavior with Prioritized, Categorized Animation | |
Topics: General, Animation; Genres: General
Abstract: Skeletal animation systems allow AI programmers to creates realistic behavior for characters by playing multiple, layered animations simultaneously. The challenge comes in trying to manage these independent layers of animation. This article describes the implementation of a system in which layers of animation are prioritized, and categorized by the region of the body they affect. This data-driven approach moves the management of the layers out of the code. The article and companion CD provide code for this layering system. Handling of blended transitions between animations is discussed using a bone caching technique.
Designing a GUI Tool to Aid in the Development of Finite State Machines
Topics: General, FSM, State Machines, Tools; Genres: General
Abstract:
The Beauty of Response Curves
Topics: General; Genres: General
Abstract:
Simple and Efficient Line-of-Sight for 3D Landscapes | |
Topics: General, Movement; Genres: General
Abstract:
An Open Source Fuzzy Logic Library | |
Topics: Fuzzy Logic; Genres: General
Abstract: This article introduces the Free Fuzzy Logic Library (FFLL), an open source library that can load files that adhere to the IEC 61131-7 Fuzzy Control Language (FCL) standard. FFLL provides a solid base of code that you are free to enhance, extend, and improve. Whether used for rapid prototyping or as a component in an AI engine, FFLL can save significant time and money. The entire library and a sample program is included on the book's CD.
Basic A* Pathfinding Made Simple | |
Topics: A* Pathfinding; Genres: General
Abstract:
Generic A* Pathfinding
Topics: A* Pathfinding; Genres: General
Abstract:
Pathfinding Design Architecture
Topics: A*, Pathfinding; Genres: General
Abstract:
How to Achieve Lightning Fast A*
Topics: A* Pathfinding; Genres: General
Abstract:
Practical Optimizations for A* Path Generation
Topics: A* Pathfinding; Genres: General
Abstract: The A* algorithm is probably the most widely used path algorithm in games, but in its pure form, A* can use a great deal of memory and take a long time to execute. While most optimizations deal with improving the estimate heuristic or with storing and searching the open and closed lists more efficiently, this article examines methods of restricting A* to make it faster and more responsive to changing map conditions. Such A* restrictions take the form of artificially constricting the search space, using partial solutions, or short-circuiting the algorithm altogether. For each restriction, the situations in which these optimizations will prove most useful are discussed.
Simple, Cheap Pathfinding | |
Topics: Pathfinding, Movement; Genres: General
Abstract: There are several cases in which using a lightweight AI method for pathfinding is appropriate, especially on low-powered hand-held gaming systems like the Game Boy Advance or various cell phones. This article presents a simple scheme in which a four-sensored, or whiskered robot, can move through an environment with surprisingly lifelike results. This scheme was successfully used in a number of published games for the Game Boy Color (including NFL Blitz, Disney's Tarzan, and Alice in Wonderland), as well as in several other games for mobile devices.
Preprocessed Solution for Open Terrain Environments | |
Topics: Pathfinding; Genres: General
Abstract:
Building a Near-Optimal Navigation Mesh
Topics: Pathfinding; Genres: General
Abstract: When you want your AI
characters to perform pathfinding in a fully 3D environment, the kind of data structure you select to perform pathfinding will have an enormous impact on the performance of your pathfinding and the quality of the paths. A navigation mesh is one of the best ways to pathfind in these kinds of game worlds. It provides very fast pathfinding and allows you to find the optimal path from any arbitrary point in the game world to any other. This article describes in minute detail how to take arbitrary 3D world geometry ("polygon soup") and automatically construct and optimize a navigation mesh as a preprocessing step.
Realistic Turning between Waypoints
Topics: Pathfinding, Movement; Genres: General
Abstract:
Navigating Doors, Elevators, Ledges, and Other Obstacles
Topics: Pathfinding, Movement; Genres: General
Abstract:
Simple Swarms as an Alternative to Flocking
Topics: Flocking, Movement; Genres: General
Abstract: Craig Reynold's flocking algorithms have been well documented and are highly successful at producing natural-looking movement in groups of agents. However, the algorithms can be computationally expensive, especially where there are a large number of agents or a complex environment to detect against. For this reason, they are not always suited to real-time applications such as video games. This article details a much simpler algorithm for producing natural-looking movement in large swarms of creatures involving tens or hundreds of agents. Although this algorithm cannot guarentee separation of creatures within the swarm, the overall impression organic movement is very convincing.
Strategic and Tactical Reasoning with Waypoints
Topics: Movement, Strategy, Tactical; Genres: FPS, Action
Abstract: Non-player characters (NPCs) commonly use waypoints for navigation through their virtual world. This article will demonstrate how preprocessing the relationships between these waypoints can be used to dynamically generate combat tactics for NPCs in a first-person shooter or action adventure game. By precalculating and storing tactical information about the relationship between waypoints in a bit string class, NPCs can quickly find valuable tactical positions and exploit their environment. Issues discussed include fast map analysis, safe pathfinding, using visibility, intelligent attack positioning, flanking, static waypoint analysis, pinch points, squad tactics, limitations, and advanced issues.
Recognizing Strategic Dispositions: Engaging the Enemy
Topics: Strategy, Tactical, Movement; Genres: RTS, Strategy
Abstract:
Squad Tactics: Team AI and Emergent Maneuvers
Topics: Strategy, Tactical, Coordinated Movement, Cooperation; Genres: FPS, Action
Abstract: AI squad behavior is made up of coordinated individual actions towards a joint goal. There are two basic coordination styles: centralized control by a leader, and decentralized cooperation between individuals. This chapter discusses the latter style in detail. Decentralized cooperation can already be realized with minor changes to "standard individual AI". This chapter illustrates how some tactical squad maneuvers can emerge from these coordinating individual AIs, using a squad assault as an example. The limitations of the approach are illustrated using a second example: a squad ambush. This chapter precedes and complements the chapter "Squad Tactics: Planned Maneuvers".
Squad Tactics: Planned Maneuvers
Topics: Strategy, Tactical, Coordinated Movement, Cooperation; Genres: FPS, Action
Abstract: AI squad behavior can also be realized by designing an explicit team leader, responsible for planning and managing the squad's maneuver. This AI team leader assesses the squad's state, picks and plans the most appropriate squad maneuver. He executes the squad maneuver by issuing orders, and by interpreting feedback and information from the squad members. This is illustrated using a bounding overwatch squad advance. This centralized style to squad AI is more complex than the emergent behavior in "Squad Tactics: Team AI and Emergent Maneuvers". However, it does provide largely autonomous operating squads, able to execute complex maneuvers, and often combines well with some decentralized cooperation among squad members.
Tactical Team AI Using a Command Hierarchy | |
Topics: Strategy, Tactical, Coordinated Movement, Cooperation; Genres: FPS, Action
Abstract: Team-based AI is becoming an increasingly trendy selling point for first- and third-person action games. Often, this is limited to scripted sequences or simple "I need backup" requests. However, by using a hierarchy of decision-making, it is possible to create some very convincing teams that make decisions in real time.
Formations
Topics: Formations, Coordinated Movement; Genres: RPS, RTS, FPS, Action
Abstract: In games today, formations are expected for any type of cohesive group movement. From squad-based first-person shooters to sports sims to real-time strategy games, anytime that a group is moving or working together it is expected to do so in an orderly, intelligent fashion. This article will cover standard military formations, facing issues, mixed formations, spacing distance, ranks, unit mobility, group pathfindng, and dealing with obstacles.
Architecting a Game AI
Topics: Architecture; Genres: General
Abstract:
An Efficient AI Architecture using Prioritized Task Categories
Topics: Architecture; Genres: General
Abstract: Real-time games have many diverse subsections: rendering, AI, collision detection, player-input and audio are just a few. Each of these tasks has a finite amount of time in which to execute, each is trying to do so as quickly as possible, and all of them must work together to give a rich, detailed gaming world. This article concentrates on the AI component and specifically, how to distribute it over time and make it fast for real-time games. It also details how to avoid processing until it's absolutely necessary. The goal will be to structure our AI so that it can execute quickly and efficiently. Two benefits will be realized by doing this; our games will run more smoothly and we'll have freed up the necessary processing power to bring about even more advanced AI.
An Architecture Based on Load Balancing
Topics: Architecture; Genres: General
Abstract:
A Simple Inference Engine for a Rule-Based Architecture | |
Topics: Architecture; Genres: General
Abstract:
Implementing a State Machine Language | |
Topics: Architecture, FSM, State Machines, Scripting; Genres: General
Abstract: This article presents a robust way to structure your state machines with a simple language. This State Machine Language will not only provide structure, but it will unleash some powerful concepts that will make programming games much easier. While the language itself is simple, it embodies some very important software engineering principles such as simplicity, maintainability, robustness, and ease of debuggine. The following article, "Enhancing a State Machine Language through Messaging," expands on this language with a powerful communication technique using messages. Each article has full soure code on the accompanying CD-ROM.
Enhancing a State Machine Language through Messaging | |
Topics: Architecture, FSM, State Machines, Scripting; Genres: General
Abstract: The previous article, "Implementing a State Machine Language," set the groundwork for a powerful language that can structure state machines in a simple, readable, and very debuggable format. In this article, that language will be expanded to encompass the problem of communication between AI game objects. This communication technique will revolutionize the State Machine Language by allowing complicated control flow and timers. Full source code is included on the accompanying CD-ROM.
Blackboard Architectures | |
Topics: Architecture; Genres: General
Abstract: The blackboard architecture is a simple technique for handling coordination between agents. Although simple to implement, the architecture has proven elegant and powerful enough to be useful for problems ranging from synthetic character control to natural language understanding and other reasoning problems. This article explains the canonical blackboard architecture and shows many examples of how a game AI can benefit.
Introduction to Bayesian Networks and Reasoning Under Uncertainty
Topics: Architecture, Bayesian Networks; Genres: General
Abstract: Since the 1990s, probabilistic inference techniques, and the specific subfield of Bayesian networks, have become immensely popular in the academic AI community. The game AI field, however, seems to have missed the boat. This is unfortunate, because Bayesian reasoning techniques can be extraordinarily helpful in getting your AI to reason about situations in a human-like fashion. This article provides a thorough introduction to the underlying concepts of probabilistic reasoning techniques and Bayesian networks, and describes a number of specific examples of the ways you can use them in game AI systems to perform more human-like reasoning.
A Rule-Based Architecture using Dempster-Shafer Theory | |
Topics: Architecture, Dempster-Shafer; Genres: General
Abstract: DST is a variant of probability theory that explicitly models ignorance and uncertainty. Instead of reasoning on discrete events, it manipulates sets of possible events when evidence is imprecise or partially contradictory. Since DST obeys axioms that are less restrictive than those of classic probability, it may apply in more circumstances.
An Optimized Fuzzy Logic Architecture for Decision-Making
Topics: Architecture, Fuzzy Logic; Genres: General
Abstract:
A Flexible Goal-Based Planning Architecture
Topics: Architecture; Genres: General
Abstract:
First-Person Shooter AI Architecture
Topics: Architecture; Genres: FPS, Action
Abstract: This article provides a basic
introduction to building an AI architecture for a first-person shooter game (such as Quake or Unreal) or a first-person sneaker (such as Thief: The Dark Project). We discuss the major components of an FPS AI (including specific subsystems for animation, movement and pathfinding, behavior, combat, sensory modelling, and scripting and trigger systems) and how those components should fit together.
Architecting an RTS AI
Topics: Architecture; Genres: RTS
Abstract: RTS games are one of the more thorny genres as far as AI is concerned, and a good architecture is necessary to ensure success. Most examples presented in this article are taken from the work done on Empire Earth. Issues include game components (civilization manager, build manager, unit manager, resource manager, research manager, and combat manager), difficulty levels, challenges (random maps, wall building, island hopping, resource management, stalling), and overall strategies.
An Economic Approach to Goal-Directed Reasoning in an RTS
Topics: Architecture; Genres: RTS
Abstract: In this article, we discuss one approach to creating an agent for a real-time strategy game, using the Utility Model. This approach takes Economic theories and concepts regarding consumer choice, and creates a mapping onto our game agent's decision space. We explain relevant AI terminology (goal-directed reasoning, reactive systems, planning, heuristic functions) and Economic terminology (utility, marginal utility, cost, production possibilities), and introduce a simplistic RTS example to provide a framework
for the concepts.
The Basics of Ranged Weapon Combat
Topics: Weapon Selection, Weapon Handling; Genres: RTS, RPG, FPS, Action
Abstract: This article gives a brief
introduction to the problems of firing ranged weapons. We discuss to-hit rolls, aim point selection, ray-testing, avoiding friendly fire incidents, dead reckoning, and calculating weapon trajectories for ballistic weapons.
Level-Of-Detail AI for a Large Role-Playing Game
Topics: Level-of-Detail AI, LOD AI, Optimizations; Genres: RPG
Abstract: With thousands of objects demanding AI time slices in Neverwinter Nights, it would be difficult to satisfy all creatures and maintain a playable frame rate. The level-of-detail AI schemes used allowed the game to achieve the perception of thousands of actors thinking simultaneously. The article discusses how to subdivide your game objects into categories, and how certain time-intensive actions (such as pathfinding and combat) can be reduced to make more efficient use of the time available to AI.
A Dynamic Reputation System Based on Event Knowledge
Topics: Reputation System; Genres: RPG, Action, Adventure
Abstract: This article describes a non-player character (NPC) reputation system (a mechanism for dynamically managing NPCs' opinions of each other and of the player in order to influence the NPCs' actions). Most existing reputation systems manage NPCs' opinions globally. The reputation system this article describes instead changes a specific NPC's opinions only if the NPC has direct or indirect knowledge of events that trigger a change. The article describes the data structures required for the reputation system, the way they work together to make the complete system, and the way the system fits into the overall design of NPC behavior.
Representing a Race Track for the AI
Topics: Driving; Genres: Racing
Abstract: This article is the first in a series of three racing AI articles and describes a practical representation of a racetrack for an AI system. The representation includes defining sectors, interfaces, the driving lines (racing line, overtaking line), path type, terrain type, walls, hairpin turns, and brake/throttle points. Methods for determining the current sector and the distance along a sector are also discussed.
Racing AI Logic
Topics: Driving; Genres: Racing
Abstract: This is the second article in a series of three racing AI articles that describes how to implement an AI capable of racing a car around a track. Although the AI will follow predefined driving lines, it will not rigidly follow the track like a train on rails, but merely use these lines as a guide. This goal is to have the AI produce an output that emulates human input; specifically joystick and/or key presses. Using this method, the game engine only needs to gather input from the AI controller instead of a human input device. The article will cover the basic AI framework (FSM, fixed-time step, controlling the car, simplifying with 2D), traversing sectors (anticipating the road ahead, hairpin turns), driving to a target, overtaking, handling under-steer and over-steer (detecting the car's stability, testing for stability, correcting the car), wall avoidance, other states (airborne, off the track), and catch-up logic.
Training an AI to Race
Topics: Driving, Learning; Genres: Racing
Abstract: This is the final article of the three article series, and shows ways to train the AI to race optimally around a racetrack. Issues covered include tuning the car handling (adjusting parameters, converging on optimum values, modifying parameter values, modifying the range, training at high simulation speeds) and real-time editing (real-time track modification, user control overriding AI).
Competitive AI Racing under Open Street Conditions
Topics: Driving; Genres: Racing
Abstract:
Camera AI for Replays
Topics: Camera AI, Replay AI; Genres: Racing, Sports
Abstract:
Simulating Real Animal Behavior
Topics: Animal AI, Flocking; Genres: Hunting, General
Abstract:
Agent Cooperation in FSMs for Baseball
Topics: FSM, State Machines, Cooperation; Genres: Baseball, Sports
Abstract:
Intercepting a Ball
Topics: Movement; Genres: Sports
Abstract:
Scripting: Overview and Code Generation | |
Topics: Scripting; Genres: General
Abstract:
Scripting: The Interpreter Engine | |
Topics: Scripting; Genres: General
Abstract:
Scripting: System Integration
Topics: Scripting; Genres: General
Abstract:
Creating Scripting Languages for Non-Programmers
Topics: Scripting; Genres: General
Abstract:
Scripting for Undefined Circumstances
Topics: Scripting; Genres: General
Abstract: Games are increasingly allowing the player to set the agenda. Want to while away hours mucking around with the game physics by throwing rocks into crowds of villagers? No problem! On the other hand, a strong storyline helps to inform the player of their goals, and provides a context for their actions. Traditionally, storylines in games have been advanced via cinematic sequences, and it is common for these to be displayed using the game engine. Can we resolve the conflict that occurs when we simultaneously afford the player the freedom to set the agenda and the game designers the ability to impose a storyline? What if a crucial moment in the story depends on the presence of the harmless little villager that the player unthinkingly threw into the ocean at the beginning of the game? Even worse, what if a non-player character under AI control intrudes into a cinematic sequence and begins to wreak havoc? In this article we discuss the features that were implemented in the game "Black & White" to allow the game designers to create storyline-advancing "Challenges" without compromising the unpredictable nature of the game.
The Perils of AI Scripting
Topics: Scripting; Genres: General
Abstract: Scripting is an enormously popular technique for developing game AI systems, but it can also be enormously dangerous. This article describes some of the considerations that you should think about very carefully before you jump on the scripting bandwagon, many of which you might not otherwise discover until it's too late. We also describe a number of the things that can go wrong when your lofty scripting language ambitions collide with the realities of game development.
How Not To Implement a Basic Scripting Language
Topics: Scripting; Genres: General
Abstract: This paper goes into some of the mistakes that were made while writing the scripting languages for Baldur's Gate and Neverwinter Nights. The four major points, which are covered with anecdotes: the lack of up-front design, ignoring early-adopter feedback, believing the code will only be used for one project, and believing the language will be used for one specific task.
Learning and Adaptation in Games | |
Topics: Learning; Genres: General
Abstract: It is anticipated that the widespread adoption of learning in games will be one of the most important advances ever to be made in game AI. Genuinely adaptive AIs will change the way that games are played by forcing the player to continually search for new strategies to defeat the AI. This article presents a detailed examination of the different approaches available for adding learning and adaptation to games and draws on the author's experiences of AI development to provide numerous practical examples. The reader is guided through the decisions that must be made when designing an adaptive AI, and summaries of the problems that are most frequently encountered with practical implementations are provided along with descriptions of effective solutions. The CD that accompanies the book contains source code for a genetic programming class, which can be used to evolve rule-based AI, and genetic algorithm and population-based incremental learner classes, which can be used to evolve AI more generally. The practical application of all these classes is illustrated by evolving an AI that successfully navigates a simple environment.
Varieties of Learning
Topics: Learning; Genres: General
Abstract:
GoCap: Game Observation Capture
Topics: Learning; Genres: General
Abstract:
Pattern Recognition with Sequential Prediction | |
Topics: Learning, Pattern Matching; Genres: General
Abstract: This article provides a simple but efficient algorithm for recognizing repetitive patterns in number sequences. Pattern recognition is something that humans are very good at, but for a computer this is not so easy. Too often a game AI can be beaten by repeatedly performing the same trick, just because it is unable to perceive the pattern. This article explains how to deal with this problem and shows you how to map game events onto useful number sequences. Furthermore, it describes a few possible applications of the algorithm in computer games.
Using N-Gram Statistical Models to Predict Player Behavior
Topics: Learning, Pattern Matching; Genres: General
Abstract: N-Grams are statistical constructs used to predict sequences of events in situations that exhibit the property of local structure. Language is one such context: the probability of hearing the word "fries" is higher if one has just heard the word "french" than if one has just heard the word "fruit". Some games, specifically fighting games in which players develop signature move combinations, also exhibit this property. The article describes how to train an AI to recognize patterns and predict the human player's next move using N-Gram models.
Practical Natural Language Learning
Topics: Learning, NLP; Genres: General
Abstract: The perception of intelligence seems to be directly related to the observation of behavior that is surprising yet sensible. Natural language interfaces were common features of computer entertainment software prior to the advent of sophisticated computer graphics, but these were often repetitive in nature: encountering the same scripted conversation over and over again quickly becomes boring. Stochastic language models have the ability to acquire various features of a language from observations they make, and these features can be used generatively to produce novel utterances that have the properties of being both surprising and sensible. In this article we show how such a system, when used to host in-game socially-oriented conversations, can greatly contribute towards the subjective impression of intelligence experienced by the player.
Testing Undefined Behavior as a Result of Learning
Topics: Learning, Testing; Genres: General
Abstract: We consider learning to be the essence of Artificial Intelligence. Non-player characters, when granted the ability to learn, are given the potential to surprise and entertain the player in completely unexpected ways. This is very reinforcing from the player's point of view, but a nightmare for a testing department. How can they assure the quality of a game that may behave completely differently depending on the who's playing it? In this article we show, via a case study of the computer game "Black & White", exactly how a testing department can achieve their goals when the product they're testing features unpredictable learning AI.
Imitating Random Variations in Behavior using a Neural Network | |
Topics: Learning, Neural Networks; Genres: General
Abstract: As game AI has increased in sophistication, it has become possible to create computer controlled agents that display remarkably human-like behavior. One of the few indications that an agent is non-organic is the frequently clinical nature of their actions, an effect exacerbated by the often ad hoc mechanisms used to add random variations. This article shows how neural networks can be taught to imitate the actual random variations in behavior that are exhibited by real people. This makes it possible to simulate the playing styles of different sports personalities in unprecedented detail - even the extent to which, for example, the cueing direction and position of the cue ball relative to the cushion affect the accuracy of a pool player's shots. The article assumes minimal knowledge of neural networks and illustrates the techniques through their application to a real game. The CD that accompanies the book contains all the source code for the game, along with that for the neural network class, which is designed as a plug-in component that can easily be transferred to other applications.
Genetic Algorithms: Evolving the Perfect Troll | |
Topics: Learning, Genetic Algorithms; Genres: General
Abstract: Genetic Algorithms mimic the process of natural selection to evolve solutions to problems that cannot be solved analytically. Candidate solutions, generated at random, are tested and evaluated for their fitness; the best of them are then bred and the process repeated over many generations, until an individual of satisfactory performance is found. This article explains the biological foundations of genetic algorithms and illustrates their behavior with an example: evolving a troll for a fantasy game.
The Dark Art of Neural Networks
Topics: Learning, Neural Networks; Genres: General
Abstract:
Optimized Machine Learning with GoCap
Topics: Learning; Genres: General
Abstract:
Area Navigation: Expanding the Path-Finding Paradigm
Topics: Pathfinding; Genres: General
Abstract:
Function Pointer-Based, Embedded Finite-State Machines | |
Topics: State Machines, FSM; Genres: General
Abstract: This article examines the use of function pointers in creating a inheritable base class for adding finite state machine (FSM) functionality to new or existing C++ classes. The function pointer implementation replaces the classic switch statement implementation commonly used to implement FSMs in game objects. The new implementation is designed to work well with C++ inheritance and function overloading and offers better performance and less maintenace than switch implementations.
Terrain Analysis in an RTS-The Hidden Giant
Topics: Tactical; Genres: RTS
Abstract:
A Extensible Trigger System for AI Agents, Objects, and Quests
Topics: Architecture, Trigger System, Scripting; Genres: General
Abstract:
Tactical Path-Finding with A* | |
Topics: A* Pathfinding, Tactical; Genres: General, FPS, RTS
Abstract: Tactical paths consider cover and stealth in addition to travel time. Although costs for cover and stealth are easily added to the A* cost function, this alone does not result in convincing tactical paths. This chapter analyzes the defects in these paths, and discusses tactical improvements: taking into account exposure time and enemy aiming behavior, and anticipating likely enemy movement. The extensions to the A* cost functions introduce additional run-time costs. This chapter discusses the costs, and provides work-arounds and optimizations to make tactical pathfinding more efficient.
A Fast Approach To Navigation Meshes
Topics: Pathfinding; Genres: General
Abstract:
Choosing a Relationship Between Path-Finding and Collision
Topics: Pathfinding; Genres: General
Abstract:
Naughty Dog's Jak & Daxter: The Precursor Legacy
Stephen White (Naughty Dog)
Game Developer Magazine, April 2002.
Topics: Scripting; Genres: General
Abstract: This postmortem on the PS2 game Jak & Daxter describes the pros and
cons of their custom language based on Lisp. The language supports nonpreemptive
cooperative multi-tasking and required a custom compiler. Pros include: the ability to
compile and download code while the game is running which resulted in rapid tuning and debugging,
the ability to write logic that didn't have to save state when it suspended itself for that
game tick, simplified syntax, and the ability to intermix assembly instructions with higher-level
code. Cons include: it caused a lot of grief, all support/bug fixes/feature enhancements came from
the sole programmer who was the designer of the language, it took over a year to develop the
compiler, programmers had to put up with odd quirks, missing features, and numerous bugs, gave up
third-party tools such as profilers and debuggers, hard to find programmers with Lisp experience,
and problems with memory usage (garbage collection).
Polygon Soup for the Programmer's Soul: 3D Pathfinding
Greg Hjelstrom, Patrick Smith (Westwood Studios)
Game Developers Conference Proceedings, 2002.
Topics: Pathfinding; Genres: General
Abstract: One of the fundemental goals of an AI system is to avoid making the unit appear "dumb." At
the root of this challenge lies one of the hardest problems to overcome efficiently and believably:
pathfinding. Today, 3D graphics and sound technologies begin to reach a level of realism that is easily
destroyed by seeing an AI unit walk face-first into a solid wall, slide along the perimeter, and
ultimately get stuck on an errant polygon. This session addresses the pitfalls of attempting to pathfind
the arbitrary world we call "polygon soup." It also covers automatic data generation and compression,
a run-time distributed algorithm, organic post-process modifiers, and solutions for tricky situations
such as doors, ladders, and elevators.
Social Activities: Implementing Wittgenstein
Tom Barnet-Lamb (Lionhead Studios), Richard Evans (Lionhead Studios)
Game Developers Conference Proceedings, 2002.
Topics: Cooperation, Coordinated Movement; Genres: General
Abstract: In Black & White, a number of different "group minds" were implemented, such as reactions,
towns, and dances. These activities had a lot in common, but were implemented completely separately.
What was in common between them was not captured explicitly. This meant that adding a new type
of activity was quite difficult and time-consuming: all the bookkeeping had to be re-implemented
each time. This lecture proposes a new system that captures what is common between different
activities and makes it as easy as possible to add a new type. Furthermore, and more excitingly, this
new system allows the mod community to add new activities after the game has been released. This
is a good idea because the perceived "depth" of an AI agent is largely a function of the number
of different sorts of activities it can engage in. By making it optimally easy to add new activities,
we increase the total number of activities we can implement. In Black & White, the number of activities
implemented was rather small. With this new system, we hope to have hundreds of different activities.
Game Scripting in Python
Bruce Dawson (Humongous Entertainment)
Game Developers Conference Proceedings, 2002.
Topics: Scripting; Genres: General
Abstract: Scripting languages allow rapid development of game behavior without the pitfalls that await
the unwary C++ programmer. Using an existing scripting language saves the time and cost of developing
a custom language and typically gives users a far more powerful language than they could create on their
own. Python is an execellent choice for game scripting, because it is easily embedded, is powerful, can
seamlessly be extended with C/C++ code, has most of the advanced features that make scripting languages
worthwhile, and can be used for automating productions tasks as well as in the game. Additionally, the books,
development tools and libraries available for Python give great opportunities for leveraging the work
of others. This session describes the presenter's experiences with integrating Python into a game engine.
It explains why Python was chosen, what the benefits have been, what problems were encountered, and
how they were solved. This session illustrates why using an existing scripting language, rather than
creating one's own, is the smart thing to do. Python is a good choice for a game scripting language, and
integration is easy, especially with the lessons that are taught in this session.
State-Based System of Animation: Artfully Blending Animation with AI
Peter Hirchmann & Sunil Thankamushy (Dreamworks Interactive)
Game Developers Conference (Audio only), 2002.
Topics: Animation; Genres: General
Abstract: As we enter the era of next-generation gaming technology, it is very important to create solid tools
for high-quality animation performance that enable the animators and designers to do real-time magic and fully
utilize the real-time nature of this medium. With today's high-powered game systems, the animator should be
able to rise out of that tiny cubicle and create content that isn't just dead assets, but ones that are
elivened with intelligence: scripted states, behaviors, routines, patterns, and the like. Working on Medal of
Honor has been a terrific exercise in finding creative solutions to blend character animation with AI so they
may work hand in hand to enhance the immersive experience of the game. In the course of the three games that
make up the Medal of Honor universe, rigorous processes, queer methodologies, and simple philosophies have been
developed and used very effectively by the animators. This session is about sharing some of what was learned.
Action-Based Discretization for AI Search
Todd Neller (Gettysburg College)
Game Developers Conference (Audio only), 2002.
Topics: Architecture, Pathfinding; Genres: General
Abstract: For agents to act intelligently in continuous, dynamic environments, some facility for look-ahead
is necessary. In order to apply AI search techniques to continuous problems, one must first form a discrete
approximation of the continuous problem. State-space-based discretization techniques (such as waypoints and
additional state) suffer computationally when the environment is very dynamic, making it necessary to keep
track of many changing variables. An alternate technique focuses on discretizing continuous action spaces
(how to act), and action timing (when to act). So long as the environment is efficiently simulated, the
complexity (dimensionality) of the state space is irrelevant. Since complex actions can arise from a few
simple action primitives, it is possible to synthesize complex actions dynamically with search. Lecture
attendees learn about the fundemental trade-offs between state-space discretization and action/action-timing-space
discretization. Additionally, they learn new algorithms that perform such discretization autonomously.
Machine Learning in Games Development
Nick Palmer
AI-Depot.com, September 2002.
Topics: Learning; Genres: General
Abstract: This article explains the current perceptions of ML in the games industry, some of the
techniques and implementations used in present and future games, and offers suggestions for
further exploration.
Artificial Intelligence in Game Design
Tim Schreiner
AI-Depot.com, July 2002.
Topics: History, General; Genres: General
Abstract: With important upcoming video games focusing on single player only, it can be surmised
that game designers know the importance of AI. Its important roles in design are narrowed down to
three, and analysed further.
Expert Systems and Logic Games
Alex J. Champandard
AI-Depot.com, January 2002.
Topics: Expert Systems; Genres: Puzzle
As an integral part of Artificial Intelligence for the past five decades, Expert Systems have
become a very popular solution to a wide variety of problems. After giving a basic overview of
expert systems, we'll show they can be used to tackle a logic game such as connect four.
Beginners Guide to Pathfinding Algorithms
Senior Diablo
AI-Depot.com, December 2002.
Topics: Pathfinding; Genres: General
Abstract: Network & tree searches are important as a basis for AI in many contexts. This article
provides a colourful introduction and explains the different search methods available. It also shows
the evolution of A* over other search algorithms.
Decision Trees and Evolutionary Programming
Kirk Delisle
AI-Depot.com, December 2002.
Topics: Learning; Genres: General
Abstract: Commonly used in pattern recognition and AI decision systems, the basic structure of DT
allows application of IF...THEN type rules to classification, which are easily utilized and interpreted.
This article presents a unique method of developing such trees using Evolutionary Programming.
Minimax Explained
Paulo Pinto
AI-Depot.com, July 2002.
Topics: General; Genres: Puzzle
Abstract: Discusses how search can be applied to logic games with full information. Game trees are
described, as well as an algorithm that can search them. Pseudo code is given and optimisations like
alpha-beta are explained.
Game Trees in Realtime Games
Marco van de Wijdeven
AI-Depot.com, July 2002.
Topics: General, Search; Genres: General, RTS
Abstract: Examines how heuristic game tree search can be used in videogames like real-time
strategy games. Written from the viewpoint of both AI programmers and gamers, the article
provides an over view of concepts as well as a description and analysis of the algorithm.
Finite State Machines (FSM)
Jason Brownlee
AI-Depot.com, July 2002.
Topics: FSM, State Machines; Genres: General
Abstract: Provides a practical introduction to FSM, within the context of AI as a control
technique. The emphasis is placed on practicality both in definition and explanation, rather
than heavy theoretical or mathematical concepts.
Path-Planning from Start to Finish
Alex J. Champandard
AI-Depot.com, April 2002.
Topics: A* Pathfinding; Genres: General
Abstract: The fifth issue of a multi-part tutorial covering all the aspects of path planning.
This issue discusses single-pair shortest-path problems, with the different kinds of searches
that can solve them. A* (star) is then explained as a heuristic approach; with pseudo-code and
optimisation ideas.
2001
Managing AI with Micro-Threads | |
Topics: Architecture; Genres: General
Abstract:
Micro-Threads for Game Object AI | |
Topics: Architecture; Genres: General
Abstract: Presents code and concepts to create hundreds of low-overhead threads by manipulating the stack. This technique has notable benefits in terms of AI load balancing and the author has implemented the architecture on systems ranging from the PC to the GameBoy.
A Generic Fuzzy State Machine in C++ | |
Topics: Fuzzy Logic, FSM, State Machines; Genres: General
Abstract: Fuzzy Logic provides an attractive alternative to more crisp forms of finite state decision making. This article builds on the presentation of the Finite-State Machine class from the first Game Programming Gems book, by introducing a generic Fuzzy-State Machine class in C++. The concepts of fuzzy logic are presented and an example of applicability for computer game AI is offered. The FSMclass and FSMstate classes from the first GEMS book are converted into fuzzy logic versions, and source code is provided for review.
Using a Neural Network in a Game: A Concrete Example | |
Topics: Neural Networks, Learning; Genres: General
Abstract: Neural networks are a powerful artificial intelligence technique that are based on an abstraction of the neurocomputational functions of the human brain. One of their most important characteristics is that they can learn by example, and do not need to be programmed in the conventional sense. For example, Codemasters (the developers of Colin McRae Rally 2.0) discovered that a neural network could learn how to drive a rally car by imitating the developers' play, thus avoiding the need to construct a complex set of rules. This article guides the reader through all the steps that are necessary to incorporate neural networks into their own game. Assuming no prior understanding, the article presents a case study of applying one of the most popular, easy to use, and effective neural networks, the multilayer perceptron, to a real game. All the steps required for successful neural network development are described, as are the most common problems, and their solutions. The CD that accompanies the book includes all the source code for the game, and the neural network class that lies at the heart of its AI. The class is designed to be used as a drop-in module in other games and hence contains no application specific code.
A High-Performance Tile-based Line-of-Sight and Search system
Topics: Movement, Sensory; Genres: RTS
Abstract:
An Architecture for RTS Command Queuing
Topics: Movement; Genres: RTS
Abstract: Explains the concept of Command Queuing in an RTS along with several ways to implement it. Command Queuing is the idea that the player should be able to queue up any sequence of command orders (Move, Attack, Patrol, Repair, etc) for a particular unit. Some commands that cycle, such as Patrol, present specific challanges in order to acheive the right behavior. Solutions to these difficulties are discussed along with detailed diagrams.
Stratagies for Optimizing AI
Topics: Architecture, Optimization; Genres: General
Abstract: Presents 11 strategies for optimizing AI, along with tips and examples for each.
1. Use event-driven behavior rather than polling.
2. Reduce redundant calculations.
3. Centralize cooperation with managers.
4. Run the AI less often.
5. Distribute the processing over several frames.
6. Employ level-of-detail AI.
7. Solve only part of the problem.
8. Do the hard work offline.
9. Use emergent behavior to avoid scripting.
10. Amortize query costs with continuous bookkeeping.
11. Rethink the problem.
Influence Mapping
Topics: Tactical; Genres: RTS, Strategy
Abstract: Influence mapping is a powerful and proven AI technique for reasoning about the world on a spatial level. Although influence maps are most often used in strategy games, they have many uses in other genres as well. Among other things, an influence map allows your AI to assess the major areas of control by different factions, precisely identify the boundary of control between opposing forces, identify "choke points" in the terrain, determine which areas require further exploration, and inform the base-construction AI systems to allow you to place buildings in the most appropriate locations.
Strategic Assessment Techniques
Topics: Tactical; Genres: RTS, Strategy
Abstract: This article discusses two useful techniques for strategic decision-making. These are easiest to understand in the context of strategy game AI, but they have applications to other game genres as well. The resource allocation tree describes a data structure that allows an AI system to continuously compare its desired resource allocation to its actual current resources in order to determine what to build or purchase next. The dependency graph is a data structure that represents a game's "tech tree," and we discuss a number of ways that an AI can perform inference on the dependency graph in order to construct long-term strategic plans and perform human-like reasoning about what its opponents are attempting to accomplish.
Terrain Reasoning for 3D Action Games
Topics: Tactical, Movement; Genres: Action, FPS
Abstract:
Flocking with Teeth: Predators and Prey | |
Topics: Flocking, Movement; Genres: General
Abstract:
Expanded Geometry for Points-of-Visibility Pathfinding
Topics: Movement, Pathfinding; Genres: General
Abstract:
Optimizing Points-of-Visibility Pathfinding
Topics: Movement, Pathfinding; Genres: General
Abstract:
Imploding Combinatorial Explosion in a Fuzzy System
Topics: Fuzzy Logic; Genres: General
Abstract: As a fuzzy logic systems grow, the number of rules needed for the system grows exponentally. This is know as combinatorial explosion and can quickly make fuzzy systems slow, confusing, and difficult to maintain. This article clearly explains the Combs Method which turns the rule's exponential growth into linear growth! System with 10 variables and 5 sets per variable require only 50 rules using the Combs Methos, as opposed to 9,765,625 rules using traditional fuzzy logic methods. This article explains what can be a confusing topic in a clear and concise manner, a proof of the Combs Method is included for the curious reader.
Creature Smarts: The Art and Architecture of a Virtual Brain
Robert Burke, Damian Isla, Marc Downiew, Yuri Ivanov, Bruce Blumberg (M.I.T. Synthetic Characters Group)
Game Developers Conference Proceedings, 2001.
Topics: Architecture; Genres: General
Abstract: This lecture describes the process of character creation from a behavior-based standpoint.
Drawing upon experience designing interactive installations, the speakers discuss the components necessary
to take a character from its initial artistic design phase through to its implementation as an
autonomous agent in a dynamic virtual world. In designing these virtual creatures, the Synthetic
Characters Group at the MIT Media Lab draws inspiration from animal behavior, experimental biology,
and the brain and cognitive sciences. The speakers discuss how the lessons drawn from these diverse
fields can inform the design of a character's cognitive architecture, perception system, short-term
and associative memory, emotion system, motor system, and learning. The primary case study used is
Duncan, an autonomous sheepdog first presented at the Game Developers Conference in 2000. Intelligence
is a problem that can be tackled in layers, by breaking its components into discreet subsystems as
suggested by nature. Under this system, in the end, doing things right is easier. Enforcing perceptual
honesty and making use of biologically inspired cognitive models results in more lifelike behavior.
Expressiveness is key; if it's in the character, show it. AI is not an afterthought; an interactive
system should be designed with AI in mind from the beginning.
The Basics of Team AI
Clark Gibson, John O'Brien (Red Storm Entertainment)
Game Developers Conference Proceedings, 2001.
Topics: Strategy, Tactical, Coordinated Movement, Cooperation; Genres: General
Abstract: With the popularity of network play growing every day, modern gameplay is moving away from
single-player modes to team-based games with cooperative goals. This change in game styles has
necessitated a change in AI, from individual AIs out to hunt down a single player to team AIs that
either help the player or cooperate in the hunt. This lecture discusses the basics of team-based AI,
drawing on the speakers' experience with games such as Tom Clancy's Rainbow Six and Shadow Watch.
Terrain Reasoning for 3D Action Games
William van der Sterren (CGF-AI)
Game Developers Conference Proceedings, 2001.
Available Online at Gamasutra, 2001.
Topics: Tactical, Movement; Genres: Action, FPS
Abstract: Terrain reasoning in 3D action games is about understanding concepts such as stronghold,
cover, ambush, and sniper location. This lecture introduces a simple yet powerful approach for
terrain reasoning, enabling the AI itself to compute these concepts. Traditionally, AI relies on hints
and scripts manually added by level designers to grasp the terrain. However, an AI that actually
understands the terrain will respond better to dynamic situations and directions issued by the
player. The terrain reasoning presented uses a waypoint graph with a high spatial density of waypoints.
Due to its density, it is a good abstraction of the terrain. Being a graph, it enables computations. The
lecture shows numerous examples of how to express terrain concepts in terms of this graph. A case
study illustrates how situational awareness, team formations, tactical pathfinding, and adaptive tactics
are implemented using both in-game and pregame terrain reasoning.
Level-of-Detail AI
Demis Hassabis (Elixer)
Game Developers Conference (audio only), 2001.
Topics: LOD AI, Simulation; Genres: General, Simulation
Abstract: As simulations become ever more complex and the need for realistic environments in games
becomes greater, the question of how to deal with large numbers of autonomous agents efficiently becomes
increasingly vital. This lecture gives a broad overview of simulations in general before addressing
the issues raised by large numbers of autonomous agents through the use of cutting-edge LOD techniques.
Various strategies are reviewed which deal with issues such as detail flipping, consistency guarantees,
networking problems, timeslicing, agent compression, and more. These points are illustrated with a
demonstration of Elixir's first game, Republic: The Revolution, which is built on a highly complex
simulation of an entire country containing hundreds of thousands of autonomous agents.
Game Developers Conference 2001: An AI Perspective
Eric Dybsand (Glacier Edge Technology)
Available Online at Gamasutra, 2001.
Topics: History, General; Genres: General
Abstract: A computer game industry insider reviews many of the AI topic
lectures, presentations, tutorials, roundtables, and sessions that
were presented at the 2001 Game Developers Conference held in
March, 2001 (including the infamous AI Programmer's Dinner).
Toward More Realistic Pathfinding
Marco Pinter (Badass Games)
Game Developer Magazine, April 2001.
Available Online at Gamasutra, 2001.
Topics: A*, Pathfinding, Movement; Genres: General
Abstract:
The Future of AI in Games: A Personal View
Richard Evans (Lionhead Studios)
Game Developer Magazine, August 2001.
Topics: Architecture, Learning, History; Genres: General
Abstract:
Game AI: The State of the Industry
Steven Woodcock (Wyrd Wyrks)
Game Developer Magazine, August 2001.
Topics: History, General; Genres: General
Abstract:
Bot Navigation: Design Philosophy
Alex J. Champandard
AI-Depot.com, September 2001.
Topics: Bots, Pathfinding; Genres: FPS
Abstract: This article discusses the pitfalls of bot navigation, and describes the human approach
to spatial awareness and terrain recognition. Base on this, a modular system is described allowing
both reactive and deliberative components to cooperate eleguantly.
Bot Navigation: Advanced Obstacle Avoidance
Alex J. Champandard
AI-Depot.com, November 2001.
Topics: Bots, Pathfinding; Genres: FPS
Abstract: This is the third installment of our Bot Navigation column. In this issue, we discuss
evolution in real-time noisy environments, practical optimisations for evolutionary solutions and
representations enhancements that increase the model's performance.
First Steps in Game AI: Your Own Bot
Alex J. Champandard
AI-Depot.com, October 2001.
Topics: Bots; Genres: FPS
Abstract: In tackling practical issues involved in creating game AI, this article demonstrates
how First Person Shooters are ideal for developing Artificial Intelligence. Not only is this
framework an ideal platform for modern technology, but it's also great fun!
Bot Navigation: Neural Networks for Obstacle Avoidance
Alex J. Champandard
AI-Depot.com, October 2001.
Topics: Bots, Learning; Genres: FPS
Abstract: A practical insight into applying machine learning to a common first person game. These
few pages will use your theoretical understanding of neural networks, and allow you to tackle a
concrete problem with it.
2000
Designing a General Robust AI Engine | |
Topics: Architecture, FSM, State Machines, Scripting; Genres: General
Abstract:
A Finite-State Machine Class | |
Topics: Architecture, FSM, State Machines; Genres: General
Abstract: Simple Finite-State Machines are powerful tools used in many computer game AI implementations. This article introduces a generic C++ class that implements a Finite-State Machine that is useful to the novice for learning about Finite-State Machines and as a building block for more complex AI implementations in development projects. The processes of a Finite-State Machine are presented, an example game implementation is offered as an example of Finite-State Machine usage, and source code illustrates how finite-state functionality can be implemented in a generic manner.
Game Trees
Topics: Game Tree; Genres: General, Board Games
Abstract:
The Basics of A* for Path Planning | |
Topics: A* Pathfinding; Genres: General
Abstract:
A* Aesthetic Optimizations
Topics: A* Pathfinding; Genres: General
Abstract:
A* Speed Optimizations
Topics: A* Pathfinding; Genres: General
Abstract:
Simplified 3D Movement and Pathfinding Using Navigation Meshes | |
Topics: Movement, Pathfinding; Genres: General
Abstract:
Flocking: A Simple Technique for Simulating Group Behavior | |
Topics: Movement, Flocking; Genres: General
Abstract:
Fuzzy Logic for Video Games | |
Topics: Fuzzy Logic; Genres: General
Abstract:
A Neural-Net Primer | |
Topics: Neural Networks; Genres: General
Abstract:
Pawn Captures Wyvern: How Computer Graphics Can Improve Your Pathfinding
Mark Brockington (BioWare)
Game Developers Conference Proceedings, 2000.
Available Online at Gamasutra, 2000.
Topics: A* Pathfinding; Genres: General
Abstract: For a long period of time, the study of games of thought (such as computer chess) rarely
included discussions about pathfinding. However, the two fields are highly related to one another.
Advances in computer chess searching algorithms can be used to dramatically speed up search
algorithms such as A-Star. This talk looks at a number of computer chess searching improvements
and shows, with concrete examples, how to improve A-Star-style pathfinding algorithms with these
chess derived techniques.
Terrain Analysis in Realtime Strategy Games
Dave Pottinger (Ensemble Studios)
Game Developers Conference Proceedings, 2000.
Topics: Tactical; Genres: RTS
Abstract: Terrain analysis is like a black-art. Every real-time strategy (RTS) game with a decent
AI, whether it knows it or not, does some type of terrain analysis. This lecture examines various methods
for terrain analysis as they apply to RTS games. Starting with simple topics as chokepoint determination
and building placement, the class moves on to more advanced topics such as frame-based terrain representation
and integration of terrain knowledge throughout the rest of the AI. Copious examples are provided by the way
of numberous 2D/3D demos and code snippets.
Interaction with Groups of Autonomous Characters
Craig Reynolds
Game Developers Conference Proceedings, 2000.
Topics: Movement, Flocking, General; Genres: General
Abstract: This lecture presents a methodology for contructing large groups of autonomous
characters which respond to the user's interaction (as well as to each other and their environment)
in real time. The characters are based on steering controllers under the direction of a simple
mental model which mediates between several conflicting behavioral goals. The characters
are represented graphically by 3D models with a library of animated motions which must be
choreographed by the behavioral controllers.
Formation-Based Pathfinding with Real-World Vehicles
Jim Van Verth, Victor Brueggemann, Jon Owen, Peter McMurry
Game Developers Conference Proceedings, 2000.
Topics: Pathfinding, Movement, Formations; Genres: General
Abstract: A number of papers and articles have been written about formation-based pathfinding.
Many of them, however, make the assumption that the units involved can move in any direction and can
turn on a dime. This lecture presents our solution in Force 21 to the problem of controlling
real-world vehicles in formation, what we learned from it, and what we will do differently the
next time.
AI Madness: Using AI to Bring Open City Racing to Life
Joe Adzima (Motocentric)
Game Developer Magazine, December 2000.
Available Online at Gamasutra, 2000.
Topics: Driving; Genres: Racing
Abstract:
The Future of Game AI
Dave Pottinger (Ensemble Studios)
Game Developer Magazine, August 2000.
Topics: History, General; Genres: General
Abstract:
Bridging the Gap Between Developers & Researchers
John Laird (Artificial Intelligence Laboratory, University of Michigan)
Game Developer Magazine, August 2000.
Topics: General; Genres: General
Abstract:
Game AI: The State of the Industry
Steven Woodcock (Wyrd Wyrks)
Game Developer Magazine, August 2000.
Topics: History, General; Genres: General
Abstract:
More AI in Less Processor Time: 'Egocentric' AI
Ian Wright and James Marshall
Available Online at Gamasutra, 2000.
Topics: Architecture; Genres: General
Abstract: Discusses a technique for confining per frame AI processing. Covers time-slicing the processing with dynamic suspension and reactivation, running AI code at different frequencies, and staggering AI processing relative to each other to prevent processing spikes.
1999
Designing AI Engines with Built-in Machine Learning Capabilities
Zhimin Ding
Game Developers Conference Proceedings, 1999.
Topics: Architecture, Learning; Genres: General
Abstract: A game engine usually consists of a set of 3D environments and a collection of simulated
interactive characters. The behaviors of these characters are often specified in an ad hoc fashion
with if...then... statements. This is both tedious and inflexible. An alternative solution
is to assign an AI engine to each of these characters and let their behaviors evolve. This is
possible if the AI engine has built-in learning capabilities. This presentation introduces machine
learning technologies that combine system identification and optimal control into an integrated AI engine.
The AI engine does not assume any prior knowledge abou the system under its control and synthesize
an optimal control strategy at run time. Once you have completed the interface of the AI engine with
the characters through the simulated sensors and actuators, you can assign a goal to each of the
characters and let them evolve interesting interactive behaviors.
Developing an Artificial Intelligence Engine
John Laird, Michael van Lent
Game Developers Conference Proceedings, 1999.
Topics: Architecture; Genres: General
Abstract: As computer games become more complex and consumers demand more sophisticated
computer-controlled agents, developers are required to place a greater emphasis on the artificial
intelligence aspects of their games. One source of sophisticated AI techniques is the academic
artificial intelligence community. This lecture presents our recent efforts to develop a behavior engine
based on state-of-the-art artificial intelligence techniques from the academic research community.
The first part of the behavior engine is a large knowledge base of game independent goals, strategies,
and tactics. By adding a small amount of game specific information the behavior knowledge baase can
be easily applied to any game within a genre. The second part of the behavior engine is the Soar
artificial intelligence architecture, which applies the behavior knowledge base to generate intelligent
behaviors for agents in a game. Our behavior engine, which has been interfaced with Quake II and Descent III,
draws on advanced AI techniques such as goal-directed reasoning, hierarchical decomposition and machine
learning.
Steering Behaviors for Autonomous Characters
Craig Reynolds
Game Developers Conference Proceedings, 1999.
PDF and HTML versions of the paper
Topics: Movement, Flocking; Genres: General
Abstract: This lecture presents solutions for one requirement of autonomous characters in
animation and games: the ability to navigate around their world in a lifelife and improvisational
manner. These steering behaviors are largely independent of the particulars of the character's
means of locomotion. Combinations of steering behaviors can be used to achieve higher-level
goals (for example, get from here to there while avoiding obstacles, go down this corridor,
join that group of characters). This lecture divides motion behavior into three levels. It
focuses on the middle level of steering behaviors, briefly describes the lower level of
locomotion, and touches lightly on the higher level of goal setting and strategy.
Game AI: The State of the Industry
Steven Woodcock (Wyrd Wyrks)
Game Developer Magazine, August 1999.
Available Online at Gamasutra, 1999.
Topics: History, General; Genres: General
Abstract:
Implementing Coordinated Movement
Dave Pottinger (Ensemble Studios)
Game Developer Magazine, February 1999.
Available Online at Gamasutra, 1999.
Topics: Formations, Pathfinding, Coordinated Movement; Genres: RTS, General
Abstract:
Coordinated Unit Movement
Dave Pottinger (Ensemble Studios)
Game Developer Magazine, January 1999.
Available Online at Gamasutra, 1999.
Topics: Formations, Pathfinding, Coordinated Movement; Genres: RTS, General
Abstract:
AI for Games and Animation: A Cognitive Modeling Approach
John Funge
Available Online at Gamasutra, 1999.
Topics: Architecture; Genres: General
Abstract:
1998
Project AI
Mark Lewis Baldwin
Computer Game Developers Conference Proceedings, 1998.
Topics: Architecture; Genres: General
Abstract:
Multiple Character Interaction Between Believable Characters
Adam Frank, Andrew Stern
Computer Game Developers Conference Proceedings, 1998.
Topics: Architecture; Genres: General
Abstract:
Hardcore AI for the Computer Games of Tomorrow
John Funge
Computer Game Developers Conference Proceedings, 1998.
Topics: Architecture; Genres: General
Abstract:
Lies, Damn Lies, and ASR Statistics
Neil Kirby (Bell Labs)
Computer Game Developers Conference Proceedings, 1998.
Topics: NLP; Genres: General
Abstract:
Building Advanced Autonomous AI Systems for Large Scale Real Time Simulations
John Laird, Randolph Jones
Computer Game Developers Conference Proceedings, 1998.
Topics: Architecture; Genres: General
Abstract:
Natural Language Processing in 55 Minutes or Less
John O'Neil
Computer Game Developers Conference Proceedings, 1998.
Topics: NLP; Genres: General
Abstract:
Making the Play: Team Cooperation in Microsoft Baseball 3D
Steve Rabin (WizBang Software Productions)
Computer Game Developers Conference Proceedings, 1998.
Topics: Architecture, Cooperation; Genres: Sports, Baseball
Abstract: Explains a technique for coordinating 9 fielders during defensive play so that they cooperate and can dynamically cover each other's positions if needed. The technique involves using a manager entity to assign jobs by priority based on the ball and baserunner positions, instead of each player having a static job, like cover first base.
The Orc Problem
Swen Vincke
Game Developer Magazine, October 1998.
Topics: Genetic Algorithms, Pathfinding; Genres: General
Abstract:
Game AI: The State of the Industry
Steven Woodcock (Wyrd Wyrks)
Game Developer Magazine, October 1998.
Available Online at Gamasutra, 1998.
Topics: History, General; Genres: General
Abstract:
Incorporating Motion Capture Animation into an AI Engine
Wyeth Ridgway (Zombie)
Game Developer Magazine, June 1998.
Topics: Animation, Architecture; Genres: General
Abstract:
Adding Planning Capabilities to Your Game AI
W. Brian Stout
Game Developer Magazine, January 1998.
Topics: Planning, Architecture; Genres: General
Abstract:
1997
Autonomous Agents: A Matter of Life and Death
Peter de Bourcier
Computer Game Developers Conference Proceedings, 1997.
Topics: A-Life, Learning; Genres: General
Abstract:
Making the Solution Fit the Problem: AI and Character Control in Crash Bandicoot
Andy Gavin
Computer Game Developers Conference Proceedings, 1997.
Topics: Scripting; Genres: General
Abstract:
Adding Extensible Custom Languages to Game Engines
Robert Huebner
Computer Game Developers Conference Proceedings, 1997.
Topics: Scripting; Genres: General
Abstract:
Representing Artificial Personalities
Greg Pisanich and Michael Prevost
Computer Game Developers Conference Proceedings, 1997.
Topics: Architecture; Genres: General
Abstract:
Issues of Autonomous Character Design
Ben Resner
Computer Game Developers Conference Proceedings, 1997.
Topics: General; Genres: General
Abstract:
Inside NHL Powerplay 96: What Are They Thinking?
David Roberts
Computer Game Developers Conference Proceedings, 1997.
Topics: Architecture, Scripting; Genres: Sports, Hockey
Abstract:
Cyberlife: A Biologically Inspired Architecture for Games
Toby Simpson
Computer Game Developers Conference Proceedings, 1997.
Topics: Architecture; Genres: General
Abstract:
Apparent Intelligence or Inanimate Objects Make Good Friends
Chip Standifer
Computer Game Developers Conference Proceedings, 1997.
Topics: General; Genres: General
Abstract:
Real AI, Part 3: Planning
W. Bryan Stout
Computer Game Developers Conference Proceedings, 1997.
Topics: Planning; Genres: General
Abstract:
Applied AI: Chess is Easy, Go is Hard
Bruce Wilcox
Computer Game Developers Conference Proceedings, 1997.
Topics: Game Trees, Search; Genres: Board Games
Abstract:
Adding Languages to Game Engines
Robert Huebner (Lucas Arts Entertainment)
Game Developer Magazine, September 1997.
Available Online at Gamasutra, 1997.
Topics: Scripting; Genres: General
Abstract:
Real-Time Pathfinding for Multiple Objects
Swen Vincke
Game Developer Magazine, June 1997.
Topics: Pathfinding; Genres: General
Abstract:
1996
Real AI, Part 2: Pathfinding
W. Bryan Stout
Computer Game Developers Conference Proceedings, 1996.
Topics: A*, Pathfinding; Genres: General
Abstract:
Smart Moves: Intelligent Path-Finding
W. Brian Stout
Game Developer Magazine, October 1996.
Available Online at Gamasutra, 1999.
Topics: A*, Pathfinding; Genres: General
Abstract:
The Making of HyperBlade
Stuart Rosen (WizBang! Software Productions), Robert Duisberg (WizBang! Software Productions)
Game Developer Magazine, August 1996.
Topics: Scripting, Architecture; Genres: General
Abstract:
Fuzzy Logic in Games
Larry O'Brien
Game Developer Magazine, April 1996.
Topics: Fuzzy Logic; Genres: General
Abstract:
Using Genetic Algorithms
Don O'Brien
Game Developer Magazine, February 1996.
Topics: Genetic Algorithms; Genres: General
Abstract:
1994
Real AI, Part 1: Game-Tree Search
W. Bryan Stout
Computer Game Developers Conference Proceedings, 1994.
Topics: Game Tree; Genres: Puzzle, Board Games
Abstract: Covers beginner to advanced techniques used to solve abstract games of perfect information, such as Chess, checkers, Othello/reversi, and tic-tac-toe. Topics include game tree, minimax search, exhaustive vs. selective search, alpha-beta pruning, transposition tables, iterative deepening, move ordering techniques, quiescence search, board representation, evaluation functions, opening and endgame databases, minimal window search, history heuristic, forward prunning, and search extensions.
|
