|
Artificial Intelligence: Pathfinding and Movement
Company of Heroes Squad Formations Explained |
Abstract: This article describes all the techniques used to produce the squad formation movement in Company of Heroes. The squads controlled with this system have very tactical and visually interesting motion that handles obstacles and destructible environments with minimal impact on performance. A variety of techniques are described that, when used together, produce high quality squad motion.
Turning Spaces into Places |
Abstract: This article explores the complex relationship between the forms of spatial representation employed by game agents and the forms of behavior that are easily supported by them. We shall see how most game agents typically reduce space to little more than a list of individual entities with objective spatial features existing in a task-neutral navigational representation of the global environment, and we will see how this is likely to severely limit their behavioral sophistication. This observation leads us into an extended discussion of the much richer notions of place found in the philosophical literature, before returning to practical themes with a review of place-based models in game AI. We will discuss affordance theory, smart object models, terrain analysis, influence mapping and informed environments, relating these specific approaches back to the general philosophical notions of place identified in the middle section of the article.
Dynamically Updating a Navigation Mesh via Efficient Polygon Subdivision |
Abstract: Many 3D games rely on some sort of navigation mesh for pathfinding. However, most methods of NavMesh generation are not suitable for run-time updates for reflecting a dynamic environment. This article proposes a novel use of line-clipping to create a system that can be dynamically updated in real time.
Intrinsic Detail in Navigation Mesh Generation |  |
Abstract: This article describes a method to generate high-fidelity paths over very large terrains. The key to this approach is the Restricted Quadtree Triangulation (RQT), which provides the minimal representation of a height map given a world-space error metric. RQT is well suited to navigation meshes because it represents low-frequency terrain (flat plains, for example), with the fewest needed vertices while preserving detail in high-frequency regions. At runtime, path generation determines a preliminary course over a high-tolerance representation of the entire terrain, then refines the initial path in subsequent frames by paging low-tolerance navigation meshes for terrain chunks in the order they occur along the path. Crucial details-a narrow valley through an otherwise impassable mountain range, for example-are omitted by naive simplifications but preserved by RQT. This approach is less complex than various schemes to stitch streaming data, avoids backtracking during path refinement, and works transparently alongside other navigation mesh simplifications described in previous volumes of this series.
Navigation Mesh Generation: An Empirical Approach |
Abstract: Automatic generation of navigation meshes can increase the speed and quality of level content creation. This article presents a new empirical approach to mesh generation that relies on directly sampling the world geometry for navigability data. The algorithm is well suited to a wide range of detailed environments and results in a relatively uniform triangle mesh ideal for pathfinding use. Implementation approaches, optimizations, and extensions are also discussed.
Navigation Graph Generation in Highly Dynamic Worlds |
Abstract: Game designers are introducing more and more dynamic changes into worlds that have previously been largely entirely static. This makes for a compelling playing experience, but can be a major headache for AI programmers. If the physical world can change at any moment, how can the AI of the NPCs keep up? This paper addresses this challenge with an innovative technique for updating the key AI data structure (the navigation graph) in real-time. The technique starts with the game's raw geometry ("polygon soup") and processes this on the CPU (or even GPU!), generating or updating the navigation graph automatically.
Fast Pathfinding Based on Triangulation Abstractions |
Abstract: Pathfinding for games is a multidimensional problem. The industry is making increasing demands for solutions that are fast, use minimal pre-computation and memory, work for large and complex environments and objects of multiple sizes, etc. This article presents two search algorithms - TA* (Triangulation A*) and TRA* (Triangulation Reduction A*) - which successfully address these requirements. TA* finds paths on a Constrained Delaunay Triangulation environment representation, while TRA* works on a reduced graph calculated from this triangulation.
Automatic Path Node Generation for Arbitrary 3D Environments | |
Abstract: This article presents an automated way to create a compact and efficient navigable space mesh for an arbitrary static 3d game environment. It has been used in several commercial products and proven to provide an excellent knowledge base, allowing AI bots to navigate extremely complex 3d worlds even over vast distances.
Risk-Adverse Pathfinding Using Influence Maps | |
Abstract: This article describes a pathfinding algorithm that allows the use of Influence Maps (IM) to mark hostile and friendly regions. The algorithm allows us to find the optimal path from point A to point B very quickly while taking into consideration the different threat and safety regions in the environment. This allows units to balance the risk while traversing their path, thus allowing for more depth of gameplay.
Practical Pathfinding in Dynamic Environments |
Abstract: The article discusses the subject of pathfinding in dynamic environments. It features tried and tested techniques for handling the addition, removal and most importantly modification of objects during the game. It covers how both nodes and edges can be used to store valuable information that speed up searches as well as information that is used in the actual searches. As pathfinding graphs become larger and more detailed, it is useful to catch unnecessary searches can before the actual call to the pathfinder is made. It is described how this can be done as well as how to verify existing paths.
Postprocessing for High-Quality Turns |
Abstract: This article describes a system to achieve high quality vehicle motion for units that move primarily by sliding along a predefined path. The system refines the paths generated by a standard smoothed A* into routes that obey the limited turning capabilities of units. A palette of possible turns to use for each corner in the original path is defined and a search technique to quickly determine the optimal turn for each corner is described. A way to avoid speed discontinuities when changing paths is also specified.
Memory-Efficient Pathfinding Abstractions | |
Abstract: Several different types of hierarchical pathfinding abstractions have been proposed in game-development literature, and many more are likely being used in published games. This article describes a pathfinding abstraction that is specifically designed to minimize the memory overhead of the abstraction. In addition to describing the abstraction itself, we also describe in detail how the abstraction can be used for pathfinding, including many small optimizations that are important for practical use. We measure the performance experimentally, showing a 100-fold improvement over the worst-case performance of A*.
Abstract: Cooperative pathfinding is a general technique for coordinating the movements of multiple units. Units communicate their planned paths, enabling other units to avoid their intended routes. This article explains how to implement cooperative pathfinding using a space-time A* search. Moreover, it provides a number of improvements and optimizations, which allow cooperative pathfinding to be implemented both efficiently and robustly.
Improving on Near-Optimality: More Techniques for Building Navigation Meshes |
Abstract: New techniques for automatically building navigation meshes for use in pathfinding are presented, building on Paul Tozour's article "Building a Near-Optimal Navigation Mesh." Polygons are subdivided around walls and other static obstacles with precise cuts that reduce the number of polygons. The same subdivision method can be used for merging overlapping polygons, and the height of the agent is taken into account by extruding polygons. An additional technique for merging the resulting polygons is presented. To improve performance, a simple spatial data structure based on a hash table is used.
Smoothing a Navigation Mesh Path |
Abstract: It is becoming increasingly common to use a navigation mesh as the search space representation for pathfinding in games. We present a path-smoothing algorithm for use with a navigation mesh. The algorithm converts a rough path of navigation mesh cells found by A* into a curved path which an agent can follow. We use B�zier splines to generate a rounded curve which is guaranteed to stay on the surface of the navigation mesh, keeping the agent safe. We explain a string-pulling technique used to make the smoothed path as direct as possible.
Preprocessed Pathfinding Using the GPU |
Abstract: This article proposes GPU-based implementations for two popular algorithms used to solve the all-pairs shortest paths problem: Dijkstra's algorithm, and the Floyd-Warshall algorithm. These algorithms are used to preprocess navigation mesh data for fast pathfinding. This approach can offload pathfinding-related CPU computations to the GPU at the expense of latency. However, once the solution table is generated, this approach minimizes the latency time for a specific path search, thus giving the game a better sense of interactivity. The biggest benefit of this approach is gained in systems with multiple agents simultaneously requesting paths in the same search space. Although the article describes a GPU-specific implementation for a navigation mesh, any other multi-processor environment or discrete search space representation can be used.
Flow Fields for Movement and Obstacle Avoidance |
Abstract: There are many algorithms in AI which can produce conflicting results. For example, in collision avoidance, avoiding one object can result in hitting another. The AI must resolve these conflicts and find a solution that avoids all objects simultaneously. Resolution is often achieved using iterative processing or prioritization techniques. However, by using flow fields this problem can be solved for all objects simultaneously. In this article we will see how flow fields can be an elegant solution to many other problems as well, such as, smoothing A* results and controlling movement during battle.
Insect AI 2: Implementation Strategies |
Abstract: The integration of AI into a game engine where the agent is simulated and run under physical control can be a challenge. The AI's internal model of the world is likely to be very simple relative to the complexity of the game world, yet the AI has to function in a reasonable and efficient manner. This article shows how to usefully integrate Insect AI into systems where the physics, collision, and animation systems are black boxes not directly under AI control, and are not even directly accessible by the AI. It also discusses practicalities of implementation including integration with pre-existing AI algorithms in a game engine.
Intelligent Steering Using Adaptive PID Controllers |
Abstract: As physics systems become more complex and are embedded more deeply into our games, our jobs as AI programmers become more difficult. AI characters need to operate under the same physical restrictions as the player to maintain the visual continuity of the game, to reduce the player's sense of being cheated by the computer, and to reduce the development workload necessary to create multiple physics systems which must interact with one another. Although this problem can be solved by using standard PID (Proportional-Integral-Derivative) controllers, they are difficult to tune for physics systems whose characteristics vary over time. Fortunately, control engineering provides a solution to this problem: adaptive controllers. This article focuses on Model Reference Adaptive Controllers: controllers which attempt to make the AI character's behavior match a predefined model as closely as possible within the physical constraints imposed by the game. The article comes with full source code for a demo that lets you change the handling characteristics of a missile flying towards a moving target, and watch while the PID coefficients are updated in real-time.
Fast, Neat, and Under Control: Arbitrating Between Steering Behaviors |
Abstract: Steering behaviors are a convenient way of creating complex and lifelike movements from simple reactive procedures. However, the process of merging those behaviors is not trivial and the resulting steering command can lead to suboptimal or even catastrophic results. This article presents a solution to these problems by introducing inverse steering behaviors (ISBs) for controlling physical agents. Based on the original concept of steering behaviors, ISBs facilitate improved arbitration between different behaviors by doing a cost based analysis of several steering vectors instead of relying on one solution only.
Real-Time Crowd Simulation Using AI.implant |
Abstract: Next-generation gaming hardware such as the Xbox 360 and PlayStation 3 will allow the creation and visualization of large visually rich but virtually uninhabited cities. It remains an open problem to efficiently create and control large numbers of vehicles and pedestrians within these environments. We present a system originating from the special effects industry, and expanded in the military simulation industry, that has been successfully evolved into a practical and scalable real-time urban crowd simulation game pipeline with a behavioral fidelity that previously has only been available for non-real-time applications such as films and cinematics.
A Unified Architecture for Goal Planning and Navigation |
Abstract: Graph networks, traversed by standard algorithms such as A*, are the staple of most pathfinding systems. The formalization of navigation algorithms into a search graph that represents spatial positioning is one of the most effective ideas in game AI. However ubiquitous graph networks may be in pathfinding, their use in more general problem domains in modern games seems to be less common. Couldn't we extend the standard pathfinding arsenal—graph networks and A*—to other problem sets? This is the idea that we will be exploring in this article.
Training Digital Monsters to Fight in the Real World |
Abstract: This article discusses how we approached and solved the problem of creating compelling AI agents for Digimon Rumble Arena 2, a one to four-player brawler. This consisted of two major challenges: How to pathfind through and respond intelligently to highly dynamic and interactive environments, and how to program a wide variety of characters to play effectively in ten different game types without incurring a combinatorial explosion of code complexity.
Ant Colony Organization for MMORPG and RTS Creature Resource Gathering |
Abstract: This article provides details about the implementation of ant colonies for pathfinding in massively multiplayer and real-time strategy games. Details include the effects of pheromones and individual ant behavior, as well as what variables to focus on when adapting the provided source code. Readers are taught how to control the elasticity of path seeking and path reinforcement.
Tactical Path-Finding Using Stochastic Maps on the GPU |
Search Space Representations |
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 |
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 |
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 |
Jumping, Climbing, and Tactical Reasoning: How to Get More Out of a Navigation System |
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 |
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 |
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 |
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.
Transport Unit AI for Strategy Games |
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.
Considerations for Movement and Physics in MMP Games |
Client-Side Movement Prediction |
Simple, Cheap Pathfinding |
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 |
Building a Near-Optimal Navigation Mesh |
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 |
Navigating Doors, Elevators, Ledges, and Other Obstacles |
Simple Swarms as an Alternative to Flocking |
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 |
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.
Area Navigation: Expanding the Path-Finding Paradigm |
A Fast Approach To Navigation Meshes |
Choosing a Relationship Between Path-Finding and Collision |
Flocking with Teeth: Predators and Prey |
Expanded Geometry for Points-of-Visibility Pathfinding |
Optimizing Points-of-Visibility Pathfinding |
Simplified 3D Movement and Pathfinding Using Navigation Meshes |
Flocking: A Simple Technique for Simulating Group Behavior |
|
