Navigation: Overview >> Working Group on Pathfinding

Working Group on Pathfinding

The working group on pathfinding is combined out of eight members. Noel S. Stephens coordinates the group, which is composed of various game AI developers, middleware producers, academics and educators. He took over this role from Eric Dybsand (who was the successor of Ian Frank). We posted 224 discussion contributions to our forum so far, arguing about the best way to define an interface for pathfinding.

Goals for Pathfinding Standards

Our preliminary focus/goal is to define the core terminology and techniques associated with commonly used pathfinding algorithms and data structures. Currently, our group is focusing on gathering this past year's collective work, documenting it, and putting application towards the theories discussed.

Common Terminology

AI
For the purposes of this group's documents, when the term "AI" is used by itself, it refers specifically to the pathfinding algorithm or agent.
Agent
An entity in a simulation. For the purposes of this group, an agent is the entity (be it a character, vehicle, or whatever) which is attempting to pathfind.
Connection
A path between two nodes. Every node must have one or more connections to another node in order to exist in the graph.
Explicit Graph
An explicit graph is one in which the graph is held in a data structure that encapsulates the graph structure.
Graph
A representation of a terrain model made up of an arbitrary mesh of nodes and connections.
Grid
A representation of the terrain in which all of the nodes have a fixed number of connections in fixed directions.
Implicit Graph
An implicit graph is one in which the graph's structure is exposed through an interface. It is more representationally powerful than an explicit graph.
Node
An atomic entry in the navigational graph. When the AI navigates to a node, its destination is considered to be the center of the node.
Pathfinding
This is the process of searching for waypoints that form a path, which can be used by agents as a guide for movement through terrain and obstacles within a virtual world.
Region
A collection of nodes. The region is a collection of "large scale" navigational data such that the AI can use this to determine a larger path it needs to cover or not cover in order to reach its destination.

High-Level Specification

The pathfinding group has been discussing several concepts in regards to storing and retrieving data pertinent to that of the typical pathfinding algorithms. Thus far, we have come up with a Graph, Node, Connection concept.

The Graph is the underlying container/descriptor for any given region.

Nodes are the sub-sections that break the graph into regions that are more manageable. The nodes will hold navigational related information that the agents can use to determine the most optimal path. The weighted information held within the node is dynamically assigned to the node and directly affects the weight/cost of the node.

Each node will be connected to another node to form a grid of nodes that the agents can parse through in order to formulate the most optimal path. The connections will also have a weighted value assigned to them and thus will have the ability to have dynamically assigned navigational data members associated with them.

There will be the ability within both nodes and connections to register callback methods that will be able to handle/over-ride weighted calculations. This allows agents the ability to control how they view the Graph, Node, connection sets uniquely to the agent itself. The idea is to have a series of container classes that have the ability to have data members stored within them which defines the container class itself in regards to pathfinding algorithms as well as have the ability to over-ride fundamental pathfinding algorithms that will enable for a more flexible system.

As of recently, the pathfinding group has defined the first stage to achieve the goal for the before mentioned pathfinding concepts. These three sub-groups within the pathfinding group are:

Terminology and Theory Documentation Group

The members of this group are responsible for documenting both terms and concepts discussed throughout the pathfinding forums. The end result for this group is to create a nicely formatted document that contains terms commonly used within the discussions (with definitions) and documentation that the laymen mind might not be familiar with as well as concepts discussed through the forums that the pathfinding group agrees are pertinent to the standard said group is constructing.

This group should query the two other groups for any new terminology or concepts. This group should not feel like they are liable in coming up with the terminology, but rather will act as a conduit to organize and prepare the information discussed in the pathfinding forums.

Members of the group:

Graph, Node, Connection Set Class Construction Group

The members of this group are assigned the task to construct a series of classes that correspond to the Graph, Node, Connection topology and theory discussed thus far in the pathfinding group. The first stage of this task is to construct a simple Windows application that will allow a user to construct a graph, create nodes within the graph, and then create connections between the nodes.

The classes should be pure to their purpose and thus should not contain any elements that require any Windows API support. Any external library support should be contained in classes outside of the Graph, Node, Connection classes. The result should be a series of generic classes that can be ported to any platform with little effort.

Members of the Group:

Navigational Mesh File I/O Group

The members of this group are assigned the task to construct a set of classes/libraries that can be used to read in a navigational mesh file from a specific format. The data that gets read in should have a fairly simple set of access methods that will enable access to the data read in from the file.

The members of this group need to keep in mind that there needs to be a layer between the file I/O methods and the actual code/classes that handle storing and retrieving the data. This will allow for portability later in the year. A good starting example of this type of code could almost be borrowed directly from Game Programming Gems 1 section 3.6 "Simplified 3D Movement and Pathfinding Using Navigational Meshes".

Members of the Group:

Design Decisions

Thus far, we have come up with the agreement that pathfinding is very unique based on the game genre and demands. In order to provide the most flexible pathfinding standard we will need to create class containers that can be defined externally, yet have methods that allow external systems to configure them for the specific pathfinding requirements needed at the time. We have felt that there is no universal means to pathfinding, yet there are similar traits and data sets that can be configured/assigned to allow for typical internal algorithm (i.e. A*) use.

We have agreed that such a task will require refinement of the concepts, and before we come up with an entire system we need to come up with sub-systems first. Now that we have a well defined theory foundation, we have broken our group into sub-groups with the assignments of either tracking/documenting new concepts/terminology, creating a very fundamental Graph, Node, Connection class set, and finally coming up with a means to testing our Graph, Node, Connection class set (Navigational Mesh I/O).

It has been agreed upon to test our current theories through common application before seeking further analysis or further depth to our suggested theories. Upon completion of our first application stage, we will analyze our implementation and discuss how we can better improve the fundamental concepts used as well as the interface to said concepts.

Group Members

Current members of the working group on pathfinding:

Navigation: Overview >> Working Group on Pathfinding