Algorithm for iterative hit checking each frame
Since there are many moving vehicles in one frame, we need a good algorithm to hit check and advance all the vehicles in a mostly parallelized manner. A colliding vehicle will have a new velocity vector that could collide with something else, so multiple iterations are required. The goal of this algorithm is to provide for this while minimizing the cost of extra calculations should a vehicle collide.
Blueprint information
- Status:
- Started
- Approver:
- None
- Priority:
- High
- Drafter:
- None
- Direction:
- Approved
- Assignee:
- David Schneider
- Definition:
- Approved
- Series goal:
- None
- Implementation:
-
Good progress
- Milestone target:
- None
- Started by
- David Schneider
- Completed by
Related branches
Related bugs
Sprints
Whiteboard
1) Parallel: Do hover/gravity phase. Calculate velocity and generate frame velocity vector (a percentage of the velocity).
2) Sequential: For each vehicle, add to the octree a "MovingVehicle" object, which is the hitsphere of the vehicle swept along the frame velocity vector.
3) Parallel: If this is the first iteration, or the vehicle collided on the previous iteration, do a full, octree-based forward check using frame velocity vector. If this is the second collision, and the vehicle didn't collide the last iteration, only do a check against the vehicles that had a collision in the past iteration (and take into account the collision that may have been calculated previously for a later time in the frame). If there are any collisions, save, flag and mark the time t in the frame that the collision takes place. Collisions with MovingVehicles have to be more precisely calculated to see if the collision actually happens temporally.
4) Sequential: Remove the "MovingVehicle" objects from the octree and find the min of the collision times t.
5) Parallel: Move the vehicles along their frame velocity vector, up to time t. If the collision ocurrs for this vehicle (the saved one at time t), calculate the new velocity and frame velocity vector.
6) Sequential: If a collision was flagged for this iteration, repeat from 2.
