Navigation: Overview >> Working Group on Pathfinding

Working Group on Pathfinding

This year most of the effort of the pathfinding group has gone into designing and implementing a generic API that does not dictate a particular world representation or search technique. The group has presented a partial proposal API and accompanying reference implementation that satisfies most past decisions of the group and relevant discussion in other groups. The partial API covers only the graph searching stage of the pathfinding pipeline and not the preprocessing or post-processing stage defined in the 2004 AIISC pathfinding group report. In order to create a more complete API the group will address the following issues next:

1. Handling graph (saving/loading/transferring) in XML format.

2. Preprocessing and query input format.
a. selection between coordinates and node number as query input
b. definition of what such a conversion means algorithmically for various graph types.
c. means to take into account agents.

3. Post-processing and path output format
a. conversion of the path using node number to a "normal curve"
b. smoothing/string pulling etc
c. API means to select these options, and formats for returning such results from queries

4. Easy interface with the steering API

Key API And Design Features

This discussion assumes familiarity with the 2003 and 2004 AIISC pathfinding group reports. We will use the nomenclature (connection, graph, etc.) defined by the group in previous years. The partial API is a single include file defining 3 basic classes:

The API does not force a specific implementation on the objects so that the underlying implementations can build data structures as they see fit to meet their restrictions (e.g. memory, computation) and optimize. The factory object can cope with several simultaneous implementations, assuming different library providers can have products with different strengths and weaknesses.

The API allows the library user to specify his own world representation at run-time. Several world representations can be used together through a common interface: The nodes and connections follow a "flexible format" methodology (similar to DirectX vertex format):

The API is state driven in respect to manipulating the state of the pathfinding pipeline to ensure forward compatibility. The API defines some enumeration for selecting the type functionality (e.g. type of heuristic function, selecting between preprocessing and postprocessing in the future). Only a handful of values are currently defined. Other features:

New API

The mechanism for adding a new implementation is of main importance as the API is intended for both users (studios) and library writers (middleware providers), and the API has two parts respectively. One is targeted at users described above and the other at library writers.

The second interface forms a sort of Library Development Kit and provides features for easily dealing with the flexible graph format. Using it also allows interchanging an implementation for a better one without the need to recompile the game or even use several implementations simultaneously (e.g. one library is faster but doesn't implement all the API functions).

Understanding the API Through a Trivial Example 

// The API
#include "ais.h"

// Define the node and vertex format at run-time
// a 2D waypoint graph with a single weight for each connection
const AISNodeFormat gFNF = AISNODE_POSITION(AISTYPE_FLOAT, 2);
const AISConnFormat gFCF = AISCONN_WEIGHTS(AISTYPE_FLOAT, 1);

struct CNode{
	AISVector2Float v;		// same as float x,y;
};

struct CConnection
{
	UINT32 mNodeFrom;
	UINT32 mNodeTo;
	float mWeight;
};

// Use the factory to create a graph object that will hold all
// these connections and nodes (we use the ref. implementation)
ais_CGraph graph = GetAis()->CreateGraph(AISIMP_GENERIC,
gFNF, gFCF, gMaxNodes, 0);

// Insert nodes and connections into the graph
graph->SetNodes(0, gNumNodes, gNodes);
graph->SetConnections(gNumConnections, gConnections);

// Optimize graph structure to get better performance
graph->Process();

// Perform 2 pathfinding queries on the graph in a batch
ais_CQuery query1 = graph->AddQueryFindPath(StartNode, EndNode);
ais_CQuery query2 = graph->AddQueryFindPath(StartNode, EndNode2);
graph->FlushOperations();

// Get the result of the first query
UINT32 resultSize = graph->GetQueryResults(query1, buffer, true);

Group Members

Current members of the working group on steering:

 

Navigation: Overview >> Working Group on Pathfinding