Algorithm Guide
High and Mid-Level CRISS algorithm reference:
This document serves to explain in simple abstract terms the primary
algorithms used for dynamics simulation in CRISS. It does not give the
exact mathematical formulas as they are irrelevant (those are only useful
for the low-level, very specific algorithms). It describes the overall
process used to handle motion, collisions, and non physical conditions.
The Main Loop:
The main loop consists of the following steps:
- Pre-integration
- Receiving data from the networking, and applying forces/velocities
according to physical constraints.
- Integration to the end of the tick.
- Detection of all collisions that occurred during the tick. (as a result
of objects moving under no acceleration) This inserts them into a sorted
list.
- Resolution of the first (chronologically) collision. This modifies the
velocities of the affected objects.
- Validation of the collision list.
- Detection of new collisions caused by the resolution of the collision
- Looping from step three until there are no more collisions unresolved.
- Sending updated data out to the networking interface.
- Looping from one until the simulation is complete.
Greater Detail:
- Pre-integration is the process of storing information about the current
position/rotation of an object, and the current time. This allows the
integrator to integrate from the "last known position" of the object. This
is essential to the architecture, as it allows us to handle discontinuities
in velocities that occur during infinitesimal-time collisions.
- Receiving data from networking. This basically applies appropriate
forces, velocities, positions, etc... to objects, according to established
physical parameters (max accelerations, etc)
- Integration to the end of the tick. This is simply the use of a last
known position/orientation of an object, along with its velocities to
displace it, moving it to its new position, corresponding to a given time
(in this case, the undo the tick).
- Detection of all collisions. This basically tests to see if each
circle is colliding with any lines or other circles (the test is efficient
in that each candidate collision-pair is only tested once).
- Resolution of the first collision. This is rather complex. The
affected objects are integrated backwards to the time of collision. Their
velocities are changed by the collision, and their new "starting point" is
saved by pre-integrating them. This solves the problem of integrating
discontinuous velocities. They are then integrated forward to calculate
their new positions at the end of the tick.
- Validation of the collision list. Every collision in the collision
list that contained one or more of the affected objects is validated to
insure accuracy. Most likely they will now be inaccurate, and will be
thrown out.
- Detection of new collisions. The affected moving objects are tested in
their new positions for collisions with other objects. These are inserted
into the collision list.
- This loop is repeated until all collisions have been resolved, i.e. the
collision list is empty.
- The physics simulation, at the end of each cycle, encapsulates a
snapshot of the current situation, and returns a vector containing this
snapshot. The translational and rotational positions and velocities of all
moving objects in the simulation are recorded in the vector, so that
networking can provide feedback to the AI system.
- This one-step process is continuously looped throughout the lifetime
of the simulation.
Collision Detection:
For the purpose of collision detection, there are several algorithms that
are used. For speed/efficiency purposes (which proved to be largely irrelevant).