Detailed Description

Cooperative pathfinding is used to calculate paths for agents in such a way that collisions between the agents are minimized.

This is achieved by instead of searching only on a graph of nodes searches are done on (node,time) pairs (up until some fixed time into the future for performance). When an agent has calculated a path, it will reserve all nodes it will visit for exactly the times it will occupy that time. So a path going through nodes A, B and C will reserve A at time 0, B at time 1 and C at time 2. Since agents reserve whole nodes, cooperative pathfinding works best for grid graphs where the agents have roughly the same size as a single node. However it might be suitable to use point graphs for some games. Cooperative pathfinding works on navmesh based graphs, however it doesn't make that much sense since the nodes (triangles) in navmesh based graphs can vary a lot in size.

Since the agent needs to know exactly where it will be in the future, special movement scripts need to be used. The regular movement scripts only follows the paths, but they give have any guarantees that they will reach specific points at specific times. The CooperativeAI script can be used for this purpose. It will make sure that the agent reaches the correct nodes at the correct times. A limitation of cooperative pathfinding is that all units need to move at exactly the same speed of one node per tick. There are plans to extend this to work at multiples and simple fractions of the default speed (e.g 2, 3, 1/2, 1/3 times the tick).

If you are writing your own movement scripts, cooperative pathfinding also requires a special path type, the CooperativeABPath. It works as a drop in replacement for the regular ABPath, but it takes the cooperative pathfinding information into account.

You will also need to attach the CooperativeContext component to the same GameObject that has the AstarPath component. That component holds the reservation table mentioned above and has some additional options.

Todo:: Add list of limitations here (see blog post below in the meantime)

See also: http://arongranberg.com/2015/06/cooperative-pathfinding-experiments/; "Cooperative Pathfinding" by David Silver, Department of Computing Science, University of Alberta

Classes
class	Agent

class	CooperativeNNConstraint

class	CooperativePathData

struct	Entry
	(node,time) pair More...

interface	IAgent

struct	Item

struct	SearchChainElement

Public Types
enum	Mode { ReduceCollisions, ReduceWaits }
	See #mode. More...

Public Member Functions
IAgent	AddAgent (Vector3 position)

int	GetReservation (GraphNode node, int time)
	Returns the pathID which has reserved the specified node at the specified time. More...

Public Attributes
List< Agent >	agents = new List<Agent>()

bool	prioritizeRightHandTraffic = true
	Choose a preferred side of narrow corridors to help resolve congestion faster. More...

int	softReservationPenalty = 1000
	Penalty to use for soft reservations. More...

int	temporalDepth = 30
	Maximum number of time steps to be used in path planning. More...

float	tickLength = 1
	Length in seconds of each tick. More...

Properties
int	Tick `[get]`
	Current tick. More...

float	Time `[get]`
	Current tick with the fractional part. More...

Private Member Functions
void	AddAgent (Agent agent)

List< Agent >	FindTrail (Dictionary< GraphNode, Agent > node2agent, Agent agent, out Agent blockingAgent, out bool isCycle)

PathHandler IPathHandlerProvider.	GetNewPathHandler (int threadID, int totalThreadCount)
	Returns a new CooperativePathHandler. More...

void	Init ()

void	OnDrawGizmos ()
	Draw nice visualizations for the reservation table. More...

void	OptimizePath (CooperativePathData path)

void	PostPathCalculated ()

void	RemoveAgent (Agent agent)

void	RemoveReservation (GraphNode node, int time, int pathID)
	Remove reservation for the node at the specified time if it is currently reserved by the pathID. More...

bool	RemoveReservation (CooperativePathData path)
	Remove reservations which were added with Reserve(CooperativeABPath) More...

bool	RemoveReservationInternal (CooperativePathData path)

void	Reserve (GraphNode node, int time, int pathID, bool hard, bool fromEnd)
	Reserves the node at the specified time with a pathID. More...

void	Reserve (CooperativePathData path)
	Reserve all (node,time) pairs which the path will occupy. More...

