c_Stage is the stage class of Gemini Engine.


This class is designed to hold information about the stage such as terrain, objects, boundaries and resources. Additionally, collision detection is conducted from this class.

Separate stages are created by inheriting this class and redefining functions as needed.


Visual of the Separating Axis Theorem


This algorithm works on the principle of the Separating Axis Theorem. Without going into a detailed proof, the SAT states that for any 2 convex polygons, we can be sure that there is no overlap if a straight axis can be drawn between the shapes, separating them. An example is on the diagram to the right, which lays out why this theorem works in a more intuitive manner.

The ideal thing about this algorithm is that the engine does not need to always run through every step. As soon as an appropriate axis is found that separates the polygons there is a guarantee that no collision takes place, and the algorithm can end. Since this is the more likely case, this ensure the algorithm can end early, often

The Code

Lifted on 8/14/2014 ver


ideal axis locations

This function is a helper function for collision detection. There are infinite locations we could put the axis, but the only locations that are needed are lined up against a side of the polygon in question, as in the diagram on the right. There should be one axis per polygon side.

Both polygons are projected onto an axis perpendicular to the one that is given; their position being their 'distance' from the separating axis. In order to save processing, only the projected locations of the shapes is looked at; if they overlap there may intersection and if they do not, there is no intersection. This is efficient, and can be especially seen with rectangles.

This is located in the player class, so that only one function needs to ever be used. All collisions will involve a player somehow (and some will not involve the stage, like attack collisions)

Step by Step Through the Code

    bool hitflag;
    int polyIndex = -1;//to keep record of which polygon caused the collision
    int hitIndex = -1;//to keep record of which side of the polygon caused collision
    SPoint plBox[4], plLast[4];
    double plAng[4] = {0, M_PI/2, M_PI, -M_PI/2};//store angles related to player hitbox for efficiency

Definining needed variables ahead of time.

