world.c

   1 /*
   2 Copyright (C) 1996-1997 Id Software, Inc.
   3
   4 This program is free software; you can redistribute it and/or
   5 modify it under the terms of the GNU General Public License
   6 as published by the Free Software Foundation; either version 2
   7 of the License, or (at your option) any later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  12
  13 See the GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18
  19 */
  20 // world.c -- world query functions
  21
  22 #include "quakedef.h"
  23
  24 /*
  25
  26 entities never clip against themselves, or their owner
  27
  28 line of sight checks trace->crosscontent, but bullets don't
  29
  30 */
  31
  32
  33 void ClearLink (link_t *l);
  34 void RemoveLink (link_t *l);
  35 void InsertLinkBefore (link_t *l, link_t *before);
  36 void InsertLinkAfter (link_t *l, link_t *after);
  37
  38 #define EDICT_FROM_AREA(l) ((edict_t *)((qbyte *)l - (int)&(((edict_t *)0)->area)))
  39
  40 //============================================================================
  41
  42 // ClearLink is used for new headnodes
  43 void ClearLink (link_t *l)
  44 {
  45         l->prev = l->next = l;
  46 }
  47
  48 void RemoveLink (link_t *l)
  49 {
  50         l->next->prev = l->prev;
  51         l->prev->next = l->next;
  52 }
  53
  54 void InsertLinkBefore (link_t *l, link_t *before)
  55 {
  56         l->next = before;
  57         l->prev = before->prev;
  58         l->prev->next = l;
  59         l->next->prev = l;
  60 }
  61 void InsertLinkAfter (link_t *l, link_t *after)
  62 {
  63         l->next = after->next;
  64         l->prev = after;
  65         l->prev->next = l;
  66         l->next->prev = l;
  67 }
  68
  69
  70 typedef struct
  71 {
  72         // bounding box of entire move area
  73         vec3_t          boxmins, boxmaxs;
  74
  75         // size of the moving object
  76         vec3_t          mins, maxs;
  77
  78         // size when clipping against monsters
  79         vec3_t          mins2, maxs2;
  80
  81         // size when clipping against brush models
  82         vec3_t          hullmins, hullmaxs;
  83
  84         // start and end origin of move
  85         vec3_t          start, end;
  86
  87         // trace results
  88         trace_t         trace;
  89
  90         // type of move (like ignoring monsters, or similar)
  91         int                     type;
  92
  93         // the edict that is moving (if any)
  94         edict_t         *passedict;
  95 }
  96 moveclip_t;
  97
  98
  99 /*
 100 ===============================================================================
 101
 102 ENTITY AREA CHECKING
 103
 104 ===============================================================================
 105 */
 106
 107 typedef struct areanode_s
 108 {
 109         int             axis;           // -1 = leaf node
 110         float   dist;
 111         struct areanode_s       *children[2];
 112         link_t  trigger_edicts;
 113         link_t  solid_edicts;
 114 } areanode_t;
 115
 116 #define AREA_DEPTH      4
 117 #define AREA_NODES      32
 118
 119 static  areanode_t      sv_areanodes[AREA_NODES];
 120 static  int                     sv_numareanodes;
 121
 122 /*
 123 ===============
 124 SV_CreateAreaNode
 125
 126 ===============
 127 */
 128 areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
 129 {
 130         areanode_t      *anode;
 131         vec3_t          size;
 132         vec3_t          mins1, maxs1, mins2, maxs2;
 133
 134         anode = &sv_areanodes[sv_numareanodes];
 135         sv_numareanodes++;
 136
 137         ClearLink (&anode->trigger_edicts);
 138         ClearLink (&anode->solid_edicts);
 139
 140         if (depth == AREA_DEPTH)
 141         {
 142                 anode->axis = -1;
 143                 anode->children[0] = anode->children[1] = NULL;
 144                 return anode;
 145         }
 146
 147         VectorSubtract (maxs, mins, size);
 148         if (size[0] > size[1])
 149                 anode->axis = 0;
 150         else
 151                 anode->axis = 1;
 152
 153         anode->dist = 0.5 * (maxs[anode->axis] + mins[anode->axis]);
 154         VectorCopy (mins, mins1);
 155         VectorCopy (mins, mins2);
 156         VectorCopy (maxs, maxs1);
 157         VectorCopy (maxs, maxs2);
 158
 159         maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
 160
 161         anode->children[0] = SV_CreateAreaNode (depth+1, mins2, maxs2);
 162         anode->children[1] = SV_CreateAreaNode (depth+1, mins1, maxs1);
 163
 164         return anode;
 165 }
 166
 167 /*
 168 ===============
 169 SV_ClearWorld
 170
 171 ===============
 172 */
 173 void SV_ClearWorld (void)
 174 {
 175         Collision_Init ();
 176
 177         memset (sv_areanodes, 0, sizeof(sv_areanodes));
 178         sv_numareanodes = 0;
 179         Mod_CheckLoaded(sv.worldmodel);
 180         SV_CreateAreaNode (0, sv.worldmodel->normalmins, sv.worldmodel->normalmaxs);
 181 }
 182
 183
 184 /*
 185 ===============
 186 SV_UnlinkEdict
 187
 188 ===============
 189 */
 190 void SV_UnlinkEdict (edict_t *ent)
 191 {
 192         if (!ent->area.prev)
 193                 return;         // not linked in anywhere
 194         RemoveLink (&ent->area);
 195         ent->area.prev = ent->area.next = NULL;
 196 }
 197
 198
 199 /*
 200 ====================
 201 SV_TouchLinks
 202 ====================
 203 */
 204 void SV_TouchLinks ( edict_t *ent, areanode_t *node )
 205 {
 206         link_t          *l, *next;
 207         edict_t         *touch;
 208         int                     old_self, old_other;
 209
 210 loc0:
 211 // touch linked edicts
 212         for (l = node->trigger_edicts.next ; l != &node->trigger_edicts ; l = next)
 213         {
 214                 next = l->next;
 215                 touch = EDICT_FROM_AREA(l);
 216                 if (touch == ent)
 217                         continue;
 218                 if (!touch->v.touch || touch->v.solid != SOLID_TRIGGER)
 219                         continue;
 220                 if (ent->v.absmin[0] > touch->v.absmax[0]
 221                  || ent->v.absmin[1] > touch->v.absmax[1]
 222                  || ent->v.absmin[2] > touch->v.absmax[2]
 223                  || ent->v.absmax[0] < touch->v.absmin[0]
 224                  || ent->v.absmax[1] < touch->v.absmin[1]
 225                  || ent->v.absmax[2] < touch->v.absmin[2])
 226                         continue;
 227                 old_self = pr_global_struct->self;
 228                 old_other = pr_global_struct->other;
 229
 230                 pr_global_struct->self = EDICT_TO_PROG(touch);
 231                 pr_global_struct->other = EDICT_TO_PROG(ent);
 232                 pr_global_struct->time = sv.time;
 233                 PR_ExecuteProgram (touch->v.touch, "");
 234
 235                 pr_global_struct->self = old_self;
 236                 pr_global_struct->other = old_other;
 237         }
 238
 239 // recurse down both sides
 240         if (node->axis == -1)
 241                 return;
 242
 243         if (ent->v.absmax[node->axis] > node->dist)
 244         {
 245                 if (ent->v.absmin[node->axis] < node->dist)
 246                         SV_TouchLinks(ent, node->children[1]); // order reversed to reduce code
 247                 node = node->children[0];
 248                 goto loc0;
 249         }
 250         else
 251         {
 252                 if (ent->v.absmin[node->axis] < node->dist)
 253                 {
 254                         node = node->children[1];
 255                         goto loc0;
 256                 }
 257         }
 258 }
 259
 260
 261 /*
 262 ===============
 263 SV_LinkEdict
 264
 265 ===============
 266 */
 267 void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
 268 {
 269         model_t         *model;
 270         areanode_t      *node;
 271
 272         if (ent->area.prev)
 273                 SV_UnlinkEdict (ent);   // unlink from old position
 274
 275         if (ent == sv.edicts)
 276                 return;         // don't add the world
 277
 278         if (ent->free)
 279                 return;
 280
 281 // set the abs box
 282
 283         if (ent->v.solid == SOLID_BSP)
 284         {
 285                 if (ent->v.modelindex < 0 || ent->v.modelindex > MAX_MODELS)
 286                         PR_RunError("SOLID_BSP with invalid modelindex!\n");
 287                 model = sv.models[(int) ent->v.modelindex];
 288                 if (model != NULL)
 289                 {
 290                         if (model->type != mod_brush)
 291                                 PR_RunError("SOLID_BSP with non-BSP model\n");
 292
 293                         if (ent->v.angles[0] || ent->v.angles[2] || ent->v.avelocity[0] || ent->v.avelocity[2])
 294                         {
 295                                 VectorAdd(ent->v.origin, model->rotatedmins, ent->v.absmin);
 296                                 VectorAdd(ent->v.origin, model->rotatedmaxs, ent->v.absmax);
 297                         }
 298                         else if (ent->v.angles[1] || ent->v.avelocity[1])
 299                         {
 300                                 VectorAdd(ent->v.origin, model->yawmins, ent->v.absmin);
 301                                 VectorAdd(ent->v.origin, model->yawmaxs, ent->v.absmax);
 302                         }
 303                         else
 304                         {
 305                                 VectorAdd(ent->v.origin, model->normalmins, ent->v.absmin);
 306                                 VectorAdd(ent->v.origin, model->normalmaxs, ent->v.absmax);
 307                         }
 308                 }
 309                 else
 310                 {
 311                         // SOLID_BSP with no model is valid, mainly because some QC setup code does so temporarily
 312                         VectorAdd (ent->v.origin, ent->v.mins, ent->v.absmin);
 313                         VectorAdd (ent->v.origin, ent->v.maxs, ent->v.absmax);
 314                 }
 315         }
 316         else
 317         {
 318                 VectorAdd (ent->v.origin, ent->v.mins, ent->v.absmin);
 319                 VectorAdd (ent->v.origin, ent->v.maxs, ent->v.absmax);
 320         }
 321
 322 //
 323 // to make items easier to pick up and allow them to be grabbed off
 324 // of shelves, the abs sizes are expanded
 325 //
 326         if ((int)ent->v.flags & FL_ITEM)
 327         {
 328                 ent->v.absmin[0] -= 15;
 329                 ent->v.absmin[1] -= 15;
 330                 ent->v.absmin[2] -= 1;
 331                 ent->v.absmax[0] += 15;
 332                 ent->v.absmax[1] += 15;
 333                 ent->v.absmax[2] += 1;
 334         }
 335         else
 336         {
 337                 // because movement is clipped an epsilon away from an actual edge,
 338                 // we must fully check even when bounding boxes don't quite touch
 339                 ent->v.absmin[0] -= 1;
 340                 ent->v.absmin[1] -= 1;
 341                 ent->v.absmin[2] -= 1;
 342                 ent->v.absmax[0] += 1;
 343                 ent->v.absmax[1] += 1;
 344                 ent->v.absmax[2] += 1;
 345         }
 346
 347         if (ent->v.solid == SOLID_NOT)
 348                 return;
 349
 350 // find the first node that the ent's box crosses
 351         node = sv_areanodes;
 352         while (1)
 353         {
 354                 if (node->axis == -1)
 355                         break;
 356                 if (ent->v.absmin[node->axis] > node->dist)
 357                         node = node->children[0];
 358                 else if (ent->v.absmax[node->axis] < node->dist)
 359                         node = node->children[1];
 360                 else
 361                         break;          // crosses the node
 362         }
 363
 364 // link it in
 365
 366         if (ent->v.solid == SOLID_TRIGGER)
 367                 InsertLinkBefore (&ent->area, &node->trigger_edicts);
 368         else
 369                 InsertLinkBefore (&ent->area, &node->solid_edicts);
 370
 371 // if touch_triggers, touch all entities at this node and descend for more
 372         if (touch_triggers)
 373                 SV_TouchLinks ( ent, sv_areanodes );
 374 }
 375
 376
 377
 378 /*
 379 ===============================================================================
 380
 381 POINT TESTING IN HULLS
 382
 383 ===============================================================================
 384 */
 385
 386 /*
 387 ============
 388 SV_TestEntityPosition
 389
 390 This could be a lot more efficient...
 391 ============
 392 */
 393 int SV_TestEntityPosition (edict_t *ent)
 394 {
 395         return SV_Move (ent->v.origin, ent->v.mins, ent->v.maxs, ent->v.origin, MOVE_NORMAL, ent).startsolid;
 396 }
 397
 398
 399 /*
 400 ===============================================================================
 401
 402 LINE TESTING IN HULLS
 403
 404 ===============================================================================
 405 */
 406
 407 /*
 408 ==================
 409 SV_ClipMoveToEntity
 410
 411 Handles selection or creation of a clipping hull, and offseting (and
 412 eventually rotation) of the end points
 413 ==================
 414 */
 415 trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end)
 416 {
 417         int i;
 418         trace_t trace;
 419         model_t *model;
 420
 421         i = ent->v.modelindex;
 422         if ((unsigned int) i >= MAX_MODELS)
 423                 PR_RunError("SV_ClipMoveToEntity: invalid modelindex\n");
 424         model = sv.models[i];
 425         if (i != 0 && model == NULL)
 426                 PR_RunError("SV_ClipMoveToEntity: invalid modelindex\n");
 427
 428         if ((int) ent->v.solid == SOLID_BSP)
 429         {
 430                 Mod_CheckLoaded(model);
 431                 if (model->type != mod_brush)
 432                 {
 433                         Con_Printf ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model, entity dump:\n");
 434                         ED_Print (ent);
 435                         Host_Error ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model\n");
 436                 }
 437                 if (ent->v.movetype != MOVETYPE_PUSH)
 438                         Host_Error ("SV_ClipMoveToEntity: SOLID_BSP without MOVETYPE_PUSH");
 439         }
 440
 441         Collision_ClipTrace(&trace, ent, model, ent->v.origin, ent->v.angles, ent->v.mins, ent->v.maxs, start, mins, maxs, end);
 442
 443         return trace;
 444 }
 445
 446 //===========================================================================
 447
 448 /*
 449 ====================
 450 SV_ClipToLinks
 451
 452 Mins and maxs enclose the entire area swept by the move
 453 ====================
 454 */
 455 void SV_ClipToLinks ( areanode_t *node, moveclip_t *clip )
 456 {
 457         link_t          *l, *next;
 458         edict_t         *touch;
 459         trace_t         trace;
 460
 461 loc0:
 462         if (clip->trace.allsolid)
 463                 return;
 464 // touch linked edicts
 465         for (l = node->solid_edicts.next ; l != &node->solid_edicts ; l = next)
 466         {
 467                 next = l->next;
 468                 touch = EDICT_FROM_AREA(l);
 469                 if (touch->v.solid == SOLID_NOT)
 470                         continue;
 471                 if (touch == clip->passedict)
 472                         continue;
 473                 if (touch->v.solid == SOLID_TRIGGER)
 474                         Host_Error ("Trigger in clipping list");
 475
 476                 if (clip->type == MOVE_NOMONSTERS && touch->v.solid != SOLID_BSP)
 477                         continue;
 478
 479                 if (clip->boxmins[0] > touch->v.absmax[0]
 480                  || clip->boxmaxs[0] < touch->v.absmin[0]
 481                  || clip->boxmins[1] > touch->v.absmax[1]
 482                  || clip->boxmaxs[1] < touch->v.absmin[1]
 483                  || clip->boxmins[2] > touch->v.absmax[2]
 484                  || clip->boxmaxs[2] < touch->v.absmin[2])
 485                         continue;
 486
 487                 if (clip->passedict)
 488                 {
 489                         if (clip->passedict->v.size[0] && !touch->v.size[0])
 490                                 continue;       // points never interact
 491                         if (PROG_TO_EDICT(touch->v.owner) == clip->passedict)
 492                                 continue;       // don't clip against own missiles
 493                         if (PROG_TO_EDICT(clip->passedict->v.owner) == touch)
 494                                 continue;       // don't clip against owner
 495                         // LordHavoc: corpse code
 496                         if (clip->passedict->v.solid == SOLID_CORPSE && (touch->v.solid == SOLID_SLIDEBOX || touch->v.solid == SOLID_CORPSE))
 497                                 continue;
 498                         if (clip->passedict->v.solid == SOLID_SLIDEBOX && touch->v.solid == SOLID_CORPSE)
 499                                 continue;
 500                 }
 501
 502                 // might interact, so do an exact clip
 503                 if ((int)touch->v.flags & FL_MONSTER)
 504                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins2, clip->maxs2, clip->end);
 505                 else if (touch->v.solid == SOLID_BSP)
 506                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->hullmins, clip->hullmaxs, clip->end);
 507                 else
 508                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins, clip->maxs, clip->end);
 509                 // LordHavoc: take the 'best' answers from the new trace and combine with existing data
 510                 if (trace.allsolid)
 511                         clip->trace.allsolid = true;
 512                 if (trace.startsolid)
 513                 {
 514                         clip->trace.startsolid = true;
 515                         if (!clip->trace.ent)
 516                                 clip->trace.ent = trace.ent;
 517                 }
 518                 if (trace.inopen)
 519                         clip->trace.inopen = true;
 520                 if (trace.inwater)
 521                         clip->trace.inwater = true;
 522                 if (trace.fraction < clip->trace.fraction)
 523                 {
 524                         clip->trace.fraction = trace.fraction;
 525                         VectorCopy(trace.endpos, clip->trace.endpos);
 526                         clip->trace.plane = trace.plane;
 527                         clip->trace.endcontents = trace.endcontents;
 528                         clip->trace.ent = trace.ent;
 529                 }
 530         }
 531
 532 // recurse down both sides
 533         if (node->axis == -1)
 534                 return;
 535
 536         if (clip->boxmaxs[node->axis] > node->dist)
 537         {
 538                 if (clip->boxmins[node->axis] < node->dist)
 539                         SV_ClipToLinks(node->children[1], clip);
 540                 node = node->children[0];
 541                 goto loc0;
 542         }
 543         else if (clip->boxmins[node->axis] < node->dist)
 544         {
 545                 node = node->children[1];
 546                 goto loc0;
 547         }
 548 }
 549
 550
 551 /*
 552 ==================
 553 SV_MoveBounds
 554 ==================
 555 */
 556 void SV_MoveBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
 557 {
 558 #if 0
 559 // debug to test against everything
 560 boxmins[0] = boxmins[1] = boxmins[2] = -999999999;
 561 boxmaxs[0] = boxmaxs[1] = boxmaxs[2] =  999999999;
 562 #else
 563         int             i;
 564
 565         for (i=0 ; i<3 ; i++)
 566         {
 567                 if (end[i] > start[i])
 568                 {
 569                         boxmins[i] = start[i] + mins[i] - 1;
 570                         boxmaxs[i] = end[i] + maxs[i] + 1;
 571                 }
 572                 else
 573                 {
 574                         boxmins[i] = end[i] + mins[i] - 1;
 575                         boxmaxs[i] = start[i] + maxs[i] + 1;
 576                 }
 577         }
 578 #endif
 579 }
 580
 581 /*
 582 ==================
 583 SV_Move
 584 ==================
 585 */
 586 trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, edict_t *passedict)
 587 {
 588         moveclip_t      clip;
 589         vec3_t          bigmins, bigmaxs;
 590         int                     i;
 591
 592         memset ( &clip, 0, sizeof ( moveclip_t ) );
 593
 594         VectorCopy(start, clip.start);
 595         VectorCopy(end, clip.end);
 596         VectorCopy(mins, clip.mins);
 597         VectorCopy(maxs, clip.maxs);
 598         clip.type = type;
 599         clip.passedict = passedict;
 600
 601         Collision_RoundUpToHullSize(sv.worldmodel, clip.mins, clip.maxs, clip.hullmins, clip.hullmaxs);
 602
 603         if (type == MOVE_MISSILE)
 604         {
 605                 // LordHavoc: modified this, was = -15, now = clip.mins[i] - 15
 606                 for (i=0 ; i<3 ; i++)
 607                 {
 608                         clip.mins2[i] = clip.mins[i] - 15;
 609                         clip.maxs2[i] = clip.maxs[i] + 15;
 610                 }
 611         }
 612         else
 613         {
 614                 VectorCopy (clip.mins, clip.mins2);
 615                 VectorCopy (clip.maxs, clip.maxs2);
 616         }
 617
 618         bigmins[0] = min(clip.mins2[0], clip.hullmins[0]);
 619         bigmaxs[0] = max(clip.maxs2[0], clip.hullmaxs[0]);
 620         bigmins[1] = min(clip.mins2[1], clip.hullmins[1]);
 621         bigmaxs[1] = max(clip.maxs2[1], clip.hullmaxs[1]);
 622         bigmins[2] = min(clip.mins2[2], clip.hullmins[2]);
 623         bigmaxs[2] = max(clip.maxs2[2], clip.hullmaxs[2]);
 624
 625         // clip to world
 626         clip.trace = SV_ClipMoveToEntity (sv.edicts, start, mins, maxs, end);
 627
 628         // clip to entities
 629         // create the bounding box of the entire move
 630         SV_MoveBounds ( start, bigmins, bigmaxs, end, clip.boxmins, clip.boxmaxs );
 631
 632         SV_ClipToLinks ( sv_areanodes, &clip );
 633
 634         return clip.trace;
 635 }
 636