1 /*
2 ===========================================================================
3
4 Return to Castle Wolfenstein single player GPL Source Code
5 Copyright (C) 1999-2010 id Software LLC, a ZeniMax Media company.
6
7 This file is part of the Return to Castle Wolfenstein single player GPL Source Code (RTCW SP Source Code).
8
9 RTCW SP Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13
14 RTCW SP Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with RTCW SP Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the RTCW SP Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the RTCW SP Source Code. If not, please request a copy in writing from id Software at the address below.
23
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
25
26 ===========================================================================
27 */
28
29 // world.c -- world query functions
30
31 #include "server.h"
32
33 /*
34 ================
35 SV_ClipHandleForEntity
36
37 Returns a headnode that can be used for testing or clipping to a
38 given entity. If the entity is a bsp model, the headnode will
39 be returned, otherwise a custom box tree will be constructed.
40 ================
41 */
SV_ClipHandleForEntity(const sharedEntity_t * ent)42 clipHandle_t SV_ClipHandleForEntity( const sharedEntity_t *ent ) {
43 if ( ent->r.bmodel ) {
44 // explicit hulls in the BSP model
45 return CM_InlineModel( ent->s.modelindex );
46 }
47 if ( ent->r.svFlags & SVF_CAPSULE ) {
48 // create a temp capsule from bounding box sizes
49 return CM_TempBoxModel( ent->r.mins, ent->r.maxs, qtrue );
50 }
51
52 // create a temp tree from bounding box sizes
53 return CM_TempBoxModel( ent->r.mins, ent->r.maxs, qfalse );
54 }
55
56
57
58 /*
59 ===============================================================================
60
61 ENTITY CHECKING
62
63 To avoid linearly searching through lists of entities during environment testing,
64 the world is carved up with an evenly spaced, axially aligned bsp tree. Entities
65 are kept in chains either at the final leafs, or at the first node that splits
66 them, which prevents having to deal with multiple fragments of a single entity.
67
68 ===============================================================================
69 */
70
71 typedef struct worldSector_s {
72 int axis; // -1 = leaf node
73 float dist;
74 struct worldSector_s *children[2];
75 svEntity_t *entities;
76 } worldSector_t;
77
78 #define AREA_DEPTH 4
79 #define AREA_NODES 64
80
81 worldSector_t sv_worldSectors[AREA_NODES];
82 int sv_numworldSectors;
83
84
85 /*
86 ===============
87 SV_SectorList_f
88 ===============
89 */
SV_SectorList_f(void)90 void SV_SectorList_f( void ) {
91 int i, c;
92 worldSector_t *sec;
93 svEntity_t *ent;
94
95 for ( i = 0 ; i < AREA_NODES ; i++ ) {
96 sec = &sv_worldSectors[i];
97
98 c = 0;
99 for ( ent = sec->entities ; ent ; ent = ent->nextEntityInWorldSector ) {
100 c++;
101 }
102 Com_Printf( "sector %i: %i entities\n", i, c );
103 }
104 }
105
106 /*
107 ===============
108 SV_CreateworldSector
109
110 Builds a uniformly subdivided tree for the given world size
111 ===============
112 */
SV_CreateworldSector(int depth,vec3_t mins,vec3_t maxs)113 static worldSector_t *SV_CreateworldSector( int depth, vec3_t mins, vec3_t maxs ) {
114 worldSector_t *anode;
115 vec3_t size;
116 vec3_t mins1, maxs1, mins2, maxs2;
117
118 anode = &sv_worldSectors[sv_numworldSectors];
119 sv_numworldSectors++;
120
121 if ( depth == AREA_DEPTH ) {
122 anode->axis = -1;
123 anode->children[0] = anode->children[1] = NULL;
124 return anode;
125 }
126
127 VectorSubtract( maxs, mins, size );
128 if ( size[0] > size[1] ) {
129 anode->axis = 0;
130 } else {
131 anode->axis = 1;
132 }
133
134 anode->dist = 0.5 * ( maxs[anode->axis] + mins[anode->axis] );
135 VectorCopy( mins, mins1 );
136 VectorCopy( mins, mins2 );
137 VectorCopy( maxs, maxs1 );
138 VectorCopy( maxs, maxs2 );
139
140 maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
141
142 anode->children[0] = SV_CreateworldSector( depth + 1, mins2, maxs2 );
143 anode->children[1] = SV_CreateworldSector( depth + 1, mins1, maxs1 );
144
145 return anode;
146 }
147
148 /*
149 ===============
150 SV_ClearWorld
151
152 ===============
153 */
SV_ClearWorld(void)154 void SV_ClearWorld( void ) {
155 clipHandle_t h;
156 vec3_t mins, maxs;
157
158 memset( sv_worldSectors, 0, sizeof( sv_worldSectors ) );
159 sv_numworldSectors = 0;
160
161 // get world map bounds
162 h = CM_InlineModel( 0 );
163 CM_ModelBounds( h, mins, maxs );
164 SV_CreateworldSector( 0, mins, maxs );
165 }
166
167
168 /*
169 ===============
170 SV_UnlinkEntity
171
172 ===============
173 */
SV_UnlinkEntity(sharedEntity_t * gEnt)174 void SV_UnlinkEntity( sharedEntity_t *gEnt ) {
175 svEntity_t *ent;
176 svEntity_t *scan;
177 worldSector_t *ws;
178
179 ent = SV_SvEntityForGentity( gEnt );
180
181 gEnt->r.linked = qfalse;
182
183 ws = ent->worldSector;
184 if ( !ws ) {
185 return; // not linked in anywhere
186 }
187 ent->worldSector = NULL;
188
189 if ( ws->entities == ent ) {
190 ws->entities = ent->nextEntityInWorldSector;
191 return;
192 }
193
194 for ( scan = ws->entities ; scan ; scan = scan->nextEntityInWorldSector ) {
195 if ( scan->nextEntityInWorldSector == ent ) {
196 scan->nextEntityInWorldSector = ent->nextEntityInWorldSector;
197 return;
198 }
199 }
200
201 Com_Printf( "WARNING: SV_UnlinkEntity: not found in worldSector\n" );
202 }
203
204
205 /*
206 ===============
207 SV_LinkEntity
208
209 ===============
210 */
211 #define MAX_TOTAL_ENT_LEAFS 128
212 worldSector_t *debugNode;
SV_LinkEntity(sharedEntity_t * gEnt)213 void SV_LinkEntity( sharedEntity_t *gEnt ) {
214 worldSector_t *node;
215 int leafs[MAX_TOTAL_ENT_LEAFS];
216 int cluster;
217 int num_leafs;
218 int i, j, k;
219 int area;
220 int lastLeaf;
221 float *origin, *angles;
222 svEntity_t *ent;
223
224 ent = SV_SvEntityForGentity( gEnt );
225
226 // Ridah, sanity check for possible currentOrigin being reset bug
227 if ( !gEnt->r.bmodel && VectorCompare( gEnt->r.currentOrigin, vec3_origin ) ) {
228 Com_DPrintf( "WARNING: BBOX entity is being linked at world origin, this is probably a bug\n" );
229 }
230
231 if ( ent->worldSector ) {
232 SV_UnlinkEntity( gEnt ); // unlink from old position
233 }
234
235 // encode the size into the entityState_t for client prediction
236 if ( gEnt->r.bmodel ) {
237 gEnt->s.solid = SOLID_BMODEL; // a solid_box will never create this value
238 } else if ( gEnt->r.contents & ( CONTENTS_SOLID | CONTENTS_BODY ) ) {
239 // assume that x/y are equal and symetric
240 i = gEnt->r.maxs[0];
241 if ( i < 1 ) {
242 i = 1;
243 }
244 if ( i > 255 ) {
245 i = 255;
246 }
247
248 // z is not symetric
249 j = ( -gEnt->r.mins[2] );
250 if ( j < 1 ) {
251 j = 1;
252 }
253 if ( j > 255 ) {
254 j = 255;
255 }
256
257 // and z maxs can be negative...
258 k = ( gEnt->r.maxs[2] + 32 );
259 if ( k < 1 ) {
260 k = 1;
261 }
262 if ( k > 255 ) {
263 k = 255;
264 }
265
266 gEnt->s.solid = ( k << 16 ) | ( j << 8 ) | i;
267 } else {
268 gEnt->s.solid = 0;
269 }
270
271 // get the position
272 origin = gEnt->r.currentOrigin;
273 angles = gEnt->r.currentAngles;
274
275 // set the abs box
276 if ( gEnt->r.bmodel && ( angles[0] || angles[1] || angles[2] ) ) {
277 // expand for rotation
278 float max;
279
280 max = RadiusFromBounds( gEnt->r.mins, gEnt->r.maxs );
281 for ( i = 0 ; i < 3 ; i++ ) {
282 gEnt->r.absmin[i] = origin[i] - max;
283 gEnt->r.absmax[i] = origin[i] + max;
284 }
285 } else {
286 // normal
287 VectorAdd( origin, gEnt->r.mins, gEnt->r.absmin );
288 VectorAdd( origin, gEnt->r.maxs, gEnt->r.absmax );
289 }
290
291 // because movement is clipped an epsilon away from an actual edge,
292 // we must fully check even when bounding boxes don't quite touch
293 gEnt->r.absmin[0] -= 1;
294 gEnt->r.absmin[1] -= 1;
295 gEnt->r.absmin[2] -= 1;
296 gEnt->r.absmax[0] += 1;
297 gEnt->r.absmax[1] += 1;
298 gEnt->r.absmax[2] += 1;
299
300 // link to PVS leafs
301 ent->numClusters = 0;
302 ent->lastCluster = 0;
303 ent->areanum = -1;
304 ent->areanum2 = -1;
305
306 //get all leafs, including solids
307 num_leafs = CM_BoxLeafnums( gEnt->r.absmin, gEnt->r.absmax,
308 leafs, MAX_TOTAL_ENT_LEAFS, &lastLeaf );
309
310 // if none of the leafs were inside the map, the
311 // entity is outside the world and can be considered unlinked
312 if ( !num_leafs ) {
313 return;
314 }
315
316 // set areas, even from clusters that don't fit in the entity array
317 for ( i = 0 ; i < num_leafs ; i++ ) {
318 area = CM_LeafArea( leafs[i] );
319 if ( area != -1 ) {
320 // doors may legally straggle two areas,
321 // but nothing should evern need more than that
322 if ( ent->areanum != -1 && ent->areanum != area ) {
323 if ( ent->areanum2 != -1 && ent->areanum2 != area && sv.state == SS_LOADING ) {
324 Com_DPrintf( "Object %i touching 3 areas at %f %f %f\n",
325 gEnt->s.number,
326 gEnt->r.absmin[0], gEnt->r.absmin[1], gEnt->r.absmin[2] );
327 }
328 ent->areanum2 = area;
329 } else {
330 ent->areanum = area;
331 }
332 }
333 }
334
335 // store as many explicit clusters as we can
336 ent->numClusters = 0;
337 for ( i = 0 ; i < num_leafs ; i++ ) {
338 cluster = CM_LeafCluster( leafs[i] );
339 if ( cluster != -1 ) {
340 ent->clusternums[ent->numClusters++] = cluster;
341 if ( ent->numClusters == MAX_ENT_CLUSTERS ) {
342 break;
343 }
344 }
345 }
346
347 // store off a last cluster if we need to
348 if ( i != num_leafs ) {
349 ent->lastCluster = CM_LeafCluster( lastLeaf );
350 }
351
352 gEnt->r.linkcount++;
353
354 // find the first world sector node that the ent's box crosses
355 node = sv_worldSectors;
356 while ( 1 )
357 {
358 if ( node->axis == -1 ) {
359 break;
360 }
361 if ( gEnt->r.absmin[node->axis] > node->dist ) {
362 node = node->children[0];
363 } else if ( gEnt->r.absmax[node->axis] < node->dist ) {
364 node = node->children[1];
365 } else {
366 break; // crosses the node
367 }
368 }
369
370 // link it in
371 ent->worldSector = node;
372 ent->nextEntityInWorldSector = node->entities;
373 node->entities = ent;
374
375 gEnt->r.linked = qtrue;
376 }
377
378 /*
379 ============================================================================
380
381 AREA QUERY
382
383 Fills in a list of all entities who's absmin / absmax intersects the given
384 bounds. This does NOT mean that they actually touch in the case of bmodels.
385 ============================================================================
386 */
387
388 typedef struct {
389 const float *mins;
390 const float *maxs;
391 int *list;
392 int count, maxcount;
393 } areaParms_t;
394
395
396 /*
397 ====================
398 SV_AreaEntities_r
399
400 ====================
401 */
SV_AreaEntities_r(worldSector_t * node,areaParms_t * ap)402 static void SV_AreaEntities_r( worldSector_t *node, areaParms_t *ap ) {
403 svEntity_t *check, *next;
404 sharedEntity_t *gcheck;
405
406 for ( check = node->entities ; check ; check = next ) {
407 next = check->nextEntityInWorldSector;
408
409 gcheck = SV_GEntityForSvEntity( check );
410
411 if ( gcheck->r.absmin[0] > ap->maxs[0]
412 || gcheck->r.absmin[1] > ap->maxs[1]
413 || gcheck->r.absmin[2] > ap->maxs[2]
414 || gcheck->r.absmax[0] < ap->mins[0]
415 || gcheck->r.absmax[1] < ap->mins[1]
416 || gcheck->r.absmax[2] < ap->mins[2] ) {
417 continue;
418 }
419
420 if ( ap->count == ap->maxcount ) {
421 Com_DPrintf( "SV_AreaEntities: MAXCOUNT\n" );
422 return;
423 }
424
425 ap->list[ap->count] = check - sv.svEntities;
426 ap->count++;
427 }
428
429 if ( node->axis == -1 ) {
430 return; // terminal node
431 }
432
433 // recurse down both sides
434 if ( ap->maxs[node->axis] > node->dist ) {
435 SV_AreaEntities_r( node->children[0], ap );
436 }
437 if ( ap->mins[node->axis] < node->dist ) {
438 SV_AreaEntities_r( node->children[1], ap );
439 }
440 }
441
442 /*
443 ================
444 SV_AreaEntities
445 ================
446 */
SV_AreaEntities(const vec3_t mins,const vec3_t maxs,int * entityList,int maxcount)447 int SV_AreaEntities( const vec3_t mins, const vec3_t maxs, int *entityList, int maxcount ) {
448 areaParms_t ap;
449
450 ap.mins = mins;
451 ap.maxs = maxs;
452 ap.list = entityList;
453 ap.count = 0;
454 ap.maxcount = maxcount;
455
456 SV_AreaEntities_r( sv_worldSectors, &ap );
457
458 return ap.count;
459 }
460
461
462
463 //===========================================================================
464
465
466 typedef struct {
467 vec3_t boxmins, boxmaxs; // enclose the test object along entire move
468 const float *mins;
469 const float *maxs; // size of the moving object
470 const float *start;
471 vec3_t end;
472 trace_t trace;
473 int passEntityNum;
474 int contentmask;
475 int capsule;
476 } moveclip_t;
477
478
479 /*
480 ====================
481 SV_ClipToEntity
482
483 ====================
484 */
SV_ClipToEntity(trace_t * trace,const vec3_t start,const vec3_t mins,const vec3_t maxs,const vec3_t end,int entityNum,int contentmask,int capsule)485 void SV_ClipToEntity( trace_t *trace, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int entityNum, int contentmask, int capsule ) {
486 sharedEntity_t *touch;
487 clipHandle_t clipHandle;
488 float *origin, *angles;
489
490 touch = SV_GentityNum( entityNum );
491
492 memset( trace, 0, sizeof( trace_t ) );
493
494 // if it doesn't have any brushes of a type we
495 // are looking for, ignore it
496 if ( !( contentmask & touch->r.contents ) ) {
497 trace->fraction = 1.0;
498 return;
499 }
500
501 // might intersect, so do an exact clip
502 clipHandle = SV_ClipHandleForEntity( touch );
503
504 origin = touch->r.currentOrigin;
505 angles = touch->r.currentAngles;
506
507 if ( !touch->r.bmodel ) {
508 angles = vec3_origin; // boxes don't rotate
509 }
510
511 CM_TransformedBoxTrace( trace, start, end,
512 mins, maxs, clipHandle, contentmask,
513 origin, angles, capsule );
514 if ( trace->fraction < 1 ) {
515 trace->entityNum = touch->s.number;
516 }
517 }
518
519
520 /*
521 ====================
522 SV_ClipMoveToEntities
523
524 ====================
525 */
SV_ClipMoveToEntities(moveclip_t * clip)526 static void SV_ClipMoveToEntities( moveclip_t *clip ) {
527 int i, num;
528 int touchlist[MAX_GENTITIES];
529 sharedEntity_t *touch;
530 int passOwnerNum;
531 trace_t trace;
532 clipHandle_t clipHandle;
533 float *origin, *angles;
534
535 num = SV_AreaEntities( clip->boxmins, clip->boxmaxs, touchlist, MAX_GENTITIES );
536
537 if ( clip->passEntityNum != ENTITYNUM_NONE ) {
538 passOwnerNum = ( SV_GentityNum( clip->passEntityNum ) )->r.ownerNum;
539 if ( passOwnerNum == ENTITYNUM_NONE ) {
540 passOwnerNum = -1;
541 }
542 } else {
543 passOwnerNum = -1;
544 }
545
546 for ( i = 0 ; i < num ; i++ ) {
547 if ( clip->trace.allsolid ) {
548 return;
549 }
550 touch = SV_GentityNum( touchlist[i] );
551
552 // see if we should ignore this entity
553 if ( clip->passEntityNum != ENTITYNUM_NONE ) {
554 if ( touchlist[i] == clip->passEntityNum ) {
555 continue; // don't clip against the pass entity
556 }
557 if ( touch->r.ownerNum == clip->passEntityNum ) {
558 continue; // don't clip against own missiles
559 }
560 if ( touch->r.ownerNum == passOwnerNum ) {
561 continue; // don't clip against other missiles from our owner
562 }
563 }
564
565 // if it doesn't have any brushes of a type we
566 // are looking for, ignore it
567 if ( !( clip->contentmask & touch->r.contents ) ) {
568 continue;
569 }
570
571 // RF, special case, ignore chairs if we are carrying them
572 if ( touch->s.eType == ET_PROP && touch->s.otherEntityNum == clip->passEntityNum + 1 ) {
573 continue;
574 }
575
576 // might intersect, so do an exact clip
577 clipHandle = SV_ClipHandleForEntity( touch );
578
579 origin = touch->r.currentOrigin;
580 angles = touch->r.currentAngles;
581
582
583 if ( !touch->r.bmodel ) {
584 angles = vec3_origin; // boxes don't rotate
585 }
586
587 CM_TransformedBoxTrace( &trace, clip->start, clip->end,
588 clip->mins, clip->maxs, clipHandle, clip->contentmask,
589 origin, angles, clip->capsule );
590
591 if ( trace.allsolid ) {
592 clip->trace.allsolid = qtrue;
593 trace.entityNum = touch->s.number;
594 } else if ( trace.startsolid ) {
595 clip->trace.startsolid = qtrue;
596 trace.entityNum = touch->s.number;
597 }
598
599 if ( trace.fraction < clip->trace.fraction ) {
600 qboolean oldStart;
601
602 // make sure we keep a startsolid from a previous trace
603 oldStart = clip->trace.startsolid;
604
605 trace.entityNum = touch->s.number;
606 clip->trace = trace;
607 clip->trace.startsolid |= oldStart;
608 }
609 }
610 }
611
612
613 /*
614 ==================
615 SV_Trace
616
617 Moves the given mins/maxs volume through the world from start to end.
618 passEntityNum and entities owned by passEntityNum are explicitly not checked.
619 ==================
620 */
SV_Trace(trace_t * results,const vec3_t start,const vec3_t mins,const vec3_t maxs,const vec3_t end,int passEntityNum,int contentmask,int capsule)621 void SV_Trace( trace_t *results, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int passEntityNum, int contentmask, int capsule ) {
622 moveclip_t clip;
623 int i;
624
625 if ( !mins ) {
626 mins = vec3_origin;
627 }
628 if ( !maxs ) {
629 maxs = vec3_origin;
630 }
631
632 memset( &clip, 0, sizeof( moveclip_t ) );
633
634 // clip to world
635 CM_BoxTrace( &clip.trace, start, end, mins, maxs, 0, contentmask, capsule );
636 clip.trace.entityNum = clip.trace.fraction != 1.0 ? ENTITYNUM_WORLD : ENTITYNUM_NONE;
637 if ( clip.trace.fraction == 0 ) {
638 *results = clip.trace;
639 return; // blocked immediately by the world
640 }
641
642 clip.contentmask = contentmask;
643 clip.start = start;
644 // VectorCopy( clip.trace.endpos, clip.end );
645 VectorCopy( end, clip.end );
646 clip.mins = mins;
647 clip.maxs = maxs;
648 clip.passEntityNum = passEntityNum;
649 clip.capsule = capsule;
650
651 // create the bounding box of the entire move
652 // we can limit it to the part of the move not
653 // already clipped off by the world, which can be
654 // a significant savings for line of sight and shot traces
655 for ( i = 0 ; i < 3 ; i++ ) {
656 if ( end[i] > start[i] ) {
657 clip.boxmins[i] = clip.start[i] + clip.mins[i] - 1;
658 clip.boxmaxs[i] = clip.end[i] + clip.maxs[i] + 1;
659 } else {
660 clip.boxmins[i] = clip.end[i] + clip.mins[i] - 1;
661 clip.boxmaxs[i] = clip.start[i] + clip.maxs[i] + 1;
662 }
663 }
664
665 // clip to other solid entities
666 SV_ClipMoveToEntities( &clip );
667
668 *results = clip.trace;
669 }
670
671
672
673 /*
674 =============
675 SV_PointContents
676 =============
677 */
SV_PointContents(const vec3_t p,int passEntityNum)678 int SV_PointContents( const vec3_t p, int passEntityNum ) {
679 int touch[MAX_GENTITIES];
680 sharedEntity_t *hit;
681 int i, num;
682 int contents, c2;
683 clipHandle_t clipHandle;
684 float *angles;
685
686 // get base contents from world
687 contents = CM_PointContents( p, 0 );
688
689 // or in contents from all the other entities
690 num = SV_AreaEntities( p, p, touch, MAX_GENTITIES );
691
692 for ( i = 0 ; i < num ; i++ ) {
693 if ( touch[i] == passEntityNum ) {
694 continue;
695 }
696 hit = SV_GentityNum( touch[i] );
697 // might intersect, so do an exact clip
698 clipHandle = SV_ClipHandleForEntity( hit );
699 angles = hit->r.currentAngles;
700 if ( !hit->r.bmodel ) {
701 angles = vec3_origin; // boxes don't rotate
702 }
703
704 // RF, ignore this test if the origin is at the world origin
705 //if (!VectorCompare( hit->s.origin, vec3_origin )) {
706 c2 = CM_TransformedPointContents (p, clipHandle, hit->r.currentOrigin, angles);
707
708 contents |= c2;
709 //}
710 }
711
712 return contents;
713 }
714
715
716