Introduction
This section of the documentation will give a short introduction to collision detection and how it is implemented in this library. It is recommended to have understood the concepts, in order to estimate what optimizations to use and to know, which option is appropriate for a given situation. This collision detector uses 2d primitives such as circles, rectangles or polygons, to determine, when objects collide with each other.
Some optimizations have been used, to reduce the amount of computations needed to find the collisions, the first one is having collision groups. Imagine a scene of a car racing game for example, with lots of background objects, that do not move compared to each other, like walls, trees or houses for example. These objects do not have to be checked for collisions with each other, so they can be put in the same collision group. Collision detection is divided in two steps, the first one is a rough collision detection, which determines, if two collidables can possibly collide, the second step is the exact collision detection with returned collision points.
First Step of Collision Detection
In this step the collision detector checks if two collidables can possibly collide with each other, all others are omitted from further investigation. Every collidable has a bounding circle (or circumcircle), which describes the maximum distance (radius) to its center. If the added radii are greater than the distance of both centers, the collidables can not collide, otherwise they could possibly collide, which will be checked in step two.
Second Step of Collision Detection
In this step the collision detector checks if two collidables intersect (overlap), using 2-dimensional primitives assigned to objects. If they overlap, the intersection point is computed - this point is the average of the first two found intersections of the edges. A set of sets of collisions is generated upon detection, which will be saved in last_collisions. All objects, that intersect with each other are put in a EM_COLLISION_COMPOSITION, which is needed to do proper collision handling.
Detecting Collisions
Collisions are detected using the Separating Axis Theorem (SAT) which states that, given two convex shapes, if we can find
an axis along which the projection of the two shapes does not overlap, then the shapes don't overlap. Given the following
collidables, we would like to check whether they overlap or not.
The projection along the first axis overlaps, this means it is still possible for the two objects to collide.
The benefits of this method, compared to others, is that non-colliding objects fall out quickly and the whole algorithm
does not have to finish in that case.
Since the projections do not overlap we know that these two objects do not collide.
After having detected a collision we would also like to know the intersection point, if there is one - which is not the case, if one object is included in the other one. This is done by comparing each line of the shapes with each other, until at least two intersections were found, then the average of those intersections, including the direction is returned.
Motion
There are two problems with collision detection, when having moving collidables in the scene. The reason is, that we don't have infinitesimal small steps between two so-called frames. One of the problems is, that objects can "jump" through others, or return false intersection points due to too big steps, if we are looking for the first intersection.
The first problem can be come by, by checking the lines of the path for intersections with the other object and its path line - whereas a path line is a line from the center of the object to where the center was at the last frame. If there is an intersection the objects might have intersected some time between the frames. This method is not absolutely correct, but in the very most cases it will find these intersections, but since this is a real-time collision detection and not a simulation this is ok. If time permits, the convex hull of the last and current position of the collidable would be taken and checked for intersections. After a potential intersection in between both steps has been found, the collidables are tested at different times between the end positions. The first check is done at time 0.5 (which means in the middle of the frame) and both collidables are placed there and checked for intersections. If no intersection was found, the objects are again placed in the middle of both subsections and the procedure is repeated, until the depth of the breadth-first search has reached movement_check or an intersection has been found. This results in 2^movement_check intersection checks, so this depth should be chosen with care.
The second problem is that of finding the first intersection point of two moving objects. This is done using the bisection method with a depth of search_depth.
Bon Diagram
One might assume, that the collidable objects inherit from their EiffelMedia counterpart (like EM_CIRCLE_COLLIDABLE inherits from EM_CIRCLE), but this is not the case. The reason was the internal representation of the object, which was not compatible with the requirements
of optimization for the collision detection. However each collidable has the function to return its EiffelMedia counterpart