src/collision.c

   1 /************************************************************************
   2 * collision.c
   3 * voxelands - 3d voxel world sandbox game
   4 * Copyright (C) Lisa 'darkrose' Milne 2016 <lisa@ltmnet.com>
   5 *
   6 * This program is free software: you can redistribute it and/or modify
   7 * it under the terms of the GNU General Public License as published by
   8 * the Free Software Foundation, either version 3 of the License, or
   9 * (at your option) any later version.
  10 *
  11 * This program is distributed in the hope that it will be useful, but
  12 * WITHOUT ANY WARRANTY; without even the implied warranty of
  13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  14 * See the GNU General Public License for more details.
  15 *
  16 * You should have received a copy of the GNU General Public License
  17 * along with this program.  If not, see <http://www.gnu.org/licenses/>
  18 ************************************************************************/
  19
  20 #include "common.h"
  21 #include "collision.h"
  22
  23 #include "array.h"
  24 #include "list.h"
  25
  26 #include <stdlib.h>
  27 #include <math.h>
  28
  29 static void collision_initinfo(collisioninfo_t *i)
  30 {
  31         i->type = COLLISION_NODE;
  32         i->pos.x = -32768;
  33         i->pos.y = -32768;
  34         i->pos.z = -32768;
  35         i->speed = 0.0;
  36         i->speed_o.x = 0.0;
  37         i->speed_o.y = 0.0;
  38         i->speed_o.z = 0.0;
  39         i->speed_n.x = 0.0;
  40         i->speed_n.y = 0.0;
  41         i->speed_n.z = 0.0;
  42 }
  43
  44
  45 /* checks if movingbox collides with staticbox
  46  * -1 no collision, 0 x collision, 1 y collision, 2 z collision
  47  * time of collision stored in dtime */
  48 static int collision_aa(aabox_t *staticbox, aabox_t *movingbox, v3_t *speed, float d, float *dtime)
  49 {
  50         aabox_t relbox;
  51         float xsize;
  52         float ysize;
  53         float zsize;
  54         float dt;
  55         v3_t dspeed;
  56
  57         xsize = (staticbox->max.x - staticbox->min.x);
  58         ysize = (staticbox->max.y - staticbox->min.y);
  59         zsize = (staticbox->max.z - staticbox->min.z);
  60
  61         relbox.min.x = (movingbox->min.x - staticbox->min.x);
  62         relbox.min.y = (movingbox->min.y - staticbox->min.y);
  63         relbox.min.z = (movingbox->min.z - staticbox->min.z);
  64         relbox.max.x = (movingbox->max.x - staticbox->min.x);
  65         relbox.max.y = (movingbox->max.y - staticbox->min.y);
  66         relbox.max.z = (movingbox->max.z - staticbox->min.z);
  67
  68         /* check against x- */
  69         if (speed->x > 0.0) {
  70                 if (relbox.max.x <= d) {
  71                         dt = -relbox.max.x/speed->x;
  72                         *dtime = dt;
  73                         dspeed.x = speed->x*dt;
  74                         dspeed.y = speed->y*dt;
  75                         dspeed.z = speed->z*dt;
  76                         if (
  77                                 ((relbox.min.y+dspeed.y) < ysize)
  78                                 && ((relbox.max.y+dspeed.y) > 0.0)
  79                                 && ((relbox.min.z+dspeed.z) < zsize)
  80                                 && ((relbox.max.z+dspeed.z) > 0.0)
  81                         )
  82                                 return 0;
  83                 }else if (relbox.min.x > xsize) {
  84                         return -1;
  85                 }
  86         /* check against x+ */
  87         }else if (speed->x < 0.0) {
  88                 if (relbox.min.x >= (xsize-d)) {
  89                         dt = (xsize-relbox.min.x)/speed->x;
  90                         *dtime = dt;
  91                         dspeed.x = speed->x*dt;
  92                         dspeed.y = speed->y*dt;
  93                         dspeed.z = speed->z*dt;
  94                         if (
  95                                 ((relbox.min.y+dspeed.y) < ysize)
  96                                 && ((relbox.max.y+dspeed.y) > 0.0)
  97                                 && ((relbox.min.z+dspeed.z) < zsize)
  98                                 && ((relbox.max.z+dspeed.z) > 0.0)
  99                         )
 100                                 return 0;
 101                 }else if (relbox.max.x < 0.0) {
 102                         return -1;
 103                 }
 104         }
 105
 106         /* check against y- */
 107         if (speed->y > 0.0) {
 108                 if (relbox.max.y <= d) {
 109                         dt = -relbox.max.y/speed->y;
 110                         *dtime = dt;
 111                         dspeed.x = speed->x*dt;
 112                         dspeed.y = speed->y*dt;
 113                         dspeed.z = speed->z*dt;
 114                         if (
 115                                 ((relbox.min.x+dspeed.x) < xsize)
 116                                 && ((relbox.max.x+dspeed.x) > 0.0)
 117                                 && ((relbox.min.z+dspeed.z) < zsize)
 118                                 && ((relbox.max.z+dspeed.z) > 0.0)
 119                         )
 120                                 return 1;
 121                 }else if (relbox.min.y > ysize) {
 122                         return -1;
 123                 }
 124         /* check against y+ */
 125         }else if (speed->y < 0.0) {
 126                 if (relbox.min.y >= (ysize-d)) {
 127                         dt = (ysize-relbox.min.y)/speed->y;
 128                         *dtime = dt;
 129                         dspeed.x = speed->x*dt;
 130                         dspeed.y = speed->y*dt;
 131                         dspeed.z = speed->z*dt;
 132                         if (
 133                                 ((relbox.min.x+dspeed.x) < xsize)
 134                                 && ((relbox.max.x+dspeed.x) > 0.0)
 135                                 && ((relbox.min.z+dspeed.z) < zsize)
 136                                 && ((relbox.max.z+dspeed.z) > 0.0)
 137                         )
 138                                 return 1;
 139                 }else if (relbox.max.y < 0) {
 140                         return -1;
 141                 }
 142         }
 143
 144         /* check against z- */
 145         if (speed->z > 0.0) {
 146                 if(relbox.max.z <= d) {
 147                         dt = -relbox.max.z/speed->z;
 148                         *dtime = dt;
 149                         dspeed.x = speed->x*dt;
 150                         dspeed.y = speed->y*dt;
 151                         dspeed.z = speed->z*dt;
 152                         if (
 153                                 ((relbox.min.x+dspeed.x) < xsize)
 154                                 && ((relbox.max.x+dspeed.x) > 0.0)
 155                                 && ((relbox.min.y+dspeed.y) < ysize)
 156                                 && ((relbox.max.y+dspeed.y) > 0)
 157                         )
 158                                 return 2;
 159                 }
 160         /* check against z+ */
 161         }else if (speed->z < 0.0) {
 162                 if (relbox.min.z >= (zsize-d)) {
 163                         dt = (zsize-relbox.min.z)/speed->z;
 164                         *dtime = dt;
 165                         dspeed.x = speed->x*dt;
 166                         dspeed.y = speed->y*dt;
 167                         dspeed.z = speed->z*dt;
 168                         if (
 169                                 ((relbox.min.x+dspeed.x) < xsize)
 170                                 && ((relbox.max.x+dspeed.x) > 0.0)
 171                                 && ((relbox.min.y+dspeed.y) < ysize)
 172                                 && ((relbox.max.y+dspeed.y) > 0.0)
 173                         )
 174                                 return 2;
 175                 }
 176         }
 177
 178         return -1;
 179 }
 180
 181 /* checks if movingbox+y_increase would hit a ceiling */
 182 static int collision_ceiling(array_t *staticboxes, aabox_t *movingbox, float y_increase, float d)
 183 {
 184         int i;
 185         aabox_t *s;
 186
 187         if (y_increase < 0)
 188                 return 0;
 189
 190         for (i=0; i<staticboxes->length; i++) {
 191                 s = &((collisionblock_t**)staticboxes->data)[i]->box;
 192                 if (!s)
 193                         return 0;
 194                 if (
 195                         ((movingbox->max.y-d) <= s->min.y)
 196                         && ((movingbox->max.y+y_increase) > s->min.y)
 197                         && (movingbox->min.x < s->max.x)
 198                         && (movingbox->max.x > s->min.x)
 199                         && (movingbox->min.z < s->max.z)
 200                         && (movingbox->max.z > s->min.z)
 201                 )
 202                         return 1;
 203         }
 204
 205         return 0;
 206 }
 207
 208 /* gets any block that could be collided with */
 209 static int collision_get_nearby(array_t *hits, v3_t *pos, v3_t *speed, float dtime)
 210 {
 211         /* TODO: this, once content*.c/h is done */
 212         return 0;
 213 }
 214
 215 /* move pos by (speed+(accel*dtime))*dtime, checking for collisions */
 216 /* TODO: this will need something changed for the client, so it doesn't use the server map */
 217 collisionresult_t *collision_move(float pos_max_d, aabox_t *box, float stepheight, float dtime, v3_t *pos, v3_t *speed, v3_t accel)
 218 {
 219         collisionresult_t *result;
 220         collisionblock_t *cb;
 221         collisioninfo_t *info = NULL;
 222         array_t hits;
 223         aabox_t mbox;
 224         aabox_t sbox;
 225         int i;
 226         int k;
 227         float d = pos_max_d * 1.1;
 228
 229         if (d <= pos_max_d)
 230                 return NULL;
 231
 232         result = malloc(sizeof(collisionresult_t));
 233         if (!result)
 234                 return NULL;
 235
 236         result->touching_ground = 0;
 237         result->in_liquid = 0;
 238         result->touching_lethal = 0;
 239         result->collides = 0;
 240         result->collides_xz = 0;
 241         result->standing_on_unloaded = 0;
 242         result->collisions = NULL;
 243
 244         if (dtime > 0.5)
 245                 dtime = 0.5;
 246
 247         speed->x += (accel.x*dtime);
 248         speed->y += (accel.y*dtime);
 249         speed->z += (accel.z*dtime);
 250
 251         /* no movement == no collision */
 252         if (speed->x == 0.0 && speed->y == 0.0 && speed->z == 0.0)
 253                 return result;
 254
 255         if (speed->x > 5000.0) {
 256                 speed->x = 5000.0;
 257         }else if (speed->x < -5000.0) {
 258                 speed->x = -5000.0;
 259         }
 260         if (speed->y > 5000.0) {
 261                 speed->y = 5000.0;
 262         }else if (speed->y < -5000.0) {
 263                 speed->y = -5000.0;
 264         }
 265         if (speed->z > 5000.0) {
 266                 speed->z = 5000.0;
 267         }else if (speed->z < -5000.0) {
 268                 speed->z = -5000.0;
 269         }
 270
 271         array_init(&hits, ARRAY_TYPE_PTR);
 272
 273         if (!collision_get_nearby(&hits,pos,speed,dtime)) {
 274                 array_free(&hits,0);
 275                 return result;
 276         }
 277
 278         for (i=0; i<100 && dtime>1e-10; ++i) {
 279                 int nearest_collided = -1;
 280                 float nearest_dtime = dtime;
 281                 int nearest_boxindex = -1;
 282
 283                 mbox.min.x = box->min.x+pos->x;
 284                 mbox.min.y = box->min.y+pos->y;
 285                 mbox.min.z = box->min.z+pos->z;
 286                 mbox.max.x = box->max.x+pos->x;
 287                 mbox.max.y = box->max.y+pos->y;
 288                 mbox.max.z = box->max.z+pos->z;
 289
 290                 for (k=0; k<hits.length; k++) {
 291                         float dtime_tmp;
 292                         int collided;
 293                         cb = ((collisionblock_t**)hits.data)[k];
 294                         if (cb->is_stepup)
 295                                 continue;
 296
 297                         collided = collision_aa(
 298                                 &cb->box,
 299                                 &mbox,
 300                                 speed,
 301                                 d,
 302                                 &dtime_tmp
 303                         );
 304
 305                         if (collided == -1 || dtime_tmp >= nearest_dtime)
 306                                 continue;
 307
 308                         nearest_dtime = dtime_tmp;
 309                         nearest_collided = collided;
 310                         nearest_boxindex = k;
 311                 }
 312
 313                 /* no collision */
 314                 if (nearest_collided == -1) {
 315                         pos->x += speed->x*dtime;
 316                         pos->y += speed->y*dtime;
 317                         pos->z += speed->z*dtime;
 318                         dtime = 0;
 319                         break;
 320                 /* collision occurred */
 321                 }else{
 322                         cb = ((collisionblock_t**)hits.data)[nearest_boxindex];
 323
 324                         /* steps are not counted as a collision */
 325                         if (
 326                                 (nearest_collided != 1)
 327                                 && (mbox.min.y < cb->box.max.y)
 328                                 && ((mbox.min.y+stepheight) > cb->box.max.y)
 329                                 && (!collision_ceiling(&hits, &mbox, cb->box.max.y-mbox.min.y, d))
 330                         ) {
 331                                 cb->is_stepup = 1;
 332                                 continue;
 333                         }else if (nearest_dtime >= 0.0) {
 334                                 pos->x += speed->x*nearest_dtime;
 335                                 pos->y += speed->y*nearest_dtime;
 336                                 pos->z += speed->z*nearest_dtime;
 337                                 dtime -= nearest_dtime;
 338                         }else{
 339                                 if (nearest_collided == 0)
 340                                         pos->x += speed->x*nearest_dtime;
 341                                 if (nearest_collided == 1)
 342                                         pos->y += speed->y*nearest_dtime;
 343                                 if (nearest_collided == 2)
 344                                         pos->z += speed->z*nearest_dtime;
 345                         }
 346
 347                         if (cb->is_unloaded)
 348                                 continue;
 349
 350                         if (!info)
 351                                 info = malloc(sizeof(collisioninfo_t));
 352
 353                         if (!info)
 354                                 break;
 355
 356                         collision_initinfo(info);
 357
 358                         info->pos = cb->pos;
 359                         info->speed_o = *speed;
 360
 361                         switch (nearest_collided) {
 362                         case 0:
 363                                 speed->x = 0;
 364                                 result->collides = 1;
 365                                 result->collides_xz = 1;
 366                                 break;
 367                         case 1:
 368                                 speed->y = 0;
 369                                 result->collides = 1;
 370                                 break;
 371                         case 2:
 372                                 speed->z = 0;
 373                                 result->collides = 1;
 374                                 result->collides_xz = 1;
 375                                 break;
 376                         default:;
 377                         }
 378
 379                         info->speed_n = *speed;
 380                         if (math_distance(&info->speed_n,&info->speed_o) >= 0.1) {
 381                                 result->collisions = list_push(&result->collisions,info);
 382                                 info = NULL;
 383                         }
 384                 }
 385         }
 386
 387         if (info)
 388                 free(info);
 389
 390         sbox.min.x = box->min.x+pos->x;
 391         sbox.min.y = box->min.y+pos->y;
 392         sbox.min.z = box->min.z+pos->z;
 393         sbox.max.x = box->max.x+pos->x;
 394         sbox.max.y = box->max.y+pos->y;
 395         sbox.max.z = box->max.z+pos->z;
 396         for (i=0; i<hits.length; i++) {
 397                 cb = ((collisionblock_t**)hits.data)[i];
 398
 399                 /*
 400                         See if the object is touching ground.
 401
 402                         Object touches ground if object's minimum Y is near node's
 403                         maximum Y and object's X-Z-area overlaps with the node's
 404                         X-Z-area.
 405
 406                         Use 0.15*BS so that it is easier to get on a node.
 407                 */
 408                 if (
 409                         (cb->box.max.x-d) > sbox.min.x
 410                         && (cb->box.min.x+d) < sbox.max.x
 411                         && (cb->box.max.z-d) > sbox.min.z
 412                         && (cb->box.min.z+d) < sbox.max.z
 413                 ) {
 414                         if (cb->is_stepup) {
 415                                 float diff = (cb->box.max.y-sbox.min.y);
 416                                 pos->y += diff;
 417                                 sbox.min.y += diff;
 418                                 sbox.max.y += diff;
 419                         }
 420                         if (fabs(cb->box.max.y-sbox.min.y) < 0.15) {
 421                                 result->touching_ground = 1;
 422                                 if (cb->is_unloaded)
 423                                         result->standing_on_unloaded = 1;
 424                         }
 425                 }
 426         }
 427
 428         array_free(&hits,0);
 429
 430         return result;
 431 }
 432
 433 /* free a collisionresult_t */
 434 void collision_free(collisionresult_t *r)
 435 {
 436         collisioninfo_t *i;
 437         if (!r)
 438                 return;
 439
 440         while ((i = list_pop(&r->collisions))) {
 441                 free(i);
 442         }
 443
 444         free(r);
 445 }