List< SearchChainElement >	SearchForChain (Dictionary< GraphNode, Agent > node2agent, Agent agent, Agent firstAgentInOriginalChain, int maxCost)

void	TickTime ()
	Advance tick by one. More...

void	TryToMove (Dictionary< GraphNode, Agent > node2agent, Agent agent)

void	Update ()
	Increments tick every tickLength seconds. More...

Static Private Member Functions
static void	RemoveFromIndex< T > (List< T > ls, int index)

Private Attributes
System.Object	lockObject = new System.Object()
	Provides thread synchronization. More...

Dictionary< GraphNode, Agent >	node2agent = new Dictionary<GraphNode, Agent>()

List< Entry > []	reservationDropList
	Cyclic queue of entries to be removed. More...

Dictionary< Entry, int >	reservations = new Dictionary<Entry, int>()
	Space-time reservation table. More...

System.Random	rnd = new System.Random()

int	tick
	Current tick. More...

double	time
	Current tick, including fractional part. More...

Member Enumeration Documentation

◆ Mode

enum Mode

strong

See #mode.

Enumerator
ReduceCollisions
ReduceWaits

Member Function Documentation

◆ AddAgent() [1/2]

void AddAgent ( Agent agent )

private

◆ AddAgent() [2/2]

IAgent AddAgent ( Vector3 position )

◆ FindTrail()

List<Agent> FindTrail	(	Dictionary< GraphNode, Agent >	node2agent,
		Agent	agent,
		out Agent	blockingAgent,
		out bool	isCycle
	)

private

◆ GetNewPathHandler()

PathHandler IPathHandlerProvider. GetNewPathHandler	(	int	threadID,
		int	totalThreadCount
	)

private

Returns a new CooperativePathHandler.

Called by the AstarPath class during Awake.

Implements IPathHandlerProvider.

◆ GetReservation()

int GetReservation	(	GraphNode	node,
		int	time
	)

Returns the pathID which has reserved the specified node at the specified time.

Zero is returned if there is no reservation. A negative pathID is returned if it is just a soft reservation.

◆ Init()

void Init ( )

private

◆ OnDrawGizmos()

void OnDrawGizmos ( )

private

Draw nice visualizations for the reservation table.

◆ OptimizePath()

void OptimizePath ( CooperativePathData path )

private

◆ PostPathCalculated()

void PostPathCalculated ( )

private

◆ RemoveAgent()

void RemoveAgent ( Agent agent )

private

◆ RemoveFromIndex< T >()

static void RemoveFromIndex< T >	(	List< T >	ls,
		int	index
	)

staticprivate

◆ RemoveReservation() [1/2]

void RemoveReservation	(	GraphNode	node,
		int	time,
		int	pathID
	)

private

Remove reservation for the node at the specified time if it is currently reserved by the pathID.

◆ RemoveReservation() [2/2]

bool RemoveReservation ( CooperativePathData path )

private

Remove reservations which were added with Reserve(CooperativeABPath)

◆ RemoveReservationInternal()

bool RemoveReservationInternal ( CooperativePathData path )

private

◆ Reserve() [1/2]

void Reserve	(	GraphNode	node,
		int	time,
		int	pathID,
		bool	hard,
		bool	fromEnd
	)

private

Reserves the node at the specified time with a pathID.

Parameters

node	Node to reserve
time	Tick to reserve the node at (see Tick)
pathID	Path which reserves this node
hard	If false, only a penalty will be applied (see softReservationPenalty)

◆ Reserve() [2/2]

void Reserve ( CooperativePathData path )

private

Reserve all (node,time) pairs which the path will occupy.

◆ SearchForChain()

List<SearchChainElement> SearchForChain	(	Dictionary< GraphNode, Agent >	node2agent,
		Agent	agent,
		Agent	firstAgentInOriginalChain,
		int	maxCost
	)

private

◆ TickTime()

void TickTime ( )

private

Advance tick by one.

◆ TryToMove()

void TryToMove	(	Dictionary< GraphNode, Agent >	node2agent,
		Agent	agent
	)

