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_HullPointContents
 389
 390 ==================
 391 */
 392 int SV_HullPointContents (hull_t *hull, int num, vec3_t p)
 393 {
 394         while (num >= 0)
 395                 num = hull->clipnodes[num].children[(hull->planes[hull->clipnodes[num].planenum].type < 3 ? p[hull->planes[hull->clipnodes[num].planenum].type] : DotProduct (hull->planes[hull->clipnodes[num].planenum].normal, p)) < hull->planes[hull->clipnodes[num].planenum].dist];
 396
 397         return num;
 398 }
 399
 400 /*
 401 ============
 402 SV_TestEntityPosition
 403
 404 This could be a lot more efficient...
 405 ============
 406 */
 407 edict_t *SV_TestEntityPosition (edict_t *ent)
 408 {
 409         trace_t trace;
 410
 411         trace = SV_Move (ent->v.origin, ent->v.mins, ent->v.maxs, ent->v.origin, MOVE_NORMAL, ent);
 412
 413         if (trace.startsolid)
 414                 return sv.edicts;
 415
 416         return NULL;
 417 }
 418
 419
 420 /*
 421 ===============================================================================
 422
 423 LINE TESTING IN HULLS
 424
 425 ===============================================================================
 426 */
 427
 428 /*
 429 ==================
 430 SV_ClipMoveToEntity
 431
 432 Handles selection or creation of a clipping hull, and offseting (and
 433 eventually rotation) of the end points
 434 ==================
 435 */
 436 trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end)
 437 {
 438         int i;
 439         trace_t trace;
 440         model_t *model;
 441
 442         i = ent->v.modelindex;
 443         if ((unsigned int) i >= MAX_MODELS)
 444                 PR_RunError("SV_ClipMoveToEntity: invalid modelindex\n");
 445         model = sv.models[i];
 446         if (i != 0 && model == NULL)
 447                 PR_RunError("SV_ClipMoveToEntity: invalid modelindex\n");
 448
 449         if ((int) ent->v.solid == SOLID_BSP)
 450         {
 451                 Mod_CheckLoaded(model);
 452                 if (model->type != mod_brush)
 453                 {
 454                         Con_Printf ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model, entity dump:\n");
 455                         ED_Print (ent);
 456                         Host_Error ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model\n");
 457                 }
 458                 if (ent->v.movetype != MOVETYPE_PUSH)
 459                         Host_Error ("SV_ClipMoveToEntity: SOLID_BSP without MOVETYPE_PUSH");
 460         }
 461
 462         Collision_ClipTrace(&trace, ent, model, ent->v.origin, ent->v.angles, ent->v.mins, ent->v.maxs, start, mins, maxs, end);
 463
 464         return trace;
 465 }
 466
 467 //===========================================================================
 468
 469 /*
 470 ====================
 471 SV_ClipToLinks
 472
 473 Mins and maxs enclose the entire area swept by the move
 474 ====================
 475 */
 476 void SV_ClipToLinks ( areanode_t *node, moveclip_t *clip )
 477 {
 478         link_t          *l, *next;
 479         edict_t         *touch;
 480         trace_t         trace;
 481
 482 loc0:
 483         if (clip->trace.allsolid)
 484                 return;
 485 // touch linked edicts
 486         for (l = node->solid_edicts.next ; l != &node->solid_edicts ; l = next)
 487         {
 488                 next = l->next;
 489                 touch = EDICT_FROM_AREA(l);
 490                 if (touch->v.solid == SOLID_NOT)
 491                         continue;
 492                 if (touch == clip->passedict)
 493                         continue;
 494                 if (touch->v.solid == SOLID_TRIGGER)
 495                         Host_Error ("Trigger in clipping list");
 496
 497                 if (clip->type == MOVE_NOMONSTERS && touch->v.solid != SOLID_BSP)
 498                         continue;
 499
 500                 if (clip->boxmins[0] > touch->v.absmax[0]
 501                  || clip->boxmaxs[0] < touch->v.absmin[0]
 502                  || clip->boxmins[1] > touch->v.absmax[1]
 503                  || clip->boxmaxs[1] < touch->v.absmin[1]
 504                  || clip->boxmins[2] > touch->v.absmax[2]
 505                  || clip->boxmaxs[2] < touch->v.absmin[2])
 506                         continue;
 507
 508                 if (clip->passedict)
 509                 {
 510                         if (clip->passedict->v.size[0] && !touch->v.size[0])
 511                                 continue;       // points never interact
 512                         if (PROG_TO_EDICT(touch->v.owner) == clip->passedict)
 513                                 continue;       // don't clip against own missiles
 514                         if (PROG_TO_EDICT(clip->passedict->v.owner) == touch)
 515                                 continue;       // don't clip against owner
 516                         // LordHavoc: corpse code
 517                         if (clip->passedict->v.solid == SOLID_CORPSE && (touch->v.solid == SOLID_SLIDEBOX || touch->v.solid == SOLID_CORPSE))
 518                                 continue;
 519                         if (clip->passedict->v.solid == SOLID_SLIDEBOX && touch->v.solid == SOLID_CORPSE)
 520                                 continue;
 521                 }
 522
 523                 // might interact, so do an exact clip
 524                 if ((int)touch->v.flags & FL_MONSTER)
 525                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins2, clip->maxs2, clip->end);
 526                 else if (touch->v.solid == SOLID_BSP)
 527                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->hullmins, clip->hullmaxs, clip->end);
 528                 else
 529                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins, clip->maxs, clip->end);
 530                 // LordHavoc: take the 'best' answers from the new trace and combine with existing data
 531                 if (trace.allsolid)
 532                         clip->trace.allsolid = true;
 533                 if (trace.startsolid)
 534                 {
 535                         clip->trace.startsolid = true;
 536                         if (!clip->trace.ent)
 537                                 clip->trace.ent = trace.ent;
 538                 }
 539                 if (trace.inopen)
 540                         clip->trace.inopen = true;
 541                 if (trace.inwater)
 542                         clip->trace.inwater = true;
 543                 if (trace.fraction < clip->trace.fraction)
 544                 {
 545                         clip->trace.fraction = trace.fraction;
 546                         VectorCopy(trace.endpos, clip->trace.endpos);
 547                         clip->trace.plane = trace.plane;
 548                         clip->trace.endcontents = trace.endcontents;
 549                         clip->trace.ent = trace.ent;
 550                 }
 551         }
 552
 553 // recurse down both sides
 554         if (node->axis == -1)
 555                 return;
 556
 557         if (clip->boxmaxs[node->axis] > node->dist)
 558         {
 559                 if (clip->boxmins[node->axis] < node->dist)
 560                         SV_ClipToLinks(node->children[1], clip);
 561                 node = node->children[0];
 562                 goto loc0;
 563         }
 564         else if (clip->boxmins[node->axis] < node->dist)
 565         {
 566                 node = node->children[1];
 567                 goto loc0;
 568         }
 569 }
 570
 571
 572 /*
 573 ==================
 574 SV_MoveBounds
 575 ==================
 576 */
 577 void SV_MoveBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
 578 {
 579 #if 0
 580 // debug to test against everything
 581 boxmins[0] = boxmins[1] = boxmins[2] = -999999999;
 582 boxmaxs[0] = boxmaxs[1] = boxmaxs[2] =  999999999;
 583 #else
 584         int             i;
 585
 586         for (i=0 ; i<3 ; i++)
 587         {
 588                 if (end[i] > start[i])
 589                 {
 590                         boxmins[i] = start[i] + mins[i] - 1;
 591                         boxmaxs[i] = end[i] + maxs[i] + 1;
 592                 }
 593                 else
 594                 {
 595                         boxmins[i] = end[i] + mins[i] - 1;
 596                         boxmaxs[i] = start[i] + maxs[i] + 1;
 597                 }
 598         }
 599 #endif
 600 }
 601
 602 /*
 603 ==================
 604 SV_Move
 605 ==================
 606 */
 607 trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, edict_t *passedict)
 608 {
 609         moveclip_t      clip;
 610         vec3_t          bigmins, bigmaxs;
 611         int                     i;
 612
 613         memset ( &clip, 0, sizeof ( moveclip_t ) );
 614
 615         VectorCopy(start, clip.start);
 616         VectorCopy(end, clip.end);
 617         VectorCopy(mins, clip.mins);
 618         VectorCopy(maxs, clip.maxs);
 619         clip.type = type;
 620         clip.passedict = passedict;
 621
 622         Collision_RoundUpToHullSize(sv.worldmodel, clip.mins, clip.maxs, clip.hullmins, clip.hullmaxs);
 623
 624         if (type == MOVE_MISSILE)
 625         {
 626                 // LordHavoc: modified this, was = -15, now = clip.mins[i] - 15
 627                 for (i=0 ; i<3 ; i++)
 628                 {
 629                         clip.mins2[i] = clip.mins[i] - 15;
 630                         clip.maxs2[i] = clip.maxs[i] + 15;
 631                 }
 632         }
 633         else
 634         {
 635                 VectorCopy (clip.mins, clip.mins2);
 636                 VectorCopy (clip.maxs, clip.maxs2);
 637         }
 638
 639         bigmins[0] = min(clip.mins2[0], clip.hullmins[0]);
 640         bigmaxs[0] = max(clip.maxs2[0], clip.hullmaxs[0]);
 641         bigmins[1] = min(clip.mins2[1], clip.hullmins[1]);
 642         bigmaxs[1] = max(clip.maxs2[1], clip.hullmaxs[1]);
 643         bigmins[2] = min(clip.mins2[2], clip.hullmins[2]);
 644         bigmaxs[2] = max(clip.maxs2[2], clip.hullmaxs[2]);
 645
 646         // clip to world
 647         clip.trace = SV_ClipMoveToEntity (sv.edicts, start, mins, maxs, end);
 648
 649         // clip to entities
 650         // create the bounding box of the entire move
 651         SV_MoveBounds ( start, bigmins, bigmaxs, end, clip.boxmins, clip.boxmaxs );
 652
 653         SV_ClipToLinks ( sv_areanodes, &clip );
 654
 655         return clip.trace;
 656 }
 657