In order for the animation functions to remain as high level as possible, the engine must perform any collision detection necessary. For this application, it shall be assumed that the only collision detection necessary is that between the character and the edge of the path. The animation engine must implement this constraint so that it is physically impossible for the user to leave the path.
This simplification of collision detection allows other constraints, such as collision with buildings, to be ignored, as the virtual agent will never come into contact with any buildings or other structures if it is restrained to using the pre-defined paths. A description of the method in which the model is kept on the path follows.
Once the world file has been parsed and is stored in the form shown in the class diagram of Figure 4.4, one of the model objects will be assumed to contain the polygons and vertices of the path upon which the agent must be kept.
Each polygon object has a member function which, when passed a co-ordinate, will return true if the point is inside its edges, or false otherwise. This can be used for testing if the character's planned movement will take them off the path. Movement will only be permitted if the agent will remain on a path polygon.
However, since there could potentially be hundreds of path polygons in even a trivial environment, testing each one every frame of animation is clearly extremely inefficient. Therefore the following algorithm will be used to drastically reduce the number of polygons it is necessary to test each frame.
Upon loading of the world file each of the path polygons is examined in turn, and an index array of its neighbouring polygons built. Then, during animation, as well as the agent's current and desired position co-ordinates, the current index into the path polygons array is maintained.
At each frame the desired position is first tested for being inside the current polygon, and then its surrounding polygons. Movement is allowed immediately if the desired position is still inside the current polygon and, since movement is extremely incremental, most cases will fall into this category. If this is not the case however, each of the current polygon's neighbours is examined in turn. If the desired position is not in any of them then movement is disallowed, otherwise movement is allowed, and the current polygon index is updated to reflect the agent's crossing into a new polygon.
This method requires, in the worst case, N polygons to be tested at each frame (where N is the number of vertices of the current polygon), a huge improvement over having to test the entire path at each frame.
The decision as to whether two polygons are neighbours can be made by examining pairs of edges, and determining if the two polygons share an edge. The index of polygons and their neighbours is implemented using a two dimension <vector> container.