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