Titans Project Proposal
From EQUIS Lab Wiki
Up to The Titans
Contents |
Realistic Physics Modelling in a Third-Person Video Game
The Titans
CISC 864 Video Game Development
20 January 2006
The Team
The members of the Titans are Paul Schofield and Kevin Kassil.
Project Proposal
This project has two main goals: modelling the rules of physics, and three-dimensional collision detection. The Open Dynamics Engine will be used to achieve both objectives. The ODE is a programming library that allows a simulation designer to model entities as rigid bodies. The bodies respond to applied forces and torques, and interact when a collision occurs. The engine uses numerical methods to compute the entities’ orientations as they vary over time.
ODE provides an API for the C language. ODE represents each entity with two separate structures. A body characterizes the properties relevant to the dynamics of the object such as mass and moment of inertia. The geom represents an entity’s physical shape, which is necessary for detecting collisions.
We plan to augment the data structure for each entity with references to the corresponding body and geom structures in the ODE engine. (This plan will be re-assessed once the code base is made available.)
Dynamic entities are tentatively defined as
- player characters,
- non-player characters, and
- objects that can be picked up.
Static entities are tentatively defined as
- Resources such as trees and gold mines,
- (Scenery) rocks, etc., and
- Geometric faces of the polygonal mesh of a building.
Note: the previous entity definitions are based on a fresh analysis, and may change once the design of the existing system is made available.
Both player and non-player characters may jump or fall. This can be modelled with gravitational forces. The gravitational constant can be a parameter of the “zoneâ€. This would be useful if another group extended the world to contain multiple zones.
Another aspect of a “realistic†physics model is providing realistic character movement. The character’s speed should be impacted by the grade of terrain. When ascending a hill, it should decrease, and reach zero if the hill is too steep. Conversely, when descending a hill, the character’s speed should increase.
Based on observing video clips of the game, the player character appears to run up impossibly steep hills at breakneck speeds. Our guess is that the velocity vector of the character lies in the XY plane, instead of being parallel to the terrain.
A character could “lose his balance†and fall if he runs too quickly a down a hill. The probability of tumbling is proportional to the character’s speed and grade of the terrain.
Three-Dimensional Collision Detection
Based on Nick’s verbal explanation, we understand the current collision detection is a two-dimensional position constraint. In other words, for each obstacle, the character must not intersect with a shape defined in the XY plane, and extruded infinitely upwards.
Any pair of entities, where at least one is dynamic, may potentially collide. Table 1 illustrates the types of entities which may collide.
Player Characters NPCs Trees Scenery Buildings Player Characters x x x x x NPCs x x x x x Trees x x Scenery x x Buildings x x
Table 1: Pairwise Collisions by Entity Types
Optimizations
There are a number of foreseeable technical issues. One such issue could arise with a large number of entities in the zone (or world). Any pair of entities, where at least one is dynamic, may potentially collide. The ODE engine provides an efficient data structure so that the complexity of performing collision detection in each time-step is better than <math>O(n^2)</math>, where <math>n</math> is the number of dynamic and static entities in the physics model.
A related optimization strategy for ODE concerns the physical dynamics component of the engine. Since the position of each dynamic entity must be computed in each time step, we have <math>O(d)</math> complexity in each time step. However, entities that are not moving can be disabled. In practice, this reduces the number of entities that must be updated in each step.
