src/collision.c

   1 /*
   2  * See Licensing and Copyright notice in naev.h
   3  */
   4
   5 /**
   6  * @file collision.c
   7  *
   8  * @brief Deals with 2d collisions.
   9  */
  10
  11
  12 #include "collision.h"
  13
  14 #include "naev.h"
  15
  16 #include "log.h"
  17
  18
  19 /**
  20  * @brief Checks whether or not two sprites collide.
  21  *
  22  * This function does pixel perfect checks.  If the collision actually occurs,
  23  *  crash is set to store the real position of the collision.
  24  *
  25  *    @param[in] at Texture a.
  26  *    @param[in] asx Position of x of sprite a.
  27  *    @param[in] asy Position of y of sprita a.
  28  *    @param[in] ap Position in space of sprite a.
  29  *    @param[in] bt Texture b.
  30  *    @param[in] bsx Position of x of sprite b.
  31  *    @param[in] bsy Position of y of sprite b.
  32  *    @param[in] bp Position in space of sprite b.
  33  *    @param[out] crash Actual position of the collision (only set on collision).
  34  *    @return 1 on collision, 0 else.
  35  */
  36 int CollideSprite( const glTexture* at, const int asx, const int asy, const Vector2d* ap,
  37       const glTexture* bt, const int bsx, const int bsy, const Vector2d* bp,
  38       Vector2d* crash )
  39 {
  40    int x,y;
  41    int ax1,ax2, ay1,ay2;
  42    int bx1,bx2, by1,by2;
  43    int inter_x0, inter_x1, inter_y0, inter_y1;
  44    int rasy, rbsy;
  45    int abx,aby, bbx, bby;
  46
  47    /* Make sure the surfaces have transparency maps. */
  48    if (at->trans == NULL) {
  49       WARN("Texture '%s' has no transparency map.", at->name);
  50       return 0;
  51    }
  52    if (bt->trans == NULL) {
  53       WARN("Texture '%s' has no transparency map.", bt->name);
  54       return 0;
  55    }
  56
  57    /* a - cube coordinates */
  58    ax1 = (int)VX(*ap) - (int)(at->sw)/2;
  59    ay1 = (int)VY(*ap) - (int)(at->sh)/2;
  60    ax2 = ax1 + (int)(at->sw) - 1;
  61    ay2 = ay1 + (int)(at->sh) - 1;
  62
  63    /* b - cube coordinates */
  64    bx1 = (int)VX(*bp) - (int)(bt->sw)/2;
  65    by1 = (int)VY(*bp) - (int)(bt->sh)/2;
  66    bx2 = bx1 + bt->sw - 1;
  67    by2 = by1 + bt->sh - 1;
  68
  69    /* check if bounding boxes intersect */
  70    if((bx2 < ax1) || (ax2 < bx1)) return 0;
  71    if((by2 < ay1) || (ay2 < by1)) return 0;
  72
  73    /* define the remaining binding box */
  74    inter_x0 = MAX( ax1, bx1 );
  75    inter_x1 = MIN( ax2, bx2 );
  76    inter_y0 = MAX( ay1, by1 );
  77    inter_y1 = MIN( ay2, by2 );
  78
  79    /* real vertical sprite value (flipped) */
  80    rasy = at->sy - asy - 1;
  81    rbsy = bt->sy - bsy - 1;
  82
  83    /* set up the base points */
  84    abx =  asx*(int)(at->sw) - ax1;
  85    aby = rasy*(int)(at->sh) - ay1;
  86    bbx =  bsx*(int)(bt->sw) - bx1;
  87    bby = rbsy*(int)(bt->sh) - by1;
  88
  89    for (y=inter_y0; y<=inter_y1; y++)
  90       for (x=inter_x0; x<=inter_x1; x++)
  91          /* compute offsets for surface before pass to TransparentPixel test */
  92          if ((!gl_isTrans(at, abx + x, aby + y)) &&
  93                (!gl_isTrans(bt, bbx + x, bby + y))) {
  94
  95             /* Set the crash position. */
  96             crash->x = x;
  97             crash->y = y;
  98             return 1;
  99          }
 100
 101    return 0;
 102 }
 103
 104
 105 /**
 106  * @brief Checks to see if two lines collide.
 107  *
 108  *    @param[in] s1x X start point of line 1.
 109  *    @param[in] s1y Y start point of line 1.
 110  *    @param[in] e1x X end point of line 1.
 111  *    @param[in] e1y Y end point of line 1.
 112  *    @param[in] s2x X start point of line 2.
 113  *    @param[in] s2y Y start point of line 2.
 114  *    @param[in] e2x X end point of line 2.
 115  *    @param[in] e2y Y end point of line 2.
 116  *    @param[out] crash Position of the collision.
 117  *    @return 3 if lines are coincident, 2 if lines are parallel,
 118  *              1 if lines just collide on a point, or 0 if they don't.
 119  */
 120 int CollideLineLine( double s1x, double s1y, double e1x, double e1y,
 121       double s2x, double s2y, double e2x, double e2y, Vector2d* crash )
 122 {
 123    double ua_t, ub_t, u_b;
 124    double ua, ub;
 125
 126    ua_t = (e2x - s2x) * (s1y - s2y) - (e2y - s2y) * (s1x - s2x);
 127    ub_t = (e1x - s1x) * (s1y - s2y) - (e1y - s1y) * (s1x - s2x);
 128    u_b  = (e2y - s2y) * (e1x - s1x) - (e2x - s2x) * (e1y - s1y);
 129
 130    if (u_b != 0.) {
 131       ua = ua_t / u_b;
 132       ub = ub_t / u_b;
 133
 134       /* Intersection at a point. */
 135       if ((0. <= ua) && (ua <= 1.) && (0. <= ub) && (ub <= 1.)) {
 136          crash->x = s1x + ua * (e1x - s1x);
 137          crash->y = s1y + ua * (e1y - s1y);
 138          return 1;
 139       }
 140       /* No intersection. */
 141       else
 142          return 0;
 143    }
 144    else {
 145       /* Coincident. */
 146       if ((ua_t == 0.) || (ub_t == 0.))
 147          return 3;
 148       /* Parallel. */
 149       else
 150          return 2;
 151    }
 152 }
 153
 154
 155 /**
 156  * @brief Checks to see if a line collides with a sprite.
 157  *
 158  * First collisions are detected on all the walls of the sprite's rectangle.
 159  *  Then the collisions are tested by pixel perfectness until collisions are
 160  *  actually found with the ship itself.
 161  *
 162  *    @param[in] ap Origin of the line.
 163  *    @param[in] ad Direction of the line.
 164  *    @param[in] al Length of the line.
 165  *    @param[in] bt Texture b.
 166  *    @param[in] bsx Position of x of sprite b.
 167  *    @param[in] bsy Position of y of sprite b.
 168  *    @param[in] bp Position in space of sprite b.
 169  *    @param[out] crash Position of the collision.
 170  *    @return 1 on collision, 0 else.
 171  *
 172  * @sa CollideSprite
 173  */
 174 int CollideLineSprite( const Vector2d* ap, double ad, double al,
 175       const glTexture* bt, const int bsx, const int bsy, const Vector2d* bp,
 176       Vector2d crash[2] )
 177 {
 178    int x,y, rbsy, bbx,bby;
 179    double ep[2], bl[2], tr[2], v[2], mod;
 180    int hits, real_hits;
 181    Vector2d tmp_crash, border[2];
 182
 183    /* Make sure texture has transparency map. */
 184    if (bt->trans == NULL) {
 185       WARN("Texture '%s' has no transparency map.", bt->name);
 186       return 0;
 187    }
 188
 189    /* Set up end point of line. */
 190    ep[0] = ap->x + al*cos(ad);
 191    ep[1] = ap->y + al*sin(ad);
 192
 193    /* Set up top right corner of the rectangle. */
 194    tr[0] = bp->x + bt->sw/2.;
 195    tr[1] = bp->y + bt->sh/2.;
 196    /* Set up bottom left corner of the rectangle. */
 197    bl[0] = bp->x - bt->sw/2.;
 198    bl[1] = bp->y - bt->sh/2.;
 199
 200    /*
 201     * Start check for rectangular collisions.
 202     */
 203    hits = 0;
 204    /* Left border. */
 205    if (CollideLineLine(ap->x, ap->y, ep[0], ep[1],
 206          bl[0], bl[1], bl[0], tr[1], &tmp_crash) == 1) {
 207       border[hits].x = tmp_crash.x;
 208       border[hits].y = tmp_crash.y;
 209       hits++;
 210    }
 211    /* Top border. */
 212    if (CollideLineLine(ap->x, ap->y, ep[0], ep[1],
 213          bl[0], tr[1], tr[0], tr[1], &tmp_crash) == 1) {
 214       border[hits].x = tmp_crash.x;
 215       border[hits].y = tmp_crash.y;
 216       hits++;
 217    }
 218    /* Now we have to make sure hits isn't 2. */
 219    /* Right border. */
 220    if ((hits < 2) && CollideLineLine(ap->x, ap->y, ep[0], ep[1],
 221          tr[0], tr[1], tr[0], bl[1], &tmp_crash) == 1) {
 222       border[hits].x = tmp_crash.x;
 223       border[hits].y = tmp_crash.y;
 224       hits++;
 225    }
 226    /* Bottom border. */
 227    if ((hits < 2) && CollideLineLine(ap->x, ap->y, ep[0], ep[1],
 228          tr[0], bl[1], bl[0], bl[1], &tmp_crash) == 1) {
 229       border[hits].x = tmp_crash.x;
 230       border[hits].y = tmp_crash.y;
 231       hits++;
 232    }
 233
 234    /* No hits - missed. */
 235    if (hits == 0)
 236       return 0;
 237
 238    /* Beam must die in the rectangle. */
 239    if (hits == 1) {
 240       border[1].x = ep[0];
 241       border[1].y = ep[1];
 242    }
 243
 244    /*
 245     * Now we do a pixel perfect approach.
 246     */
 247    real_hits = 0;
 248    /* Directonaly vector (normalized). */
 249    v[0] = border[1].x - border[0].x;
 250    v[1] = border[1].y - border[0].y;
 251    /* Normalize. */
 252    mod = MOD(v[0],v[1])/2.; /* Multiply by two to reduce check amount. */
 253    v[0] /= mod;
 254    v[1] /= mod;
 255
 256    /* real vertical sprite value (flipped) */
 257    rbsy = bt->sy - bsy - 1;
 258    /* set up the base points */
 259    bbx =  bsx*(int)(bt->sw);
 260    bby = rbsy*(int)(bt->sh);
 261
 262    /* We start checking first border until we find collision. */
 263    x = border[0].x - bl[0] + v[0];
 264    y = border[0].y - bl[1] + v[1];
 265    while ((x > 0.) && (x < bt->sw) && (y > 0.) && (y < bt->sh)) {
 266       /* Is non-transparent. */
 267       if (!gl_isTrans(bt, bbx+(int)x, bby+(int)y)) {
 268          crash[real_hits].x = x + bl[0];
 269          crash[real_hits].y = y + bl[1];
 270          real_hits++;
 271          break;
 272       }
 273       x += v[0];
 274       y += v[1];
 275    }
 276
 277    /* Now we check the second border. */
 278    x = border[1].x - bl[0] - v[0];
 279    y = border[1].y - bl[1] - v[1];
 280    while ((x > 0.) && (x < bt->sw) && (y > 0.) && (y < bt->sh)) {
 281       /* Is non-transparent. */
 282       if (!gl_isTrans(bt, bbx+(int)x, bby+(int)y)) {
 283          crash[real_hits].x = x + bl[0];
 284          crash[real_hits].y = y + bl[1];
 285          real_hits++;
 286          break;
 287       }
 288       x -= v[0];
 289       y -= v[1];
 290    }
 291
 292    /* Actually missed. */
 293    if (real_hits == 0)
 294       return 0;
 295
 296    /* Strange situation, should never happen but just in case we duplicate
 297     *  the hit. */
 298    if (real_hits == 1) {
 299       crash[1].x = crash[0].x;
 300       crash[1].y = crash[0].y;
 301    }
 302
 303    /* We hit. */
 304    return 1;
 305 }
 306
 307