Class CooperativeContext Extends MonoBehaviour, IPathHandlerProvider

Public

Cooperative Pathfinding.

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

http://arongranberg.com/2015/06/cooperative-pathfinding-experiments/

"Cooperative Pathfinding" by David Silver, Department of Computing Science, University of Alberta

Inner Types

(node,time) pair

Public Methods

AddAgent (position)
Public
GetReservation (node, time)

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

Public

Public Variables

agents
Public
optimizePaths

Try to optimize paths whenever an agent would stand still.

Public
prioritizeRightHandTraffic

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

Public
softReservationPenalty

Penalty to use for soft reservations.

Public
temporalDepth

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

Public
Tick

Current tick.

Public
tickLength

Length in seconds of each tick.

Public
Time

Current tick with the fractional part.

Public

Public Enums

Mode

See #mode.

Public

Private/Protected Members

AddAgent (agent)
Private
FindTrail (node2agent, agent, blockingAgent, isCycle)
Private
GetNewPathHandler (threadID, totalThreadCount)

Returns a new CooperativePathHandler.

Private
Init ()
Private
lockObject

Provides thread synchronization.

Private
node2agent
Private
OnDrawGizmos ()

Draw nice visualizations for the reservation table.

Private
OptimizePath (path)
Private
PostPathCalculated ()
Private
RemoveAgent (agent)
Private
RemoveFromIndex< T > (ls, index)
Private Static
RemoveReservation (path)

Remove reservations which were added with Reserve(CooperativeABPath)

Private
RemoveReservation (node, time, pathID)

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

Private
RemoveReservationInternal (path)
Private
reservationDropList

Cyclic queue of entries to be removed.

Private
reservations

Space-time reservation table.

Private
Reserve (path)

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

Private
Reserve (node, time, pathID, hard, fromEnd)

Reserves the node at the specified time with a pathID.

Private
rnd
Private
SearchForChain (node2agent, agent, firstAgentInOriginalChain, maxCost)
Private
tick

Current tick.

Private
TickTime ()

Advance tick by one.

Private
time

Current tick, including fractional part.

Private
TryToMove (node2agent, agent)
Private
Update ()

Increments tick every tickLength seconds.

Private