|
Pathfinding / Movement (not A* specific)
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.
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.
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.
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.
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.
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.
Pathfinding Design Architecture
Topics: A*, Pathfinding; Genres: General
Abstract:
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:
Area Navigation: Expanding the Path-Finding Paradigm
Topics: Pathfinding; Genres: General
Abstract:
A Fast Approach To Navigation Meshes
Topics: Pathfinding; Genres: General
Abstract:
Choosing a Relationship Between Path-Finding and Collision
Topics: Pathfinding; Genres: General
Abstract:
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.
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.
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.
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.
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.
Expanded Geometry for Points-of-Visibility Pathfinding
Topics: Movement, Pathfinding; Genres: General
Abstract:
Optimizing Points-of-Visibility Pathfinding
Topics: Movement, Pathfinding; 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.
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:
Simplified 3D Movement and Pathfinding Using Navigation Meshes | |
Topics: Movement, Pathfinding; Genres: General
Abstract:
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.
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:
The Orc Problem
Swen Vincke
Game Developer Magazine, October 1998.
Topics: Genetic Algorithms, Pathfinding; Genres: General
Abstract:
Real-Time Pathfinding for Multiple Objects
Swen Vincke
Game Developer Magazine, June 1997.
Topics: Pathfinding; Genres: General
Abstract:
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:
|
