liblashgame

Pathfinder and path decision making library for 2D tile game
git clone git://holbrook.no/liblashgame.git
Info | Log | Files | Refs

tmp_collision.c (7538B)


      1 #ifndef COLLISION_H_INCLUDED
      2 #define COLLISION_H_INCLUDED
      3 #include <vector>
      4 #include <cmath>
      5 
      6 float * get_limits(float *o_limit, float * o) {
      7 
      8     // only pairs!
      9     if ((sizeof(o) / sizeof(float)) % 2 != 0)
     10        return nullptr;
     11 
     12     // top, left, bottom, right - init to first point in list
     13 
     14     o_limit[0] = o[1];
     15     o_limit[1] = o[0];
     16     o_limit[2] = o[1];
     17     o_limit[3] = o[0];
     18 
     19 
     20     for (int i=0; i<sizeof(o); i+=2) {
     21         if (o[i] < o_limit[1])
     22             o_limit[1] = o[i];
     23         else if (o[i] > o_limit[3])
     24             o_limit[3] = o[i];
     25         if (o[i+1] < o_limit[0])
     26             o_limit[0] = o[i+1];
     27         else if (o[i+1] > o_limit[2])
     28             o_limit[2] = o[i+1];
     29     }
     30 
     31     return o_limit;
     32 }
     33 
     34 // note that after passing the array to a function it's reduced to a pointer, debugger won't print the list
     35 // http://stackoverflow.com/questions/27212183/gdb-print-array-after-passing-to-function-only-prints-first-value-but-array-sti/27212252#27212252
     36 
     37 // checks are done from o1 perspective
     38 bool check_collision(float * o1, int o1_size, float * o2, int o2_size) {
     39 
     40     int collision_line = -1; // -1 = none, 0 = top, 1 = topleft, 2 = left [...] 7 = topright
     41 
     42     // arrays cannot be returned, so they must be passed by reference
     43     // https://www.physicsforums.com/threads/inputting-an-array-in-to-a-function-or-returning-an-array-c.285625/
     44     // we want to modify the elements ... http://stackoverflow.com/questions/10007986/c-pass-an-array-by-reference
     45     float o1_limit[4];
     46     get_limits(o1_limit, o1);
     47 
     48     float o2_limit[4];
     49     get_limits(o2_limit, o2);
     50 
     51     // first the crude check, to save processor if it can be ruled out this simply
     52 
     53     /*
     54     // challenge: extra checks for either side needs to be added here to determine which direction
     55 
     56     if (o1_limit[0] <= o2_limit[2] && o1_limit[1] <= o2_limit[3])
     57         // o1 perspective this means collsion UPWARDS
     58         collision_direction = 0;
     59     else if (o1_limit[2] >= o2_limit[0] && o1_limit[1] <= o2_limit[3])
     60         collision_direction = 1;
     61     else if (o1_limit[2] <= o2_limit[0] && o1_limit[3] >= o2_limit[1])
     62         collision_direction = 2;
     63     else if (o1_limit[0] <= o2_limit[2] && o1_limit[3] >= o2_limit[1])
     64         collision_direction = 3;
     65     */
     66 
     67     //  detect WHETHER the limit values intersect
     68     /*if ((o1_limit[0] <= o2_limit[2] && o1_limit[1] <= o2_limit[3]) ||
     69         (o1_limit[2] >= o2_limit[0] && o1_limit[1] <= o2_limit[3]) ||
     70         (o1_limit[2] <= o2_limit[0] && o1_limit[3] >= o2_limit[1]) ||
     71         (o1_limit[0] >= o2_limit[2] && o1_limit[3] >= o2_limit[1]))
     72             collision_line = 0;*/
     73 
     74 
     75     // thanks to this site for logic
     76     // http://leetcode.com/2011/05/determine-if-two-rectangles-overlap.html
     77 
     78     if (!(o1_limit[0] > o2_limit[2] || o1_limit[1] > o2_limit[3] || o1_limit[2] < o2_limit[0] || o1_limit[3] < o2_limit[1]))
     79         collision_line = 0;
     80 
     81     if (collision_line < 0)
     82         return false;
     83 
     84     // fine grained inspection
     85 
     86     // for every o1 line, check if intersect of every o2 line is within bounds of o1 line
     87 
     88     // first find slope of each main line ((o1[i+3] - o1[i+1]) / (o1[i+2] / o1[i]))
     89 
     90     for (int i=0; i < (o1_size / sizeof(float)) - 1; i += 2) {
     91 
     92         float o1_x1, o1_x2, o1_y1, o1_y2;
     93         if (i == 0) {
     94             o1_x1 = o1[(o1_size / sizeof(float)) - 2];
     95             o1_y1 = o1[(o1_size / sizeof(float)) - 1];
     96             o1_x2 = o1[i];
     97             o1_y2 = o1[i+1];
     98         } else {
     99             o1_x1 = o1[i-2];
    100             o1_y1 = o1[i-1];
    101             o1_x2 = o1[i];
    102             o1_y2 = o1[i+1];
    103         }
    104 
    105         float o1_slope = (o1_y2 - o1_y1) / (o1_x2 - o1_x1);
    106 
    107         for(int j = 0; j < (o2_size / sizeof(float)) - 1; j += 2) {
    108 
    109             float o2_x1, o2_x2, o2_y1, o2_y2;
    110             if (j == 0) {
    111                 o2_x1 = o2[(o2_size / sizeof(float)) - 2];
    112                 o2_y1 = o2[(o2_size / sizeof(float)) - 1];
    113                 o2_x2 = o2[j];
    114                 o2_y2 = o2[j+1];
    115             } else {
    116                 o2_x1 = o2[j-2];
    117                 o2_y1 = o2[j-1];
    118                 o2_x2 = o2[j];
    119                 o2_y2 = o2[j+1];
    120             }
    121 
    122             float o2_slope = (o2_y2 - o2_y1) / (o2_x2 - o2_x1);
    123 
    124     // getting the o2 line slope, insert first inspection for PARALLELL lines! If lines are parallell, we need to check the endpoints to see if any part overlaps. if it does then we have collision.
    125     // if it doesnt overlap it can still be within each other, but then one of the other lines in the shape will catch it!
    126     // if it does then return here already
    127 
    128     // Hours and hours to try to figure out how to break the two xy equations into code,
    129     // and then I find this totally different and super-simple solution by eliminating the Y totally from the picture.
    130     // http://www.softwareandfinance.com/Visual_CPP/VCPP_Intersection_Two_lines_EndPoints.html
    131 
    132     // first the intercepts (where the lines cross the Y-axis)
    133 
    134             float intercept_o1 = o1_y1 - (o1_slope * o1_x1);
    135             float intercept_o2 = o2_y1 - (o2_slope * o2_x1);
    136             float intersect_x;
    137             float intersect_y;
    138 
    139             if (o1_slope == o2_slope) {
    140                 if ((o1_x1 > o2_x1 && o1_x2 > o2_x1 && o1_x1 > o2_x2 && o1_x2 > o2_x2) ||
    141                     (o1_x1 < o2_x1 && o1_x2 < o2_x1 && o1_x1 < o2_x2 && o1_x2 < o2_x2) ||
    142                     intercept_o1 != intercept_o2) {
    143                     continue;
    144                 } else {
    145                     return true;
    146                 }
    147             }
    148 
    149     // Formula for finding the intersections
    150 
    151             if (isinf(o1_slope)) {
    152                 intersect_x = o1_x1;
    153                 intersect_y = (o2_slope * intersect_x) + intercept_o2;
    154             } else if (isinf(o2_slope)) {
    155                 intersect_x = o2_x1;
    156                 intersect_y = (o1_slope * intersect_x) + intercept_o1;
    157             } else {
    158                 intersect_x = (intercept_o2 - intercept_o1) / (o1_slope - o2_slope);
    159                 intersect_y = (o1_slope * intersect_x) + intercept_o1;
    160             }
    161     //
    162     //
    163     //
    164     // Check against o1 whether the point intersects
    165     //
    166     // int y2, y1, x2, x1
    167     // y2 = o1_y2 and y1 = o1_y1 if o1_y2 > o1_y1. If not then the other way around!
    168             float y2, y1, x2, x1;
    169 
    170             if (o1_y2 > o1_y1) {
    171                 y2 = o1_y2;
    172                 y1 = o1_y1;
    173             } else {
    174                 y2 = o1_y1;
    175                 y1 = o1_y2;
    176             }
    177 
    178             if (o1_x2 > o1_x1) {
    179                 x2 = o1_x2;
    180                 x1 = o1_x1;
    181             } else {
    182                 x2 = o1_x1;
    183                 x1 = o1_x2;
    184             }
    185 
    186             if (y2 >= intersect_y && y1 <= intersect_y && x2 >= intersect_x && x1 <= intersect_x) {
    187                 if (o2_y2 > o2_y1) {
    188                     y2 = o2_y2;
    189                     y1 = o2_y1;
    190                 } else {
    191                     y2 = o2_y1;
    192                     y1 = o2_y2;
    193                 }
    194 
    195                 if (o2_x2 > o2_x1) {
    196                     x2 = o2_x2;
    197                     x1 = o2_x1;
    198                 } else {
    199                     x2 = o2_x1;
    200                     x1 = o2_x2;
    201                 }
    202 
    203                 if (y2 >= intersect_y && y1 <= intersect_y && x2 >= intersect_x && x1 <= intersect_x) {
    204                     //collision_line = i;
    205                     return true;
    206                 }
    207             }
    208 
    209     // same for x2, x1...
    210     //
    211     // if y <= y2 && y >= y1 && x <= x2 && x <= x1 THEN we have collision.
    212 
    213 
    214         }
    215     }
    216 
    217     return false;
    218 }
    219 
    220 #endif // COLLISION_H_INCLUDED