hitflag= a flag to switch when an axis that indicates collision has been found.
polyIndex = to keep record of what polygon caused the collision. Keeps sentinel value of -1 if no such polygon exists.
hitIndex = Same thing, applies to the side of a polygon (and indicates the axis used, since one axis per side)
plBox = current location of player. May collide with stage
plLast = last known location of player, gained during the Post-Update phase. Does not collide with stage
plAng = record the angular direction the sides of the player's hitbox runs. Since the player occupies an axis-aligned box, these run laterally and vertically.

 for(int i = 0; i < tBox.iLength; i++){
        hitflag = true;//assume true, then prove false.
        for(int j = 0; j < tBox.GetJlength(i); j++)
            if(!plr->CheckAxis(i, tBox.GetAsSPoint(i, j), tBox.GetAng(i, j), plBox) ){ //no axis intersection
                hitflag = false;
                j=tBox.GetJlength(i);//exit loop early
        if(hitflag)//possible collision; check against other polygon axise
            for(int j = 0; j < 4; j++)
                if(!plr->CheckAxis(i, plBox[j], plAng[j], plBox) ){ //no axis intersection
                    hitflag = false;
                    j=4;//exit loop early
        if(hitflag){//all checks are done, collision is sure
            polyIndex = i;//keep record of the last polygon caused the flag
            i=tBox.iLength;//Collision detected, end loop early

hitflag is used to hold the results of CheckAxis, which can return as one of 2 values

true - intersection has occurred
false - no intersection has occurred, but another step is warranted

Since the first separating axis will determine a case of no collision, we will force an exit to the first loop if it ever returns false. If CheckAxis returns true for all side of the polygon checked, then a collision is possible. To be sure, the sides of the player's hitbox must be checked in the same manner. So if hitflag returned true the second loop is entered in an attempt to disprove it.

If hitflag still remains true then a collision has occured. The polygon's index is recorded and the loop is forced to end.

       for(int i = 0; i < tBox.GetJlength(polyIndex); i++){
            if(!plr->CheckAxis(polyIndex, tBox.GetAsSPoint(polyIndex, i), tBox.GetAng(polyIndex, i), plLast)){
                hitIndex = i;
                i=tBox.GetJlength(polyIndex);//end loop prematurely
        bool pAxisFlag=false;
        if(hitIndex == -1){
            for(int i  = 0; i < 4; i++){//check player angs to find the axis
                if(!plr->CheckAxis(polyIndex, plLast[i], plAng[i], plLast) ){
                    hitIndex = i;
                    pAxisFlag = true; 
            }//do collision detection again for this particular index on the polygon
        }//to get the exit vector
        SPoint axP;        
            if(!pAxisFlag)//using poly axis
                axP = ExitDist(polyIndex, tBox.GetAsSPoint(polyIndex, hitIndex), tBox.GetAng(polyIndex, hitIndex), plr, false);
            else//using player axis
                axP = ExitDist(polyIndex, plBox[hitIndex], plAng[hitIndex], plr, false);

The first run through was only a brief check that tells that there was a collision, but not quite where. Because checking this is expensive it was skipped the first time. If a collision was recorded the if statement' if(polyIndex!=-1){' will be entered. Then all sides of the polygon, and all sides of the player will be checked again. Depending on where the player axis was used (in which case pAxisFlag will be set to false) determines how to obtain the exit vector from ExitDist(…). This function is similar to CheckAxis but with further detail about where the player should move to undo a collision.

If we did not record a hit after all retFlag is set to false to return false at the function's end.

if SPoint aXp holds an exit value it will be applied to the player, positioning them on the map appropriately.

 double axAng = atan2(axP.y, axP.x);
        float wallAng = atan2(plr->stats.motion.vel.y, plr->stats.motion.vel.x); 
        float wallDist = sqrt(pow(plr->stats.motion.vel.x, 2) + pow(plr->stats.motion.vel.y, 2) );
        wallAng -= axAng;

Here values are loaded up regarding the payer's momentum.
            double rbdVec = tBox.GetAng(polyIndex, hitIndex);
            if(rbdVec<=-M_PI)//keep within proper bounds
                plr->Land(tBox.GetAng(polyIndex, hitIndex));        
                plr->stats.motion.vel.x -= cos(wallAng)*wallDist*cos(axAng);
                plr->stats.motion.vel.y -= cos(wallAng)*wallDist*sin(axAng);
            if(axAng < M_PI)
                plr->Land(tBox.GetAng(polyIndex, hitIndex));        
            plr->stats.motion.vel.x -= cos(wallAng)*wallDist*cos(axAng);
            plr->stats.motion.vel.y -= cos(wallAng)*wallDist*sin(axAng);

This is code for landing. Note that if the player is in a tumble, and has not struck a surface the player will rebound off of that surface if the player is hitting the surface roughly head on. A check for this is made by plr->Rebound(rbdVec); if it returns false no rebound is possible (either because the angle of collision is too shallow, or the player rebounded once before) Either way the player tries to land and will then be repositioned along the wall.

If the player is not in tumble, the player is simply repositioned along the wall. A closer look at these lines of code:

plr->stats.motion.vel.x -= cos(wallAng)*wallDist*cos(axAng);
plr->stats.motion.vel.y -= cos(wallAng)*wallDist*sin(axAng);

details the math involved. This re positioning keeps the player sliding along the wall, instead of simply refusing to move.

            if(!GroundTrack(plr))//ground tracking done here
        retFlag = GrabDetect(plr);//grab checking done here

If the player is not airborne, one check to Groundtrack is made. This is a very similar function to CollisionDetect, except it repositions a character half their height up and determines any collision with the ground beneath them. If it fails the player will fall.

GrabDetect() functions in a similar way as well, but this applies to the GrabBox a player has, and is used for edgegrabbing.

 if((plr->GetPos().x > uBound.x)||(plr->GetPos().y > uBound.y)||(plr->GetPos().x < lBound.x)||(plr->GetPos().y < lBound.y)){
        plr->stats.motion.vel = SPoint(0,0);

This will determine if a player has been knocked out of bounds, and will reposition and remove a stock accordingly.

Finally, retFlag is returned. If it returns true. another iteration of this algorithm will occur. If no collision has been detected, retFlag will be false and the algorithm will end.

void c_Stage::FillCollisionBox(SPoint *plBox, SPoint pos, float h, float w);

A helper function to CollisionDetect(). This will take a player at position pos, and fill plBox as an array of vertices defining an axis aligned box.

SPoint c_Stage::ExitDist(int pInd, SPoint origin, double dir, c_Player *plr, bool ifGrab);


Similar to CheckAxis, except ExitDist will return an SPoint vector that will indicate a point of non-collision just outside of the specified polygon. This vector will always point perpendicular to the polygon side, as marked on the diagram

bool c_Stage::GroundTrack(c_Player *plr);

Specialized function, working on the same principles as CollisionDetect. GroundTrack() will simply take a player above, drop them to a position below and record where on the ground they collide (if they are not set to airborne) This ensure a player can follow slopes, and climb small bumps in terrain without stumbling.

I won't cover this now, because it should be explained by the notes I have left on CheckAxis. I will make a detailed post if needed -Chris