sv_world.c (14297B)
1 /* 2 Copyright (C) 1997-2001 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 "server.h" 23 24 /* 25 =============================================================================== 26 27 ENTITY AREA CHECKING 28 29 FIXME: this use of "area" is different from the bsp file use 30 =============================================================================== 31 */ 32 33 // (type *)STRUCT_FROM_LINK(link_t *link, type, member) 34 // ent = STRUCT_FROM_LINK(link,entity_t,order) 35 // FIXME: remove this mess! 36 #define STRUCT_FROM_LINK(l,t,m) ((t *)((byte *)l - (int)&(((t *)0)->m))) 37 38 #define EDICT_FROM_AREA(l) STRUCT_FROM_LINK(l,edict_t,area) 39 40 typedef struct areanode_s 41 { 42 int axis; // -1 = leaf node 43 float dist; 44 struct areanode_s *children[2]; 45 link_t trigger_edicts; 46 link_t solid_edicts; 47 } areanode_t; 48 49 #define AREA_DEPTH 4 50 #define AREA_NODES 32 51 52 areanode_t sv_areanodes[AREA_NODES]; 53 int sv_numareanodes; 54 55 float *area_mins, *area_maxs; 56 edict_t **area_list; 57 int area_count, area_maxcount; 58 int area_type; 59 60 int SV_HullForEntity (edict_t *ent); 61 62 63 // ClearLink is used for new headnodes 64 void ClearLink (link_t *l) 65 { 66 l->prev = l->next = l; 67 } 68 69 void RemoveLink (link_t *l) 70 { 71 l->next->prev = l->prev; 72 l->prev->next = l->next; 73 } 74 75 void InsertLinkBefore (link_t *l, link_t *before) 76 { 77 l->next = before; 78 l->prev = before->prev; 79 l->prev->next = l; 80 l->next->prev = l; 81 } 82 83 /* 84 =============== 85 SV_CreateAreaNode 86 87 Builds a uniformly subdivided tree for the given world size 88 =============== 89 */ 90 areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs) 91 { 92 areanode_t *anode; 93 vec3_t size; 94 vec3_t mins1, maxs1, mins2, maxs2; 95 96 anode = &sv_areanodes[sv_numareanodes]; 97 sv_numareanodes++; 98 99 ClearLink (&anode->trigger_edicts); 100 ClearLink (&anode->solid_edicts); 101 102 if (depth == AREA_DEPTH) 103 { 104 anode->axis = -1; 105 anode->children[0] = anode->children[1] = NULL; 106 return anode; 107 } 108 109 VectorSubtract (maxs, mins, size); 110 if (size[0] > size[1]) 111 anode->axis = 0; 112 else 113 anode->axis = 1; 114 115 anode->dist = 0.5 * (maxs[anode->axis] + mins[anode->axis]); 116 VectorCopy (mins, mins1); 117 VectorCopy (mins, mins2); 118 VectorCopy (maxs, maxs1); 119 VectorCopy (maxs, maxs2); 120 121 maxs1[anode->axis] = mins2[anode->axis] = anode->dist; 122 123 anode->children[0] = SV_CreateAreaNode (depth+1, mins2, maxs2); 124 anode->children[1] = SV_CreateAreaNode (depth+1, mins1, maxs1); 125 126 return anode; 127 } 128 129 /* 130 =============== 131 SV_ClearWorld 132 133 =============== 134 */ 135 void SV_ClearWorld (void) 136 { 137 memset (sv_areanodes, 0, sizeof(sv_areanodes)); 138 sv_numareanodes = 0; 139 SV_CreateAreaNode (0, sv.models[1]->mins, sv.models[1]->maxs); 140 } 141 142 143 /* 144 =============== 145 SV_UnlinkEdict 146 147 =============== 148 */ 149 void SV_UnlinkEdict (edict_t *ent) 150 { 151 if (!ent->area.prev) 152 return; // not linked in anywhere 153 RemoveLink (&ent->area); 154 ent->area.prev = ent->area.next = NULL; 155 } 156 157 158 /* 159 =============== 160 SV_LinkEdict 161 162 =============== 163 */ 164 #define MAX_TOTAL_ENT_LEAFS 128 165 void SV_LinkEdict (edict_t *ent) 166 { 167 areanode_t *node; 168 int leafs[MAX_TOTAL_ENT_LEAFS]; 169 int clusters[MAX_TOTAL_ENT_LEAFS]; 170 int num_leafs; 171 int i, j, k; 172 int area; 173 int topnode; 174 175 if (ent->area.prev) 176 SV_UnlinkEdict (ent); // unlink from old position 177 178 if (ent == ge->edicts) 179 return; // don't add the world 180 181 if (!ent->inuse) 182 return; 183 184 // set the size 185 VectorSubtract (ent->maxs, ent->mins, ent->size); 186 187 // encode the size into the entity_state for client prediction 188 if (ent->solid == SOLID_BBOX && !(ent->svflags & SVF_DEADMONSTER)) 189 { // assume that x/y are equal and symetric 190 i = ent->maxs[0]/8; 191 if (i<1) 192 i = 1; 193 if (i>31) 194 i = 31; 195 196 // z is not symetric 197 j = (-ent->mins[2])/8; 198 if (j<1) 199 j = 1; 200 if (j>31) 201 j = 31; 202 203 // and z maxs can be negative... 204 k = (ent->maxs[2]+32)/8; 205 if (k<1) 206 k = 1; 207 if (k>63) 208 k = 63; 209 210 ent->s.solid = (k<<10) | (j<<5) | i; 211 } 212 else if (ent->solid == SOLID_BSP) 213 { 214 ent->s.solid = 31; // a solid_bbox will never create this value 215 } 216 else 217 ent->s.solid = 0; 218 219 // set the abs box 220 if (ent->solid == SOLID_BSP && 221 (ent->s.angles[0] || ent->s.angles[1] || ent->s.angles[2]) ) 222 { // expand for rotation 223 float max, v; 224 int i; 225 226 max = 0; 227 for (i=0 ; i<3 ; i++) 228 { 229 v =fabs( ent->mins[i]); 230 if (v > max) 231 max = v; 232 v =fabs( ent->maxs[i]); 233 if (v > max) 234 max = v; 235 } 236 for (i=0 ; i<3 ; i++) 237 { 238 ent->absmin[i] = ent->s.origin[i] - max; 239 ent->absmax[i] = ent->s.origin[i] + max; 240 } 241 } 242 else 243 { // normal 244 VectorAdd (ent->s.origin, ent->mins, ent->absmin); 245 VectorAdd (ent->s.origin, ent->maxs, ent->absmax); 246 } 247 248 // because movement is clipped an epsilon away from an actual edge, 249 // we must fully check even when bounding boxes don't quite touch 250 ent->absmin[0] -= 1; 251 ent->absmin[1] -= 1; 252 ent->absmin[2] -= 1; 253 ent->absmax[0] += 1; 254 ent->absmax[1] += 1; 255 ent->absmax[2] += 1; 256 257 // link to PVS leafs 258 ent->num_clusters = 0; 259 ent->areanum = 0; 260 ent->areanum2 = 0; 261 262 //get all leafs, including solids 263 num_leafs = CM_BoxLeafnums (ent->absmin, ent->absmax, 264 leafs, MAX_TOTAL_ENT_LEAFS, &topnode); 265 266 // set areas 267 for (i=0 ; i<num_leafs ; i++) 268 { 269 clusters[i] = CM_LeafCluster (leafs[i]); 270 area = CM_LeafArea (leafs[i]); 271 if (area) 272 { // doors may legally straggle two areas, 273 // but nothing should evern need more than that 274 if (ent->areanum && ent->areanum != area) 275 { 276 if (ent->areanum2 && ent->areanum2 != area && sv.state == ss_loading) 277 Com_DPrintf ("Object touching 3 areas at %f %f %f\n", 278 ent->absmin[0], ent->absmin[1], ent->absmin[2]); 279 ent->areanum2 = area; 280 } 281 else 282 ent->areanum = area; 283 } 284 } 285 286 if (num_leafs >= MAX_TOTAL_ENT_LEAFS) 287 { // assume we missed some leafs, and mark by headnode 288 ent->num_clusters = -1; 289 ent->headnode = topnode; 290 } 291 else 292 { 293 ent->num_clusters = 0; 294 for (i=0 ; i<num_leafs ; i++) 295 { 296 if (clusters[i] == -1) 297 continue; // not a visible leaf 298 for (j=0 ; j<i ; j++) 299 if (clusters[j] == clusters[i]) 300 break; 301 if (j == i) 302 { 303 if (ent->num_clusters == MAX_ENT_CLUSTERS) 304 { // assume we missed some leafs, and mark by headnode 305 ent->num_clusters = -1; 306 ent->headnode = topnode; 307 break; 308 } 309 310 ent->clusternums[ent->num_clusters++] = clusters[i]; 311 } 312 } 313 } 314 315 // if first time, make sure old_origin is valid 316 if (!ent->linkcount) 317 { 318 VectorCopy (ent->s.origin, ent->s.old_origin); 319 } 320 ent->linkcount++; 321 322 if (ent->solid == SOLID_NOT) 323 return; 324 325 // find the first node that the ent's box crosses 326 node = sv_areanodes; 327 while (1) 328 { 329 if (node->axis == -1) 330 break; 331 if (ent->absmin[node->axis] > node->dist) 332 node = node->children[0]; 333 else if (ent->absmax[node->axis] < node->dist) 334 node = node->children[1]; 335 else 336 break; // crosses the node 337 } 338 339 // link it in 340 if (ent->solid == SOLID_TRIGGER) 341 InsertLinkBefore (&ent->area, &node->trigger_edicts); 342 else 343 InsertLinkBefore (&ent->area, &node->solid_edicts); 344 345 } 346 347 348 /* 349 ==================== 350 SV_AreaEdicts_r 351 352 ==================== 353 */ 354 void SV_AreaEdicts_r (areanode_t *node) 355 { 356 link_t *l, *next, *start; 357 edict_t *check; 358 int count; 359 360 count = 0; 361 362 // touch linked edicts 363 if (area_type == AREA_SOLID) 364 start = &node->solid_edicts; 365 else 366 start = &node->trigger_edicts; 367 368 for (l=start->next ; l != start ; l = next) 369 { 370 next = l->next; 371 check = EDICT_FROM_AREA(l); 372 373 if (check->solid == SOLID_NOT) 374 continue; // deactivated 375 if (check->absmin[0] > area_maxs[0] 376 || check->absmin[1] > area_maxs[1] 377 || check->absmin[2] > area_maxs[2] 378 || check->absmax[0] < area_mins[0] 379 || check->absmax[1] < area_mins[1] 380 || check->absmax[2] < area_mins[2]) 381 continue; // not touching 382 383 if (area_count == area_maxcount) 384 { 385 Com_Printf ("SV_AreaEdicts: MAXCOUNT\n"); 386 return; 387 } 388 389 area_list[area_count] = check; 390 area_count++; 391 } 392 393 if (node->axis == -1) 394 return; // terminal node 395 396 // recurse down both sides 397 if ( area_maxs[node->axis] > node->dist ) 398 SV_AreaEdicts_r ( node->children[0] ); 399 if ( area_mins[node->axis] < node->dist ) 400 SV_AreaEdicts_r ( node->children[1] ); 401 } 402 403 /* 404 ================ 405 SV_AreaEdicts 406 ================ 407 */ 408 int SV_AreaEdicts (vec3_t mins, vec3_t maxs, edict_t **list, 409 int maxcount, int areatype) 410 { 411 area_mins = mins; 412 area_maxs = maxs; 413 area_list = list; 414 area_count = 0; 415 area_maxcount = maxcount; 416 area_type = areatype; 417 418 SV_AreaEdicts_r (sv_areanodes); 419 420 return area_count; 421 } 422 423 424 //=========================================================================== 425 426 /* 427 ============= 428 SV_PointContents 429 ============= 430 */ 431 int SV_PointContents (vec3_t p) 432 { 433 edict_t *touch[MAX_EDICTS], *hit; 434 int i, num; 435 int contents, c2; 436 int headnode; 437 float *angles; 438 439 // get base contents from world 440 contents = CM_PointContents (p, sv.models[1]->headnode); 441 442 // or in contents from all the other entities 443 num = SV_AreaEdicts (p, p, touch, MAX_EDICTS, AREA_SOLID); 444 445 for (i=0 ; i<num ; i++) 446 { 447 hit = touch[i]; 448 449 // might intersect, so do an exact clip 450 headnode = SV_HullForEntity (hit); 451 angles = hit->s.angles; 452 if (hit->solid != SOLID_BSP) 453 angles = vec3_origin; // boxes don't rotate 454 455 c2 = CM_TransformedPointContents (p, headnode, hit->s.origin, hit->s.angles); 456 457 contents |= c2; 458 } 459 460 return contents; 461 } 462 463 464 465 typedef struct 466 { 467 vec3_t boxmins, boxmaxs;// enclose the test object along entire move 468 float *mins, *maxs; // size of the moving object 469 vec3_t mins2, maxs2; // size when clipping against mosnters 470 float *start, *end; 471 trace_t trace; 472 edict_t *passedict; 473 int contentmask; 474 } moveclip_t; 475 476 477 478 /* 479 ================ 480 SV_HullForEntity 481 482 Returns a headnode that can be used for testing or clipping an 483 object of mins/maxs size. 484 Offset is filled in to contain the adjustment that must be added to the 485 testing object's origin to get a point to use with the returned hull. 486 ================ 487 */ 488 int SV_HullForEntity (edict_t *ent) 489 { 490 cmodel_t *model; 491 492 // decide which clipping hull to use, based on the size 493 if (ent->solid == SOLID_BSP) 494 { // explicit hulls in the BSP model 495 model = sv.models[ ent->s.modelindex ]; 496 497 if (!model) 498 Com_Error (ERR_FATAL, "MOVETYPE_PUSH with a non bsp model"); 499 500 return model->headnode; 501 } 502 503 // create a temp hull from bounding box sizes 504 505 return CM_HeadnodeForBox (ent->mins, ent->maxs); 506 } 507 508 509 //=========================================================================== 510 511 /* 512 ==================== 513 SV_ClipMoveToEntities 514 515 ==================== 516 */ 517 void SV_ClipMoveToEntities ( moveclip_t *clip ) 518 { 519 int i, num; 520 edict_t *touchlist[MAX_EDICTS], *touch; 521 trace_t trace; 522 int headnode; 523 float *angles; 524 525 num = SV_AreaEdicts (clip->boxmins, clip->boxmaxs, touchlist 526 , MAX_EDICTS, AREA_SOLID); 527 528 // be careful, it is possible to have an entity in this 529 // list removed before we get to it (killtriggered) 530 for (i=0 ; i<num ; i++) 531 { 532 touch = touchlist[i]; 533 if (touch->solid == SOLID_NOT) 534 continue; 535 if (touch == clip->passedict) 536 continue; 537 if (clip->trace.allsolid) 538 return; 539 if (clip->passedict) 540 { 541 if (touch->owner == clip->passedict) 542 continue; // don't clip against own missiles 543 if (clip->passedict->owner == touch) 544 continue; // don't clip against owner 545 } 546 547 if ( !(clip->contentmask & CONTENTS_DEADMONSTER) 548 && (touch->svflags & SVF_DEADMONSTER) ) 549 continue; 550 551 // might intersect, so do an exact clip 552 headnode = SV_HullForEntity (touch); 553 angles = touch->s.angles; 554 if (touch->solid != SOLID_BSP) 555 angles = vec3_origin; // boxes don't rotate 556 557 if (touch->svflags & SVF_MONSTER) 558 trace = CM_TransformedBoxTrace (clip->start, clip->end, 559 clip->mins2, clip->maxs2, headnode, clip->contentmask, 560 touch->s.origin, angles); 561 else 562 trace = CM_TransformedBoxTrace (clip->start, clip->end, 563 clip->mins, clip->maxs, headnode, clip->contentmask, 564 touch->s.origin, angles); 565 566 if (trace.allsolid || trace.startsolid || 567 trace.fraction < clip->trace.fraction) 568 { 569 trace.ent = touch; 570 if (clip->trace.startsolid) 571 { 572 clip->trace = trace; 573 clip->trace.startsolid = true; 574 } 575 else 576 clip->trace = trace; 577 } 578 else if (trace.startsolid) 579 clip->trace.startsolid = true; 580 } 581 } 582 583 584 /* 585 ================== 586 SV_TraceBounds 587 ================== 588 */ 589 void SV_TraceBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs) 590 { 591 #if 0 592 // debug to test against everything 593 boxmins[0] = boxmins[1] = boxmins[2] = -9999; 594 boxmaxs[0] = boxmaxs[1] = boxmaxs[2] = 9999; 595 #else 596 int i; 597 598 for (i=0 ; i<3 ; i++) 599 { 600 if (end[i] > start[i]) 601 { 602 boxmins[i] = start[i] + mins[i] - 1; 603 boxmaxs[i] = end[i] + maxs[i] + 1; 604 } 605 else 606 { 607 boxmins[i] = end[i] + mins[i] - 1; 608 boxmaxs[i] = start[i] + maxs[i] + 1; 609 } 610 } 611 #endif 612 } 613 614 /* 615 ================== 616 SV_Trace 617 618 Moves the given mins/maxs volume through the world from start to end. 619 620 Passedict and edicts owned by passedict are explicitly not checked. 621 622 ================== 623 */ 624 trace_t SV_Trace (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, edict_t *passedict, int contentmask) 625 { 626 moveclip_t clip; 627 628 if (!mins) 629 mins = vec3_origin; 630 if (!maxs) 631 maxs = vec3_origin; 632 633 memset ( &clip, 0, sizeof ( moveclip_t ) ); 634 635 // clip to world 636 clip.trace = CM_BoxTrace (start, end, mins, maxs, 0, contentmask); 637 clip.trace.ent = ge->edicts; 638 if (clip.trace.fraction == 0) 639 return clip.trace; // blocked by the world 640 641 clip.contentmask = contentmask; 642 clip.start = start; 643 clip.end = end; 644 clip.mins = mins; 645 clip.maxs = maxs; 646 clip.passedict = passedict; 647 648 VectorCopy (mins, clip.mins2); 649 VectorCopy (maxs, clip.maxs2); 650 651 // create the bounding box of the entire move 652 SV_TraceBounds ( start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs ); 653 654 // clip to other solid entities 655 SV_ClipMoveToEntities ( &clip ); 656 657 return clip.trace; 658 } 659