PathEngine home previous: Obstacle Managementnext: Performing Collision Queries without Preprocess
Contents, Programmers Guide, Applying the SDK, Collision Queries

Collision Queries

Point and line collision

The collision queries break down into two main categories, 'point' collision queries and 'line' collision queries.
As explained in The PathEngine Movement Model, point queries test whether an agent is obstructed at a given position, whereas line queries relate to movement along a line.
A number of line collision queries are provided with different functionality.

PathEngine then also supports querying for the closest point in unobstructed space to a given target point, with a number of different parameters and constraints.

Except for certain specific cases, collision queries require the generation of agent 'unobstructed space' (with iMesh::generateUnobstructedSpaceFor()).

Supplying a context

Each query accepts a collision context argument.
This controls the set of obstacles to be 'included' for the query.

Calling against the mesh or agent interfaces

In general, each query can be invoked on either the Interface iMesh or the Interface iAgent interface.
The iAgent methods supply arguments corresponding to the position and shape of the agent on which the method is called, and ensure that the agent itself is excluded from collision.

The queries

Basic point collision

iMesh::testPointCollision() and iAgent::testCollisionAt() provide basic point collision functionality.
This can be used to test whether an agent can be placed at a given position.

Obtaining a set of agents overlapped

iMesh::getAllAgentsOverlapped() and iAgent::getAllAgentsOverlapped() obtain a set of agents overlapped by the query agent.
This can be useful, for example, when using dynamic obstacles to implement switches or trigger systems.

Straightforward line collision

iMesh::testLineCollision() and iAgent::testCollisionTo() both provide a straightforward line collision test, with start and end positions both specified as positions on the surface of the ground mesh.
This version of the line collision can be used, for example, to see if movement is unobstructed from one agent to another, or to a known end position.

Movement in a direction

iMesh::testLineCollision_XY() and iAgent::testCollisionTo_XY() takes a start position on the surface of the ground mesh and x and y coordinates for the line end.
This is essentially a test for collision when moving in a direction from a known start position.
The query performs a traversal over the surface of the mesh to determine the actual end position with respect to overlapping geometry.

First collision

iMesh::firstCollision() and iAgent::firstCollisionTo() also take a start position on the surface of the ground mesh and x and y coordinates for the line end.
This is also essentially a movement in direction query.
This version does some extra work where necessary in order to obtain information about the point of collision.
This can be used then, to implement basic contact physics such as sliding against walls, or pushing obstacles.

Closest unobstructed point

There are essentially two versions of this query.

iMesh::findClosestUnobstructedPosition() and iAgent::findClosestUnobstructedPosition() find the closest unobstructed position to a specified target position on the mesh (or to current agent position), with only 'locally connected' ground mesh considered for the query.

iMesh::findClosestUnobstructedPositionEx() then extends this base query to add some additional possibilities such as the possibility to find unobstructed points close to arbitrary points in 3D, and to add unobstructed space connectivity constraints to the query.

This functionality is essential for pathfinding to or from positions that may be outside pathfinding unobstructed space for the pathfinding agent shape, for example in cases where large agents chase smaller agents, or when agents move under the control of an external collision system.

And this can also be very useful as a component for constructing quite a wide variety of different movement based behaviours, for example attack target slot generation when multiple agents are assigned to attack a target and should not overlap, finding 'escape' positions outside of arbitrary danger shapes, and so on.


The collision queries are very fast, so these can be used (in addition to managing agent movement) for generate and test style algorithms.
The path post processing is an example of this. In this case, curved paths are generated from a base path, and then tested for collision.
Speculative generate and test approaches can also be applied very effectively for highly interactive behaviours, such as dodging bullets and so on.

Documentation for PathEngine release 6.00 - Copyright © 2002-2016 PathEnginenext: Performing Collision Queries without Preprocess