Obstacle avoidance

Thus far in the development collision avoidance has been shown to be crucial to achieving realistic flock-like behaviour. One of the benefits of decentralised flocking behaviour is collision free travel, a benefit with applications in the field of decentralised air traffic control systems. Collision avoidance can be thought of as a force field that surrounds all agents (with a radius equal to that of the radius of perception) that increases in strength towards the central agent's loci. One technique for implementing obstacles in the agents' environment would be to surround each obstacle in the scene with a force field similar to that of the agent collision avoidance desire. This method would certainly fit very nicely with the current simulation as obstacles could simply be modelled as stationary forms of agents (these pseudo agents would only exist to repel neighbours and would play no part in cohesion or alignment calculations). As has been show by Reynolds, "the motion produced by this technique does not correspond very well to our intuitive notion of steering around obstacles".

For proof Reynolds considers the case of an agent moving on a collision course with an obstacle directly through the normal of the obstacle's force field. The resulting agent motion would be a slow deceleration as the agent towards the obstacle followed by a smooth acceleration as the agent moves away from the obstacle (still in the direction of the normal). The discrete area along the obstacles normal is known as the force fields 'black spot'. Intuitively we expect agents to avoid obstacles by choosing to move around either the right or the left hand side of the object, making this choice as soon as the obstacle falls within the area of perception. The force field model breaks this convention.

In his paper Not Bumping Into Things, Reynolds settles on one technique for obstacle avoidance that produces more realistic results: Steer towards silhouette edge. Originally developed to steer 'boids' in a 3D space, this technique shaves a silhouette from the obstacle (the outline of the object that can be seen from the agent's perspective) and then finds the edge of the silhouette closest to the agent's current heading. In 2D space the complexity of this operation is reduced to a single plane of view.

The 'steer towards [...] edge' strategy is the technique I shall use to implement obstacle avoidance. There is one case whereby this strategy will be made redundant - when no edges fall within the agents area of perception. Rather than cheating by extending this area, I shall fall back on another of Reynolds's behaviours: Steer along surface, a simple strategy that agents can use to navigate along side the face of an object until an edge becomes visible. The traversal direction depends on the angle subtended between the obstacle and agent normal. In the case of an agent moving along the obstacles 'black spot' a random left/right choice will be made.

Obstacle avoidance requirements