private

◆ Update()

void Update ( )

private

Increments tick every tickLength seconds.

Member Data Documentation

◆ agents

List<Agent> agents = new List<Agent>()

◆ lockObject

System.Object lockObject = new System.Object()

private

Provides thread synchronization.

◆ node2agent

Dictionary<GraphNode, Agent> node2agent = new Dictionary<GraphNode, Agent>()

private

◆ prioritizeRightHandTraffic

bool prioritizeRightHandTraffic = true

Choose a preferred side of narrow corridors to help resolve congestion faster.

In narrow corridors agents will be penalized for moving on the left side of the corridor. This will have the effect of agents being less likely to cross paths and thus congestion will usually be reduced. It has a slight performance impact.

This effect is present everywhere that there are walls, not just in corridors. However it is in corridors that it matters the most.

◆ reservationDropList

List<Entry> [] reservationDropList

private

Cyclic queue of entries to be removed.

When the time for an entry has passed it will be removed to avoid storing entires forever.

◆ reservations

Dictionary<Entry, int> reservations = new Dictionary<Entry, int>()

private

Space-time reservation table.

Each entry specifies the path ID which has reserved the specified node at the specified time

See also: Reserve

◆ rnd

System.Random rnd = new System.Random()

private

◆ softReservationPenalty

int softReservationPenalty = 1000

Penalty to use for soft reservations.

Soft reservations are used when #mode = ReduceWaits and the agent is waiting or standing still. This will discourage other agents from using the same node at the same time, but it will not prevent the agent from doing that. This will reduce the times the agents get stuck waiting for a long time however it can lead to more collisions.

A penalty of 1000 is roughly equal to the cost of walking one world unit.

◆ temporalDepth

int temporalDepth = 30

Maximum number of time steps to be used in path planning.

A higher number increases both memory usage and the time to calculate a path. The memory usage increases linearly so a temporal depth of 20 will use roughly twice as much memory as a temporal depth of 10. Higher values will also make path searches slower.

Recommended values lie between 8 and 50 (very soft limits). A higher value will make the agents able to resolve more complicated situations however it may reduce the responsiveness of the agents and sometimes simpler situations will take longer to resolve. A lower value will make the agents more naive.

This value cannot be changed during runtime.

◆ tick

int tick

private

Current tick.

◆ tickLength

float tickLength = 1

Length in seconds of each tick.

All units will move a single node per tick

◆ time

double time

private

Current tick, including fractional part.

Property Documentation

◆ Tick

int Tick

get

Current tick.

Incremented by one every tickLength seconds.

See also: Time

◆ Time

float Time

get

Current tick with the fractional part.

See also: Tick

The documentation for this class was generated from the following file:

/Users/arong/Unity/a-pathfinding-project/Assets/AstarPathfindingProject/Core/Cooperative/CooperativeContext.cs

Detailed Description

Classes

Public Types

Public Member Functions

Public Attributes

Properties

Private Member Functions

Static Private Member Functions

Private Attributes

Member Enumeration Documentation

◆ Mode

Member Function Documentation

◆ AddAgent() [1/2]

◆ AddAgent() [2/2]

◆ FindTrail()

◆ GetNewPathHandler()

◆ GetReservation()

◆ Init()

◆ OnDrawGizmos()

◆ OptimizePath()

◆ PostPathCalculated()

◆ RemoveAgent()

◆ RemoveFromIndex< T >()

◆ RemoveReservation() [1/2]

◆ RemoveReservation() [2/2]

◆ RemoveReservationInternal()

◆ Reserve() [1/2]

◆ Reserve() [2/2]

◆ SearchForChain()

◆ TickTime()

◆ TryToMove()

◆ Update()

Member Data Documentation

◆ agents

◆ lockObject

◆ node2agent

◆ prioritizeRightHandTraffic

◆ reservationDropList

◆ reservations

◆ rnd

◆ softReservationPenalty

◆ temporalDepth

◆ tick

◆ tickLength

◆ time

Property Documentation

◆ Tick

◆ Time