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
ClearLink(link_t * l)64 void ClearLink (link_t *l)
65 {
66 l->prev = l->next = l;
67 }
68
RemoveLink(link_t * l)69 void RemoveLink (link_t *l)
70 {
71 l->next->prev = l->prev;
72 l->prev->next = l->next;
73 }
74
InsertLinkBefore(link_t * l,link_t * before)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 */
SV_CreateAreaNode(int depth,vec3_t mins,vec3_t maxs)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 */
SV_ClearWorld(void)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 */
SV_UnlinkEdict(edict_t * ent)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
SV_LinkEdict(edict_t * ent)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 */
SV_AreaEdicts_r(areanode_t * node)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 if(!l)
371 return;
372
373 next = l->next;
374 check = EDICT_FROM_AREA(l);
375
376 if (check->solid == SOLID_NOT)
377 continue; // deactivated
378 if (check->absmin[0] > area_maxs[0]
379 || check->absmin[1] > area_maxs[1]
380 || check->absmin[2] > area_maxs[2]
381 || check->absmax[0] < area_mins[0]
382 || check->absmax[1] < area_mins[1]
383 || check->absmax[2] < area_mins[2])
384 continue; // not touching
385
386 if (area_count == area_maxcount)
387 {
388 Com_Printf ("SV_AreaEdicts: MAXCOUNT\n");
389 return;
390 }
391
392 area_list[area_count] = check;
393 area_count++;
394 }
395
396 if (node->axis == -1)
397 return; // terminal node
398
399 // recurse down both sides
400 if ( area_maxs[node->axis] > node->dist )
401 SV_AreaEdicts_r ( node->children[0] );
402 if ( area_mins[node->axis] < node->dist )
403 SV_AreaEdicts_r ( node->children[1] );
404 }
405
406 /*
407 ================
408 SV_AreaEdicts
409 ================
410 */
SV_AreaEdicts(vec3_t mins,vec3_t maxs,edict_t ** list,int maxcount,int areatype)411 int SV_AreaEdicts (vec3_t mins, vec3_t maxs, edict_t **list,
412 int maxcount, int areatype)
413 {
414 area_mins = mins;
415 area_maxs = maxs;
416 area_list = list;
417 area_count = 0;
418 area_maxcount = maxcount;
419 area_type = areatype;
420
421 SV_AreaEdicts_r (sv_areanodes);
422
423 return area_count;
424 }
425
426
427 //===========================================================================
428
429 /*
430 =============
431 SV_PointContents
432 =============
433 */
SV_PointContents(vec3_t p)434 int SV_PointContents (vec3_t p)
435 {
436 edict_t *touch[MAX_EDICTS], *hit;
437 int i, num;
438 int contents, c2;
439 int headnode;
440 float *angles;
441
442 // get base contents from world
443 contents = CM_PointContents (p, sv.models[1]->headnode);
444
445 // or in contents from all the other entities
446 num = SV_AreaEdicts (p, p, touch, MAX_EDICTS, AREA_SOLID);
447
448 for (i=0 ; i<num ; i++)
449 {
450 hit = touch[i];
451
452 // might intersect, so do an exact clip
453 headnode = SV_HullForEntity (hit);
454 angles = hit->s.angles;
455 if (hit->solid != SOLID_BSP)
456 angles = vec3_origin; // boxes don't rotate
457
458 c2 = CM_TransformedPointContents (p, headnode, hit->s.origin, hit->s.angles);
459
460 contents |= c2;
461 }
462
463 return contents;
464 }
465
466
467
468 typedef struct
469 {
470 vec3_t boxmins, boxmaxs;// enclose the test object along entire move
471 float *mins, *maxs; // size of the moving object
472 vec3_t mins2, maxs2; // size when clipping against mosnters
473 float *start, *end;
474 trace_t trace;
475 edict_t *passedict;
476 int contentmask;
477 } moveclip_t;
478
479
480
481 /*
482 ================
483 SV_HullForEntity
484
485 Returns a headnode that can be used for testing or clipping an
486 object of mins/maxs size.
487 Offset is filled in to contain the adjustment that must be added to the
488 testing object's origin to get a point to use with the returned hull.
489 ================
490 */
SV_HullForEntity(edict_t * ent)491 int SV_HullForEntity (edict_t *ent)
492 {
493 cmodel_t *model;
494
495 // decide which clipping hull to use, based on the size
496 if (ent->solid == SOLID_BSP)
497 { // explicit hulls in the BSP model
498 model = sv.models[ ent->s.modelindex ];
499
500 if (!model)
501 Com_Error (ERR_FATAL, "MOVETYPE_PUSH with a non bsp model");
502
503 return model->headnode;
504 }
505
506 // create a temp hull from bounding box sizes
507
508 return CM_HeadnodeForBox (ent->mins, ent->maxs);
509 }
510
511
512 //===========================================================================
513
514 /*
515 ====================
516 SV_ClipMoveToEntities
517
518 ====================
519 */
SV_ClipMoveToEntities(moveclip_t * clip)520 void SV_ClipMoveToEntities ( moveclip_t *clip )
521 {
522 int i, num;
523 edict_t *touchlist[MAX_EDICTS], *touch;
524 trace_t trace;
525 int headnode;
526 float *angles;
527
528 num = SV_AreaEdicts (clip->boxmins, clip->boxmaxs, touchlist
529 , MAX_EDICTS, AREA_SOLID);
530
531 // be careful, it is possible to have an entity in this
532 // list removed before we get to it (killtriggered)
533 for (i=0 ; i<num ; i++)
534 {
535 touch = touchlist[i];
536 if (touch->solid == SOLID_NOT)
537 continue;
538 if (touch == clip->passedict)
539 continue;
540 if (clip->trace.allsolid)
541 return;
542 if (clip->passedict)
543 {
544 if (touch->owner == clip->passedict)
545 continue; // don't clip against own missiles
546 if (clip->passedict->owner == touch)
547 continue; // don't clip against owner
548 }
549
550 if ( !(clip->contentmask & CONTENTS_DEADMONSTER)
551 && (touch->svflags & SVF_DEADMONSTER) )
552 continue;
553
554 // might intersect, so do an exact clip
555 headnode = SV_HullForEntity (touch);
556 angles = touch->s.angles;
557 if (touch->solid != SOLID_BSP)
558 angles = vec3_origin; // boxes don't rotate
559
560 if (touch->svflags & SVF_MONSTER)
561 trace = CM_TransformedBoxTrace (clip->start, clip->end,
562 clip->mins2, clip->maxs2, headnode, clip->contentmask,
563 touch->s.origin, angles);
564 else
565 trace = CM_TransformedBoxTrace (clip->start, clip->end,
566 clip->mins, clip->maxs, headnode, clip->contentmask,
567 touch->s.origin, angles);
568
569 if (trace.allsolid || trace.startsolid ||
570 trace.fraction < clip->trace.fraction)
571 {
572 trace.ent = touch;
573 if (clip->trace.startsolid)
574 {
575 clip->trace = trace;
576 clip->trace.startsolid = true;
577 }
578 else
579 clip->trace = trace;
580 }
581 else if (trace.startsolid)
582 clip->trace.startsolid = true;
583 }
584 }
585
586
587 /*
588 ==================
589 SV_TraceBounds
590 ==================
591 */
SV_TraceBounds(vec3_t start,vec3_t mins,vec3_t maxs,vec3_t end,vec3_t boxmins,vec3_t boxmaxs)592 void SV_TraceBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
593 {
594 int i;
595
596 for (i=0 ; i<3 ; i++)
597 {
598 if (end[i] > start[i])
599 {
600 boxmins[i] = start[i] + mins[i] - 1;
601 boxmaxs[i] = end[i] + maxs[i] + 1;
602 }
603 else
604 {
605 boxmins[i] = end[i] + mins[i] - 1;
606 boxmaxs[i] = start[i] + maxs[i] + 1;
607 }
608 }
609 }
610
611 /*
612 ==================
613 SV_Trace
614
615 Moves the given mins/maxs volume through the world from start to end.
616
617 Passedict and edicts owned by passedict are explicitly not checked.
618
619 ==================
620 */
SV_Trace(vec3_t start,vec3_t mins,vec3_t maxs,vec3_t end,edict_t * passedict,int contentmask)621 trace_t SV_Trace (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, edict_t *passedict, int contentmask)
622 {
623 moveclip_t clip;
624
625 if (!mins)
626 mins = vec3_origin;
627 if (!maxs)
628 maxs = vec3_origin;
629
630 memset ( &clip, 0, sizeof ( moveclip_t ) );
631
632 // clip to world
633 clip.trace = CM_BoxTrace (start, end, mins, maxs, 0, contentmask);
634 clip.trace.ent = ge->edicts;
635 if (clip.trace.fraction == 0)
636 return clip.trace; // blocked by the world
637
638 clip.contentmask = contentmask;
639 clip.start = start;
640 clip.end = end;
641 clip.mins = mins;
642 clip.maxs = maxs;
643 clip.passedict = passedict;
644
645 VectorCopy (mins, clip.mins2);
646 VectorCopy (maxs, clip.maxs2);
647
648 // create the bounding box of the entire move
649 SV_TraceBounds ( start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs );
650
651 // clip to other solid entities
652 SV_ClipMoveToEntities ( &clip );
653
654 return clip.trace;
655 }
656 /*
657 trace_t SV_Trace_2(vec3_t start, vec3_t end, float size, int contentmask)
658 {
659 vec3_t maxs, mins;
660
661 VectorSet(maxs, size, size, size);
662 VectorSet(mins, -size, -size, -size);
663
664 return CM_BoxTrace(start, end, mins, maxs, 0, contentmask);
665 }
666 */
667 /*
668 ==================
669 SV_Trace_Old
670
671 HACK: different compilers (and even different versions
672 of the same compiler) handle returning of structures differently.
673
674 This function is intended to be binary-compatible with
675 game DLLs built by earlier versions of GCC.
676
677 Game DLLs built by MSVC seems to behave similary to old GCC
678 (except they additionaly require pointer to destination
679 structure to be retured in EAX register), so this function is linked in
680 when building with MinGW, under assumption that no mods built with MinGW ever exist.
681 ==================
682 */
SV_Trace_OldGCC(trace_t * trace,vec3_t start,vec3_t mins,vec3_t maxs,vec3_t end,edict_t * passedict,int contentmask)683 trace_t *SV_Trace_OldGCC (trace_t *trace, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, edict_t *passedict, int contentmask)
684 {
685 moveclip_t clip;
686
687 if (!mins)
688 mins = vec3_origin;
689 if (!maxs)
690 maxs = vec3_origin;
691
692 memset ( &clip, 0, sizeof ( moveclip_t ) );
693
694 // clip to world
695 clip.trace = CM_BoxTrace (start, end, mins, maxs, 0, contentmask);
696 clip.trace.ent = ge->edicts;
697 if (clip.trace.fraction == 0) {
698 *trace = clip.trace;
699 return trace; // blocked by the world
700 }
701
702 clip.contentmask = contentmask;
703 clip.start = start;
704 clip.end = end;
705 clip.mins = mins;
706 clip.maxs = maxs;
707 clip.passedict = passedict;
708
709 VectorCopy (mins, clip.mins2);
710 VectorCopy (maxs, clip.maxs2);
711
712 // create the bounding box of the entire move
713 SV_TraceBounds ( start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs );
714
715 // clip to other solid entities
716 SV_ClipMoveToEntities ( &clip );
717
718 *trace = clip.trace;
719
720 return trace;
721
722 }
723
724
725
726