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 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 */
SV_AreaEdicts(vec3_t mins,vec3_t maxs,edict_t ** list,int maxcount,int areatype)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 */
SV_PointContents(vec3_t p)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 */
SV_HullForEntity(edict_t * ent)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 */
SV_ClipMoveToEntities(moveclip_t * clip)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 */
SV_TraceBounds(vec3_t start,vec3_t mins,vec3_t maxs,vec3_t end,vec3_t boxmins,vec3_t boxmaxs)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 */
SV_Trace(vec3_t start,vec3_t mins,vec3_t maxs,vec3_t end,edict_t * passedict,int contentmask)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
660