1 /*
2 ===========================================================================
3
4 Return to Castle Wolfenstein multiplayer 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 multiplayer GPL Source Code (RTCW MP Source Code).
8
9 RTCW MP 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 MP 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 MP Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the RTCW MP 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 MP 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
SV_LinkEntity(sharedEntity_t * gEnt)212 void SV_LinkEntity( sharedEntity_t *gEnt ) {
213 worldSector_t *node;
214 int leafs[MAX_TOTAL_ENT_LEAFS];
215 int cluster;
216 int num_leafs;
217 int i, j, k;
218 int area;
219 int lastLeaf;
220 float *origin, *angles;
221 svEntity_t *ent;
222
223 ent = SV_SvEntityForGentity( gEnt );
224
225 // Ridah, sanity check for possible currentOrigin being reset bug
226 if ( !gEnt->r.bmodel && VectorCompare( gEnt->r.currentOrigin, vec3_origin ) ) {
227 Com_DPrintf( "WARNING: BBOX entity is being linked at world origin, this is probably a bug\n" );
228 }
229
230 if ( ent->worldSector ) {
231 SV_UnlinkEntity( gEnt ); // unlink from old position
232 }
233
234 // encode the size into the entityState_t for client prediction
235 if ( gEnt->r.bmodel ) {
236 gEnt->s.solid = SOLID_BMODEL; // a solid_box will never create this value
237 } else if ( gEnt->r.contents & ( CONTENTS_SOLID | CONTENTS_BODY ) ) {
238 // assume that x/y are equal and symetric
239 i = gEnt->r.maxs[0];
240 if ( i < 1 ) {
241 i = 1;
242 }
243 if ( i > 255 ) {
244 i = 255;
245 }
246
247 // z is not symetric
248 j = ( -gEnt->r.mins[2] );
249 if ( j < 1 ) {
250 j = 1;
251 }
252 if ( j > 255 ) {
253 j = 255;
254 }
255
256 // and z maxs can be negative...
257 k = ( gEnt->r.maxs[2] + 32 );
258 if ( k < 1 ) {
259 k = 1;
260 }
261 if ( k > 255 ) {
262 k = 255;
263 }
264
265 gEnt->s.solid = ( k << 16 ) | ( j << 8 ) | i;
266 } else {
267 gEnt->s.solid = 0;
268 }
269
270 // get the position
271 origin = gEnt->r.currentOrigin;
272 angles = gEnt->r.currentAngles;
273
274 // set the abs box
275 if ( gEnt->r.bmodel && ( angles[0] || angles[1] || angles[2] ) ) {
276 // expand for rotation
277 float max;
278
279 max = RadiusFromBounds( gEnt->r.mins, gEnt->r.maxs );
280 for ( i = 0 ; i < 3 ; i++ ) {
281 gEnt->r.absmin[i] = origin[i] - max;
282 gEnt->r.absmax[i] = origin[i] + max;
283 }
284 } else {
285 // normal
286 VectorAdd( origin, gEnt->r.mins, gEnt->r.absmin );
287 VectorAdd( origin, gEnt->r.maxs, gEnt->r.absmax );
288 }
289
290 // because movement is clipped an epsilon away from an actual edge,
291 // we must fully check even when bounding boxes don't quite touch
292 gEnt->r.absmin[0] -= 1;
293 gEnt->r.absmin[1] -= 1;
294 gEnt->r.absmin[2] -= 1;
295 gEnt->r.absmax[0] += 1;
296 gEnt->r.absmax[1] += 1;
297 gEnt->r.absmax[2] += 1;
298
299 // link to PVS leafs
300 ent->numClusters = 0;
301 ent->lastCluster = 0;
302 ent->areanum = -1;
303 ent->areanum2 = -1;
304
305 //get all leafs, including solids
306 num_leafs = CM_BoxLeafnums( gEnt->r.absmin, gEnt->r.absmax,
307 leafs, MAX_TOTAL_ENT_LEAFS, &lastLeaf );
308
309 // if none of the leafs were inside the map, the
310 // entity is outside the world and can be considered unlinked
311 if ( !num_leafs ) {
312 return;
313 }
314
315 // set areas, even from clusters that don't fit in the entity array
316 for ( i = 0 ; i < num_leafs ; i++ ) {
317 area = CM_LeafArea( leafs[i] );
318 if ( area != -1 ) {
319 // doors may legally straggle two areas,
320 // but nothing should evern need more than that
321 if ( ent->areanum != -1 && ent->areanum != area ) {
322 if ( ent->areanum2 != -1 && ent->areanum2 != area && sv.state == SS_LOADING ) {
323 Com_DPrintf( "Object %i touching 3 areas at %f %f %f\n",
324 gEnt->s.number,
325 gEnt->r.absmin[0], gEnt->r.absmin[1], gEnt->r.absmin[2] );
326 }
327 ent->areanum2 = area;
328 } else {
329 ent->areanum = area;
330 }
331 }
332 }
333
334 // store as many explicit clusters as we can
335 ent->numClusters = 0;
336 for ( i = 0 ; i < num_leafs ; i++ ) {
337 cluster = CM_LeafCluster( leafs[i] );
338 if ( cluster != -1 ) {
339 ent->clusternums[ent->numClusters++] = cluster;
340 if ( ent->numClusters == MAX_ENT_CLUSTERS ) {
341 break;
342 }
343 }
344 }
345
346 // store off a last cluster if we need to
347 if ( i != num_leafs ) {
348 ent->lastCluster = CM_LeafCluster( lastLeaf );
349 }
350
351 gEnt->r.linkcount++;
352
353 // find the first world sector node that the ent's box crosses
354 node = sv_worldSectors;
355 while ( 1 )
356 {
357 if ( node->axis == -1 ) {
358 break;
359 }
360 if ( gEnt->r.absmin[node->axis] > node->dist ) {
361 node = node->children[0];
362 } else if ( gEnt->r.absmax[node->axis] < node->dist ) {
363 node = node->children[1];
364 } else {
365 break; // crosses the node
366 }
367 }
368
369 // link it in
370 ent->worldSector = node;
371 ent->nextEntityInWorldSector = node->entities;
372 node->entities = ent;
373
374 gEnt->r.linked = qtrue;
375 }
376
377 /*
378 ============================================================================
379
380 AREA QUERY
381
382 Fills in a list of all entities who's absmin / absmax intersects the given
383 bounds. This does NOT mean that they actually touch in the case of bmodels.
384 ============================================================================
385 */
386
387 typedef struct {
388 const float *mins;
389 const float *maxs;
390 int *list;
391 int count, maxcount;
392 } areaParms_t;
393
394
395 /*
396 ====================
397 SV_AreaEntities_r
398
399 ====================
400 */
SV_AreaEntities_r(worldSector_t * node,areaParms_t * ap)401 static void SV_AreaEntities_r( worldSector_t *node, areaParms_t *ap ) {
402 svEntity_t *check, *next;
403 sharedEntity_t *gcheck;
404
405 for ( check = node->entities ; check ; check = next ) {
406 next = check->nextEntityInWorldSector;
407
408 gcheck = SV_GEntityForSvEntity( check );
409
410 if ( gcheck->r.absmin[0] > ap->maxs[0]
411 || gcheck->r.absmin[1] > ap->maxs[1]
412 || gcheck->r.absmin[2] > ap->maxs[2]
413 || gcheck->r.absmax[0] < ap->mins[0]
414 || gcheck->r.absmax[1] < ap->mins[1]
415 || gcheck->r.absmax[2] < ap->mins[2] ) {
416 continue;
417 }
418
419 if ( ap->count == ap->maxcount ) {
420 Com_Printf( "SV_AreaEntities: MAXCOUNT\n" );
421 return;
422 }
423
424 ap->list[ap->count] = check - sv.svEntities;
425 ap->count++;
426 }
427
428 if ( node->axis == -1 ) {
429 return; // terminal node
430 }
431
432 // recurse down both sides
433 if ( ap->maxs[node->axis] > node->dist ) {
434 SV_AreaEntities_r( node->children[0], ap );
435 }
436 if ( ap->mins[node->axis] < node->dist ) {
437 SV_AreaEntities_r( node->children[1], ap );
438 }
439 }
440
441 /*
442 ================
443 SV_AreaEntities
444 ================
445 */
SV_AreaEntities(const vec3_t mins,const vec3_t maxs,int * entityList,int maxcount)446 int SV_AreaEntities( const vec3_t mins, const vec3_t maxs, int *entityList, int maxcount ) {
447 areaParms_t ap;
448
449 ap.mins = mins;
450 ap.maxs = maxs;
451 ap.list = entityList;
452 ap.count = 0;
453 ap.maxcount = maxcount;
454
455 SV_AreaEntities_r( sv_worldSectors, &ap );
456
457 return ap.count;
458 }
459
460
461
462 //===========================================================================
463
464
465 typedef struct {
466 vec3_t boxmins, boxmaxs; // enclose the test object along entire move
467 const float *mins;
468 const float *maxs; // size of the moving object
469 const float *start;
470 vec3_t end;
471 trace_t trace;
472 int passEntityNum;
473 int contentmask;
474 int capsule;
475 } moveclip_t;
476
477
478 /*
479 ====================
480 SV_ClipToEntity
481
482 ====================
483 */
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)484 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 ) {
485 sharedEntity_t *touch;
486 clipHandle_t clipHandle;
487 float *origin, *angles;
488
489 touch = SV_GentityNum( entityNum );
490
491 memset( trace, 0, sizeof( trace_t ) );
492
493 // if it doesn't have any brushes of a type we
494 // are looking for, ignore it
495 if ( !( contentmask & touch->r.contents ) ) {
496 trace->fraction = 1.0;
497 return;
498 }
499
500 // might intersect, so do an exact clip
501 clipHandle = SV_ClipHandleForEntity( touch );
502
503 origin = touch->r.currentOrigin;
504 angles = touch->r.currentAngles;
505
506 if ( !touch->r.bmodel ) {
507 angles = vec3_origin; // boxes don't rotate
508 }
509
510 CM_TransformedBoxTrace( trace, start, end,
511 mins, maxs, clipHandle, contentmask,
512 origin, angles, capsule );
513 if ( trace->fraction < 1 ) {
514 trace->entityNum = touch->s.number;
515 }
516 }
517
518
519 // FIXME: Copied from cm_local.h
520 #define BOX_MODEL_HANDLE 511
521
522 /*
523 ====================
524 SV_ClipMoveToEntities
525
526 ====================
527 */
SV_ClipMoveToEntities(moveclip_t * clip)528 static void SV_ClipMoveToEntities( moveclip_t *clip ) {
529 int i, num;
530 int touchlist[MAX_GENTITIES];
531 sharedEntity_t *touch;
532 int passOwnerNum;
533 trace_t trace;
534 clipHandle_t clipHandle;
535 float *origin, *angles;
536
537 num = SV_AreaEntities( clip->boxmins, clip->boxmaxs, touchlist, MAX_GENTITIES );
538
539 if ( clip->passEntityNum != ENTITYNUM_NONE ) {
540 passOwnerNum = ( SV_GentityNum( clip->passEntityNum ) )->r.ownerNum;
541 if ( passOwnerNum == ENTITYNUM_NONE ) {
542 passOwnerNum = -1;
543 }
544 } else {
545 passOwnerNum = -1;
546 }
547
548 for ( i = 0 ; i < num ; i++ ) {
549 if ( clip->trace.allsolid ) {
550 return;
551 }
552 touch = SV_GentityNum( touchlist[i] );
553
554 // see if we should ignore this entity
555 if ( clip->passEntityNum != ENTITYNUM_NONE ) {
556 if ( touchlist[i] == clip->passEntityNum ) {
557 continue; // don't clip against the pass entity
558 }
559 if ( touch->r.ownerNum == clip->passEntityNum ) {
560 continue; // don't clip against own missiles
561 }
562 if ( touch->r.ownerNum == passOwnerNum ) {
563 continue; // don't clip against other missiles from our owner
564 }
565 }
566
567 // if it doesn't have any brushes of a type we
568 // are looking for, ignore it
569 if ( !( clip->contentmask & touch->r.contents ) ) {
570 continue;
571 }
572
573 // might intersect, so do an exact clip
574 clipHandle = SV_ClipHandleForEntity( touch );
575
576 // DHM - Nerve :: If clipping against BBOX, set to correct contents
577 if ( clipHandle == BOX_MODEL_HANDLE ) {
578 CM_SetTempBoxModelContents( touch->r.contents );
579 }
580
581 origin = touch->r.currentOrigin;
582 angles = touch->r.currentAngles;
583
584
585 if ( !touch->r.bmodel ) {
586 angles = vec3_origin; // boxes don't rotate
587 }
588
589 CM_TransformedBoxTrace( &trace, clip->start, clip->end,
590 clip->mins, clip->maxs, clipHandle, clip->contentmask,
591 origin, angles, clip->capsule );
592 if ( trace.allsolid ) {
593 clip->trace.allsolid = qtrue;
594 trace.entityNum = touch->s.number;
595 } else if ( trace.startsolid ) {
596 clip->trace.startsolid = qtrue;
597 trace.entityNum = touch->s.number;
598 }
599
600 if ( trace.fraction < clip->trace.fraction ) {
601 qboolean oldStart;
602
603 // make sure we keep a startsolid from a previous trace
604 oldStart = clip->trace.startsolid;
605
606 trace.entityNum = touch->s.number;
607 clip->trace = trace;
608 clip->trace.startsolid |= oldStart;
609 }
610
611 // DHM - Nerve :: Reset contents to default
612 if ( clipHandle == BOX_MODEL_HANDLE ) {
613 CM_SetTempBoxModelContents( CONTENTS_BODY );
614 }
615 }
616 }
617
618
619 /*
620 ==================
621 SV_Trace
622
623 Moves the given mins/maxs volume through the world from start to end.
624 passEntityNum and entities owned by passEntityNum are explicitly not checked.
625 ==================
626 */
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)627 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 ) {
628 moveclip_t clip;
629 int i;
630
631 if ( !mins ) {
632 mins = vec3_origin;
633 }
634 if ( !maxs ) {
635 maxs = vec3_origin;
636 }
637
638 memset( &clip, 0, sizeof( moveclip_t ) );
639
640 // clip to world
641 CM_BoxTrace( &clip.trace, start, end, mins, maxs, 0, contentmask, capsule );
642 clip.trace.entityNum = clip.trace.fraction != 1.0 ? ENTITYNUM_WORLD : ENTITYNUM_NONE;
643 if ( clip.trace.fraction == 0 ) {
644 *results = clip.trace;
645 return; // blocked immediately by the world
646 }
647
648 clip.contentmask = contentmask;
649 clip.start = start;
650 // VectorCopy( clip.trace.endpos, clip.end );
651 VectorCopy( end, clip.end );
652 clip.mins = mins;
653 clip.maxs = maxs;
654 clip.passEntityNum = passEntityNum;
655 clip.capsule = capsule;
656
657 // create the bounding box of the entire move
658 // we can limit it to the part of the move not
659 // already clipped off by the world, which can be
660 // a significant savings for line of sight and shot traces
661 for ( i = 0 ; i < 3 ; i++ ) {
662 if ( end[i] > start[i] ) {
663 clip.boxmins[i] = clip.start[i] + clip.mins[i] - 1;
664 clip.boxmaxs[i] = clip.end[i] + clip.maxs[i] + 1;
665 } else {
666 clip.boxmins[i] = clip.end[i] + clip.mins[i] - 1;
667 clip.boxmaxs[i] = clip.start[i] + clip.maxs[i] + 1;
668 }
669 }
670
671 // clip to other solid entities
672 SV_ClipMoveToEntities( &clip );
673
674 *results = clip.trace;
675 }
676
677
678
679 /*
680 =============
681 SV_PointContents
682 =============
683 */
SV_PointContents(const vec3_t p,int passEntityNum)684 int SV_PointContents( const vec3_t p, int passEntityNum ) {
685 int touch[MAX_GENTITIES];
686 sharedEntity_t *hit;
687 int i, num;
688 int contents, c2;
689 clipHandle_t clipHandle;
690 float *angles;
691
692 // get base contents from world
693 contents = CM_PointContents( p, 0 );
694
695 // or in contents from all the other entities
696 num = SV_AreaEntities( p, p, touch, MAX_GENTITIES );
697
698 for ( i = 0 ; i < num ; i++ ) {
699 if ( touch[i] == passEntityNum ) {
700 continue;
701 }
702 hit = SV_GentityNum( touch[i] );
703 // might intersect, so do an exact clip
704 clipHandle = SV_ClipHandleForEntity( hit );
705 angles = hit->r.currentAngles;
706 if ( !hit->r.bmodel ) {
707 angles = vec3_origin; // boxes don't rotate
708 }
709
710 c2 = CM_TransformedPointContents (p, clipHandle, hit->r.currentOrigin, angles);
711
712 contents |= c2;
713 }
714
715 return contents;
716 }
717
718
719