Proceedings of the AAAI 99 Spring Symposium on Artificial Intelligence and Computer Games.

Finding a Pathfinder

Bjørn Reese
The Maersk Mc-Kinney Moller
Institute for Production Technology,
University of Southern Denmark
Campusvej 55
DK-5230 Odense M
breese@mip.ou.dk

Bryan Stout
4531 Airlie Way
Annandale, VA 22003
bstout@mindspring.com

Abstract:

The success of a given pathfinding technique for a computer game depends on the requirements and the assumptions of the game and the constraints it imposes. This paper presents a classification of the factors that influences the performance of pathfinding techniques. This includes the dynamics of the game, the geometry of the players and the environment, the (un)predictability of movement, kinematic and temporal restrictions, interaction rules, and real-time performance. The purpose of this classification is the help developers identify the complexity of the task before choosing a certain approach.

Introduction

Choosing a pathfinding techniques that performs well is important to the success of artificial intelligence in computer games, because pathfinding is a fundamental building-block for the field of Artificial Intelligence. There are a wide variety of pathfinding techniques, and one technique may excel under certain circumstances, but do badly under others. The success of a given approach depends on the requirements and assumptions of the game. The purpose of this paper is not to offer solutions, but to raise awareness about the most common factors that influences the efficiency of pathfinding techniques. The more factors that the developer intends to incorporate into the game, the more complex the pathfinding becomes.

Path Type

Pathfinding is usually associated with finding the shortest path, but there are other possibilities, which may have to be solved differently. These include finding any path, finding a path with maximum coverage of an area (Emmanuel, Fagegaltier, and Liegéois 1994), finding a path with minimal exposure (Hoff, Howard, and Tseng 1995), and finding the set of paths with the maximum capacity to get as many units as possible to the destination (Ahuja, Magnanti, and Orlin 1993).

Planning

Not every game is suited for planned navigation. Often it is sufficient to use a set of simple behavioral or reactive rules, and rely on those to perform spatial movement, collision avoidance, and other navigational requirements.

On the other hand, not every game can be satisfactory handled by such rules. Using reactive rules to navigate through a maze most often yields exceptionally bad results. Rule-based navigation is restricted by the lack of global knowledge, which results in paths of poor quality, or even getting caught in traps it cannot escape (local minima.)

Sometimes the player has an objective rather than a geometric destination. One example is the Pursuit-Evade game, where the objective of the evader is to stay away from the pursuer. Another example is to maintain visibility with another player. In such cases planned navigation is not advantageous.

Dynamics

Some parts of the environment may be able to change during the game. It is convenient to categorize these according to the origin of the change.

Geometry

The physical appearance of the environment plays an important role.

Uncertainty

Miscellaneous Factors

Improving Performance

Changes to the environment can be handled more efficiently if they are anticipated.

Re-planning

If the environment changes or new information becomes available, it may be necessary to re-evaluate the planned path. There are several approaches:

Dynamic Data Structures

Changes to the environment can be handled more efficiently, if the underlying data structure has been designed to expect such changes. Even then real-time responsivity can be further improved.

Conclusion

This paper has articulated various factors that influences the complexity, and hence the performance, of pathfinding. These factors have been catagorized according to issues such as the type of the path, the soundness for planning, the dynamics of the game, the geometry of the environment and the players, the (un)certainty of information, and various other factors.

The classification is not exhaustive, and there is some overlap between certain of the described factors. The overlap was allowed to make a classification that would map more directly unto the problem-domain, rather than an orthogonal classification which was abstracted to obscurity.

References

Ahuja, Ravindra K.; Magnanti, Thomas L.; and Orlin, James B. 1993. Network Flows. Theory, algorithms, and applications. Englewood Cliffs, New Jersey: Prentice Hall.

Basch, Julian; Guibas, Leonidas J.; and Hershberger, John, 1997. Data Structures for Mobile Data. In the 8th Symposium on Discrete Algorithms, 747-756.

Ben-Shahar, Ohad and Rivlin, Ehud, 1995. To Push or Not to Push - Part I: On the Rearrangement of Movable Objects by a Mobile Robot. Technical Report, CIS9516, Computer Science Department, Technion, Haifa, Israel.

Booth, Heather and Westbrook, Jeffery, 1992. A Linear Algorithm for Analysis of Minimum Spanning and Shortest Path Trees of Planar Graphs. Technical Report, YALE/DCS/TR-763, Department of Computer Science, Yale University, New Haven, Connecticut.

Emmanuel, T.; Fagegaltier, L.; and Liegéois, A. 1994. Motion Planning for a Patrol of Outdoor Mobile Robots. In Proceedings of European Robotics and Intelligent Systems Conference (EURISCON'94), Malaga, Spain, 103-139.

Guldner, Jürgen; Utkin, Vadim I.; Bauer, Rudolf, 1994. On the Navigation of Mobile Robots in Narrow Passages: A General Framework Based on Sliding Mode Theory. In Robot Control 1994 (SYROCO'94): a postprint volume from the IFAC Symposium, Capri, Italy, 59-64. Oxford, UK: Elsevier Science.

Hoff, Bruce; Howard, Michael D.; Tseng, David Y. 1995. Path Planning with Terrain Utilization in ModSAF. In Proceeding of the Fifth Conference on Computer Generated Forces and Behavioral Representation, Orlando, Florida, 255-263.

Korf, Richard E. 1985. Iterative-Deepening A*: An Optimal Admissible Tree Search. In Proceedings of the International Joint Conference on Artificial Intelligence, Los Altos, California, 1034-1036. Morgan Kaufmann.

Larsen, Kim S. 1998. Relaxed Balance Home Page

Latombe, Jean-Claude, 1991. Robot Motion Planning. Boston: Kluwer Academic Publishers.

Stentz, Anthony, 1995. The Focussed D* Algorithm for Real-Time Replanning. In Proceedings of the International Joint Conference on Artificial Intelligence.