Navigation: Overview >> Working Group on Pathfinding

Working Group on Pathfinding

Introduction

The working group on pathfinding currently consists of nine members - after the unfortunate death of Eric Dybsand earlier this year. Syrus Mesdaghi has replaced Noel S. Stephens as the group coordinator. The group has 300 forum postings and more than 30 uploaded files consisting of skeletal interfaces and accompanying sample implementation.

In the past year, the discussions moved from terminology and high-level specification of graphs to more concrete design considerations. During the past year, we have considered different approaches to designing the interface(s).

Specifically, in order to deal with pathfinding, two main decisions have to be made:

  1. First, one must decide on the representation of the world. Should the world be represented as a 2D grid, triangle mesh, waypoint graph, volume graph, or another representation?
  2. Second, one must decide on the search technique. It is safe to say that most games use A* as their search technique. It is also true that as the size of the world increases and the number of agents increase, even running efficient search techniques such as A* can become impractical. As the result, when possible, many games still use the more trivial "Trial and Error" techniques despite their other drawbacks, and fall-back to A* only when is necessary.

Goals

We want to define a standard Application Programming Interface that will eliminate the need to reinvent the wheel by every developer that has to approaching pathfinding. Our goal is to:

  1. Provide common input structures for world interfacing, or several types of structures for several different representations as detailed below.
  2. Provide common output structures for interfacing other AI modules.
  3. Allow for different search techniques, including hardware-based search support.

In addition, such API can promote consistency between tools that are used to create data sets on which pathfinding occurs. For example, 3D Studio Max and Maya plug-ins can output data in a format(s) that is beneficial to different games.

Different World Representations

Designing standard interfaces for pathfinding is not a trivial task. One of the questions is whether there should be a common interface that can meet the pathfinding needs of different games. This is difficult because even games that are from the same genre can have entirely different representations and search techniques. For example, the agents of games that are based on Half-Life or Unreal engines tend use waypoint graphs to navigate around the world. Agents of games that are based on the Quake III and Lithtech engines tend to use of volumes to find their way around the world. There are also plenty of games, including Counter Strike: Condition Zero, that use navigation meshes to help agents navigate the world and understand their surroundings.  Games from different genres have even a wider range of needs. For example, an RTS game such has WarCraft III needs to deal with pathfinding for numerous agents. To make the matter worse, the world changes during runtime due to harvesting and destruction of trees. This means that pre-planning is not a viable option.  

When designing the interface, there are many practicalities to consider. At one end of the spectrum, it may seem beneficial to abstract the interface enough so that it can deal with pathfinding for a wide variety of games. At the other end of the spectrum, it may make more sense to design multiple distinct interfaces that solve the pathfinding problem for specific scenarios. The latter approach means that there will be redundant functionality across the interfaces. Another point to consider is that if there is a single common interface, it will be easier to use search techniques and algorithms with different representation. However, it is also beneficial for search algorithms to know as much as possible about the specific underlying representation so that they can run efficiently and find better paths.

We now have sample implementations that represent the world as a triangular navigation mesh, waypoint graph, as well as a grid. We are currently considering whether we can try to design an interface that can work for different world representations, or we should commit to a distinct interface for each representation technique. We are generally leaning towards distinct interfaces, but we have not committed to either way.

Different Search Techniques

We have been debating on the proper way to deal with different search techniques. It is understood that search techniques in the broader sense include more than just different graph searching algorithms. Many games use some kind of algorithms, for refining or smoothing the solutions.

Currently, we consider an API supporting a 3-stage pipeline for searching:

  1. Preprocessing of queries: find the right nodes in the graph for searching (e.g., the closest way points to the source and destination, the right nav-mesh nodes, move "up" in a tiered approach).
  2. Graph searching (e.g., A*, "Trial and Error", fast marching).
  3. Post processing (e.g., string pulling, spline smoothing).

We also hope to design an API so that it can be used for hardware-based search. Efficient hardware implementation requires the interface to support batch queries, i.e., receiving a set of queries for paths between different points and returning all solutions.

Group Members

Current members of the working group on pathfinding:

 

Navigation: Overview >> Working Group on Pathfinding