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