Dynamic path generation

Path generation differs from the path finding previously mentioned because the shape and length of the new path is not determined according to pre-determined information built into the game world. Rather, information about the game world is dynamically determined according to the current situation and used to generate the most appropriate path when required. Moreover, it is likely that this path will change over time, although this may cause unwanted camera movements. Dynamic paths are typically used in situations where standard navigation is unable to determine an appropriate movement.

Another technique for dynamic path generation is to use information garnered from the motion of the player character. In many situations, a history of player movement data may be used to derive a potential movement path for the camera. If it is known that the player has passed through a confined space (e.g., a doorway), the camera may clearly follow the same path.

However, such a path would likely present a very different view of the player than normally seen. Therefore, it may be necessary to generate a volume around the player movement points to find the potential limits of valid camera motion (e.g., as an extruded cylindrical volume). This volume would be used to present a view in keeping with the expected displacement of the camera from the player character.

Visibility and rendering solutions

With the advent of hardware-assisted rendering, a new variety of solutions became available for determination of the desired camera position. We start with the assumption that the final position for the camera will be somewhere relative to the target object, and that the desired position should have an unobstructed view of the target object.

Next, we add constraints for the distance and elevation of the desired position relative to the target object. This produces a cylindrical band of potential positions around the target object. Further constraints can be layered on top of these requirements, such as only allowing a certain angular displacement relative to the target object.

Given all these constraints, we now have a small subset of potential positions to be tested for viability. If we were to render the world from each of these potential positions such that the camera was oriented toward the target object, it would result in scenes that may or may not show the target object according to occluding geometry or game objects.

If, instead, we render these views so that the target object is drawn in an easily distinguishable (and unique) color, the rendered screen buffer may be analyzed to determine if the target object was occluded. If the object is sufficiently non-occluded, then we can consider the rendered camera position as a viable position. Other hardware-accelerated techniques may be used to determine the occlusion of the target object from each of the potential positions, including depth buffer analysis.

By exploiting the parallel nature of the graphics hardware, the cost of this determination may be significantly amortized. There are, however, some caveats to this approach. First, the setup for rendering the scene from each potential position may be prohibitive.

Second, although rendering via hardware is fast, it is certainly not free. The GPU and CPU cost may be reduced by techniques such as rendering the scene flat-shaded (i.e., no lighting), changing the view frustum to restrict the scene to only the area around the target object (including far clip plane distance), and reducing the resolution of the rendered scene.

Once we have determined which of our original potential camera positions is the most preferred, we can then calculate a path or other movement method to take the camera from its current position to the desired position. Although this technique works well in determining the position, it does not take into account geometry intervening between the current position and the desired position. Additional constraints may be applied to avoid these problems. A practical implementation of these techniques may be found in Halper.

Colliders

Colliders are a variant upon the standard ray casting techniques as previously mentioned. The principle here is that the positions from which the ray casts are made are variable. Each of these positions is enclosed within a small collision volume (typically a sphere or approximated to this by another ray cast).

These position objects are referred to as colliders, since they are constrained to stay within the environment. Usually the colliders will be arranged in a particular pattern around the camera, such as a circle or semi-circle. The colliders are constantly attempting to regain their desired positions relative to the camera's ideal position as the camera moves through the environment.

The arrangement of the colliders influences how the camera will react to the environment. Each collider casts a ray toward the look-at position of the camera, or alternatively some other pre-defined point relative to the player character. The result of the ray cast is used to offset the desired position of the camera motion. The amount of influence exerted by a collider may be based on a number of factors:

• The physical distance of the collider from the camera possibly calculated in local camera space and applied in the same manner.
• A pre-defined influence factor per collider determined according to the position of a particular collider within the entire group.
• The distance from each collider to the point at which its ray cast struck geometry.
• The acceleration or velocity of the player character, possibly only in one axis depending on desired behavior (e.g., change elevation according to player speed).

Some combination of the above factors may be applied to some or all colliders. Often there are several groups of colliders, each influenced by different factors. The ways in which the influence is applied also varies, possibly using a weighted average or a centroid calculation. Some experimentation will be required according to the types of environment encountered in a particular game.

Differing arrangements of these colliders may be used according to the type of behavior required for the environment. Circular or semicircular arrangements are common, as are horizontal ones. The arrangement may vary according to changes in the player character, most commonly velocity.

Colliders and other ray casting techniques are susceptible to "noise" produced by ray casts that collide with incidental environmental features that should not adversely affect camera motion. Some knowledge of the environment may be used to filter out results that should not influence camera motion. Tagging of surface properties may also be used to ignore or apply a reduced influence on the camera position determination.

Alternatively, surfaces may be tagged to act as motion constraints or to otherwise prevent the camera from approaching. The arrangement of the colliders and the amount of influence each applies may require changing according to the environment properties (e.g., confined spaces, vertical columns, etc.) or game play mode (e.g., to match changing movement characteristics of the player character).

Technical

Since the arrangement of colliders may vary considerably, here is only an outline of the algorithm used to determine their influence upon the desired camera position:

stl::vector influence;
// might be useful as a class
for (int i = 0; i < colliders.size(); ++i)
{
influence.push_back(colliders[i].offset *
colliders[i].GetWeighting());
// the weighting depends on line of sight and/or
// other factors such as the relative collider
// position
}
// will need to get an average or similar
return GetCentroid(influence);

The arrangement of colliders will change the calculation method used to determine the average amount of influence to apply. A centroid calculation works well if the colliders are constrained to a plane, but however the final influence is calculated, it must also be applied in the same space as the collider's offsets.