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:
  1. Pre-integration
  2. Receiving data from the networking, and applying forces/velocities according to physical constraints.
  3. Integration to the end of the tick.
  4. 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.
  5. Resolution of the first (chronologically) collision. This modifies the velocities of the affected objects.
  6. Validation of the collision list.
  7. Detection of new collisions caused by the resolution of the collision
  8. Looping from step three until there are no more collisions unresolved.
  9. Sending updated data out to the networking interface.
  10. Looping from one until the simulation is complete.

Greater Detail:

  1. 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.
  2. Receiving data from networking. This basically applies appropriate forces, velocities, positions, etc... to objects, according to established physical parameters (max accelerations, etc)
  3. 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).
  4. 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).
  5. 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.
  6. 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.
  7. 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.
  8. This loop is repeated until all collisions have been resolved, i.e. the collision list is empty.
  9. 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.
  10. 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).