SV_PointContents removed (all calls replaced with Mod_PointInLeaf, which is faster)
[divverent/darkplaces.git] / world.c
1 /*
2 Copyright (C) 1996-1997 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 "quakedef.h"
23
24 /*
25
26 entities never clip against themselves, or their owner
27
28 line of sight checks trace->crosscontent, but bullets don't
29
30 */
31
32
33 void ClearLink (link_t *l);
34 void RemoveLink (link_t *l);
35 void InsertLinkBefore (link_t *l, link_t *before);
36 void InsertLinkAfter (link_t *l, link_t *after);
37
38 #define EDICT_FROM_AREA(l) ((edict_t *)((qbyte *)l - (int)&(((edict_t *)0)->area)))
39
40 //============================================================================
41
42 // ClearLink is used for new headnodes
43 void ClearLink (link_t *l)
44 {
45         l->prev = l->next = l;
46 }
47
48 void RemoveLink (link_t *l)
49 {
50         l->next->prev = l->prev;
51         l->prev->next = l->next;
52 }
53
54 void InsertLinkBefore (link_t *l, link_t *before)
55 {
56         l->next = before;
57         l->prev = before->prev;
58         l->prev->next = l;
59         l->next->prev = l;
60 }
61 void InsertLinkAfter (link_t *l, link_t *after)
62 {
63         l->next = after->next;
64         l->prev = after;
65         l->prev->next = l;
66         l->next->prev = l;
67 }
68
69
70 typedef struct
71 {
72         // bounding box of entire move area
73         vec3_t          boxmins, boxmaxs;
74
75         // size of the moving object
76         vec3_t          mins, maxs;
77
78         // size when clipping against monsters
79         vec3_t          mins2, maxs2;
80
81         // size when clipping against brush models
82         vec3_t          hullmins, hullmaxs;
83
84         // start and end origin of move
85         vec3_t          start, end;
86
87         // trace results
88         trace_t         trace;
89
90         // type of move (like ignoring monsters, or similar)
91         int                     type;
92
93         // the edict that is moving (if any)
94         edict_t         *passedict;
95 }
96 moveclip_t;
97
98
99 /*
100 ===============================================================================
101
102 ENTITY AREA CHECKING
103
104 ===============================================================================
105 */
106
107 typedef struct areanode_s
108 {
109         int             axis;           // -1 = leaf node
110         float   dist;
111         struct areanode_s       *children[2];
112         link_t  trigger_edicts;
113         link_t  solid_edicts;
114 } areanode_t;
115
116 #define AREA_DEPTH      4
117 #define AREA_NODES      32
118
119 static  areanode_t      sv_areanodes[AREA_NODES];
120 static  int                     sv_numareanodes;
121
122 /*
123 ===============
124 SV_CreateAreaNode
125
126 ===============
127 */
128 areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
129 {
130         areanode_t      *anode;
131         vec3_t          size;
132         vec3_t          mins1, maxs1, mins2, maxs2;
133
134         anode = &sv_areanodes[sv_numareanodes];
135         sv_numareanodes++;
136
137         ClearLink (&anode->trigger_edicts);
138         ClearLink (&anode->solid_edicts);
139
140         if (depth == AREA_DEPTH)
141         {
142                 anode->axis = -1;
143                 anode->children[0] = anode->children[1] = NULL;
144                 return anode;
145         }
146
147         VectorSubtract (maxs, mins, size);
148         if (size[0] > size[1])
149                 anode->axis = 0;
150         else
151                 anode->axis = 1;
152
153         anode->dist = 0.5 * (maxs[anode->axis] + mins[anode->axis]);
154         VectorCopy (mins, mins1);
155         VectorCopy (mins, mins2);
156         VectorCopy (maxs, maxs1);
157         VectorCopy (maxs, maxs2);
158
159         maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
160
161         anode->children[0] = SV_CreateAreaNode (depth+1, mins2, maxs2);
162         anode->children[1] = SV_CreateAreaNode (depth+1, mins1, maxs1);
163
164         return anode;
165 }
166
167 /*
168 ===============
169 SV_ClearWorld
170
171 ===============
172 */
173 void SV_ClearWorld (void)
174 {
175         Collision_Init ();
176
177         memset (sv_areanodes, 0, sizeof(sv_areanodes));
178         sv_numareanodes = 0;
179         Mod_CheckLoaded(sv.worldmodel);
180         SV_CreateAreaNode (0, sv.worldmodel->normalmins, sv.worldmodel->normalmaxs);
181 }
182
183
184 /*
185 ===============
186 SV_UnlinkEdict
187
188 ===============
189 */
190 void SV_UnlinkEdict (edict_t *ent)
191 {
192         if (!ent->area.prev)
193                 return;         // not linked in anywhere
194         RemoveLink (&ent->area);
195         ent->area.prev = ent->area.next = NULL;
196 }
197
198
199 /*
200 ====================
201 SV_TouchLinks
202 ====================
203 */
204 void SV_TouchLinks ( edict_t *ent, areanode_t *node )
205 {
206         link_t          *l, *next;
207         edict_t         *touch;
208         int                     old_self, old_other;
209
210 loc0:
211 // touch linked edicts
212         for (l = node->trigger_edicts.next ; l != &node->trigger_edicts ; l = next)
213         {
214                 next = l->next;
215                 touch = EDICT_FROM_AREA(l);
216                 if (touch == ent)
217                         continue;
218                 if (!touch->v.touch || touch->v.solid != SOLID_TRIGGER)
219                         continue;
220                 if (ent->v.absmin[0] > touch->v.absmax[0]
221                  || ent->v.absmin[1] > touch->v.absmax[1]
222                  || ent->v.absmin[2] > touch->v.absmax[2]
223                  || ent->v.absmax[0] < touch->v.absmin[0]
224                  || ent->v.absmax[1] < touch->v.absmin[1]
225                  || ent->v.absmax[2] < touch->v.absmin[2])
226                         continue;
227                 old_self = pr_global_struct->self;
228                 old_other = pr_global_struct->other;
229
230                 pr_global_struct->self = EDICT_TO_PROG(touch);
231                 pr_global_struct->other = EDICT_TO_PROG(ent);
232                 pr_global_struct->time = sv.time;
233                 PR_ExecuteProgram (touch->v.touch, "");
234
235                 pr_global_struct->self = old_self;
236                 pr_global_struct->other = old_other;
237         }
238
239 // recurse down both sides
240         if (node->axis == -1)
241                 return;
242
243         if (ent->v.absmax[node->axis] > node->dist)
244         {
245                 if (ent->v.absmin[node->axis] < node->dist)
246                         SV_TouchLinks(ent, node->children[1]); // order reversed to reduce code
247                 node = node->children[0];
248                 goto loc0;
249         }
250         else
251         {
252                 if (ent->v.absmin[node->axis] < node->dist)
253                 {
254                         node = node->children[1];
255                         goto loc0;
256                 }
257         }
258 }
259
260
261 /*
262 ===============
263 SV_LinkEdict
264
265 ===============
266 */
267 void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
268 {
269         model_t         *model;
270         areanode_t      *node;
271
272         if (ent->area.prev)
273                 SV_UnlinkEdict (ent);   // unlink from old position
274
275         if (ent == sv.edicts)
276                 return;         // don't add the world
277
278         if (ent->free)
279                 return;
280
281 // set the abs box
282
283         if (ent->v.solid == SOLID_BSP)
284         {
285                 if (ent->v.modelindex < 0 || ent->v.modelindex > MAX_MODELS)
286                         PR_RunError("SOLID_BSP with invalid modelindex!\n");
287                 model = sv.models[(int) ent->v.modelindex];
288                 if (model != NULL)
289                 {
290                         if (model->type != mod_brush)
291                                 PR_RunError("SOLID_BSP with non-BSP model\n");
292
293                         if (ent->v.angles[0] || ent->v.angles[2] || ent->v.avelocity[0] || ent->v.avelocity[2])
294                         {
295                                 VectorAdd(ent->v.origin, model->rotatedmins, ent->v.absmin);
296                                 VectorAdd(ent->v.origin, model->rotatedmaxs, ent->v.absmax);
297                         }
298                         else if (ent->v.angles[1] || ent->v.avelocity[1])
299                         {
300                                 VectorAdd(ent->v.origin, model->yawmins, ent->v.absmin);
301                                 VectorAdd(ent->v.origin, model->yawmaxs, ent->v.absmax);
302                         }
303                         else
304                         {
305                                 VectorAdd(ent->v.origin, model->normalmins, ent->v.absmin);
306                                 VectorAdd(ent->v.origin, model->normalmaxs, ent->v.absmax);
307                         }
308                 }
309                 else
310                 {
311                         // SOLID_BSP with no model is valid, mainly because some QC setup code does so temporarily
312                         VectorAdd (ent->v.origin, ent->v.mins, ent->v.absmin);
313                         VectorAdd (ent->v.origin, ent->v.maxs, ent->v.absmax);
314                 }
315         }
316         else
317         {
318                 VectorAdd (ent->v.origin, ent->v.mins, ent->v.absmin);
319                 VectorAdd (ent->v.origin, ent->v.maxs, ent->v.absmax);
320         }
321
322 //
323 // to make items easier to pick up and allow them to be grabbed off
324 // of shelves, the abs sizes are expanded
325 //
326         if ((int)ent->v.flags & FL_ITEM)
327         {
328                 ent->v.absmin[0] -= 15;
329                 ent->v.absmin[1] -= 15;
330                 ent->v.absmin[2] -= 1;
331                 ent->v.absmax[0] += 15;
332                 ent->v.absmax[1] += 15;
333                 ent->v.absmax[2] += 1;
334         }
335         else
336         {
337                 // because movement is clipped an epsilon away from an actual edge,
338                 // we must fully check even when bounding boxes don't quite touch
339                 ent->v.absmin[0] -= 1;
340                 ent->v.absmin[1] -= 1;
341                 ent->v.absmin[2] -= 1;
342                 ent->v.absmax[0] += 1;
343                 ent->v.absmax[1] += 1;
344                 ent->v.absmax[2] += 1;
345         }
346
347         if (ent->v.solid == SOLID_NOT)
348                 return;
349
350 // find the first node that the ent's box crosses
351         node = sv_areanodes;
352         while (1)
353         {
354                 if (node->axis == -1)
355                         break;
356                 if (ent->v.absmin[node->axis] > node->dist)
357                         node = node->children[0];
358                 else if (ent->v.absmax[node->axis] < node->dist)
359                         node = node->children[1];
360                 else
361                         break;          // crosses the node
362         }
363
364 // link it in
365
366         if (ent->v.solid == SOLID_TRIGGER)
367                 InsertLinkBefore (&ent->area, &node->trigger_edicts);
368         else
369                 InsertLinkBefore (&ent->area, &node->solid_edicts);
370
371 // if touch_triggers, touch all entities at this node and descend for more
372         if (touch_triggers)
373                 SV_TouchLinks ( ent, sv_areanodes );
374 }
375
376
377
378 /*
379 ===============================================================================
380
381 POINT TESTING IN HULLS
382
383 ===============================================================================
384 */
385
386 /*
387 ============
388 SV_TestEntityPosition
389
390 This could be a lot more efficient...
391 ============
392 */
393 int SV_TestEntityPosition (edict_t *ent)
394 {
395         return SV_Move (ent->v.origin, ent->v.mins, ent->v.maxs, ent->v.origin, MOVE_NORMAL, ent).startsolid;
396 }
397
398
399 /*
400 ===============================================================================
401
402 LINE TESTING IN HULLS
403
404 ===============================================================================
405 */
406
407 /*
408 ==================
409 SV_ClipMoveToEntity
410
411 Handles selection or creation of a clipping hull, and offseting (and
412 eventually rotation) of the end points
413 ==================
414 */
415 trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end)
416 {
417         int i;
418         trace_t trace;
419         model_t *model;
420
421         i = ent->v.modelindex;
422         if ((unsigned int) i >= MAX_MODELS)
423                 PR_RunError("SV_ClipMoveToEntity: invalid modelindex\n");
424         model = sv.models[i];
425         if (i != 0 && model == NULL)
426                 PR_RunError("SV_ClipMoveToEntity: invalid modelindex\n");
427
428         if ((int) ent->v.solid == SOLID_BSP)
429         {
430                 Mod_CheckLoaded(model);
431                 if (model->type != mod_brush)
432                 {
433                         Con_Printf ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model, entity dump:\n");
434                         ED_Print (ent);
435                         Host_Error ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model\n");
436                 }
437                 if (ent->v.movetype != MOVETYPE_PUSH)
438                         Host_Error ("SV_ClipMoveToEntity: SOLID_BSP without MOVETYPE_PUSH");
439         }
440
441         Collision_ClipTrace(&trace, ent, model, ent->v.origin, ent->v.angles, ent->v.mins, ent->v.maxs, start, mins, maxs, end);
442
443         return trace;
444 }
445
446 //===========================================================================
447
448 /*
449 ====================
450 SV_ClipToLinks
451
452 Mins and maxs enclose the entire area swept by the move
453 ====================
454 */
455 void SV_ClipToLinks ( areanode_t *node, moveclip_t *clip )
456 {
457         link_t          *l, *next;
458         edict_t         *touch;
459         trace_t         trace;
460
461 loc0:
462         if (clip->trace.allsolid)
463                 return;
464 // touch linked edicts
465         for (l = node->solid_edicts.next ; l != &node->solid_edicts ; l = next)
466         {
467                 next = l->next;
468                 touch = EDICT_FROM_AREA(l);
469                 if (touch->v.solid == SOLID_NOT)
470                         continue;
471                 if (touch == clip->passedict)
472                         continue;
473                 if (touch->v.solid == SOLID_TRIGGER)
474                         Host_Error ("Trigger in clipping list");
475
476                 if (clip->type == MOVE_NOMONSTERS && touch->v.solid != SOLID_BSP)
477                         continue;
478
479                 if (clip->boxmins[0] > touch->v.absmax[0]
480                  || clip->boxmaxs[0] < touch->v.absmin[0]
481                  || clip->boxmins[1] > touch->v.absmax[1]
482                  || clip->boxmaxs[1] < touch->v.absmin[1]
483                  || clip->boxmins[2] > touch->v.absmax[2]
484                  || clip->boxmaxs[2] < touch->v.absmin[2])
485                         continue;
486
487                 if (clip->passedict)
488                 {
489                         if (clip->passedict->v.size[0] && !touch->v.size[0])
490                                 continue;       // points never interact
491                         if (PROG_TO_EDICT(touch->v.owner) == clip->passedict)
492                                 continue;       // don't clip against own missiles
493                         if (PROG_TO_EDICT(clip->passedict->v.owner) == touch)
494                                 continue;       // don't clip against owner
495                         // LordHavoc: corpse code
496                         if (clip->passedict->v.solid == SOLID_CORPSE && (touch->v.solid == SOLID_SLIDEBOX || touch->v.solid == SOLID_CORPSE))
497                                 continue;
498                         if (clip->passedict->v.solid == SOLID_SLIDEBOX && touch->v.solid == SOLID_CORPSE)
499                                 continue;
500                 }
501
502                 // might interact, so do an exact clip
503                 if ((int)touch->v.flags & FL_MONSTER)
504                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins2, clip->maxs2, clip->end);
505                 else if (touch->v.solid == SOLID_BSP)
506                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->hullmins, clip->hullmaxs, clip->end);
507                 else
508                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins, clip->maxs, clip->end);
509                 // LordHavoc: take the 'best' answers from the new trace and combine with existing data
510                 if (trace.allsolid)
511                         clip->trace.allsolid = true;
512                 if (trace.startsolid)
513                 {
514                         clip->trace.startsolid = true;
515                         if (!clip->trace.ent)
516                                 clip->trace.ent = trace.ent;
517                 }
518                 if (trace.inopen)
519                         clip->trace.inopen = true;
520                 if (trace.inwater)
521                         clip->trace.inwater = true;
522                 if (trace.fraction < clip->trace.fraction)
523                 {
524                         clip->trace.fraction = trace.fraction;
525                         VectorCopy(trace.endpos, clip->trace.endpos);
526                         clip->trace.plane = trace.plane;
527                         clip->trace.endcontents = trace.endcontents;
528                         clip->trace.ent = trace.ent;
529                 }
530         }
531
532 // recurse down both sides
533         if (node->axis == -1)
534                 return;
535
536         if (clip->boxmaxs[node->axis] > node->dist)
537         {
538                 if (clip->boxmins[node->axis] < node->dist)
539                         SV_ClipToLinks(node->children[1], clip);
540                 node = node->children[0];
541                 goto loc0;
542         }
543         else if (clip->boxmins[node->axis] < node->dist)
544         {
545                 node = node->children[1];
546                 goto loc0;
547         }
548 }
549
550
551 /*
552 ==================
553 SV_MoveBounds
554 ==================
555 */
556 void SV_MoveBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
557 {
558 #if 0
559 // debug to test against everything
560 boxmins[0] = boxmins[1] = boxmins[2] = -999999999;
561 boxmaxs[0] = boxmaxs[1] = boxmaxs[2] =  999999999;
562 #else
563         int             i;
564
565         for (i=0 ; i<3 ; i++)
566         {
567                 if (end[i] > start[i])
568                 {
569                         boxmins[i] = start[i] + mins[i] - 1;
570                         boxmaxs[i] = end[i] + maxs[i] + 1;
571                 }
572                 else
573                 {
574                         boxmins[i] = end[i] + mins[i] - 1;
575                         boxmaxs[i] = start[i] + maxs[i] + 1;
576                 }
577         }
578 #endif
579 }
580
581 /*
582 ==================
583 SV_Move
584 ==================
585 */
586 trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, edict_t *passedict)
587 {
588         moveclip_t      clip;
589         vec3_t          bigmins, bigmaxs;
590         int                     i;
591
592         memset ( &clip, 0, sizeof ( moveclip_t ) );
593
594         VectorCopy(start, clip.start);
595         VectorCopy(end, clip.end);
596         VectorCopy(mins, clip.mins);
597         VectorCopy(maxs, clip.maxs);
598         clip.type = type;
599         clip.passedict = passedict;
600
601         Collision_RoundUpToHullSize(sv.worldmodel, clip.mins, clip.maxs, clip.hullmins, clip.hullmaxs);
602
603         if (type == MOVE_MISSILE)
604         {
605                 // LordHavoc: modified this, was = -15, now = clip.mins[i] - 15
606                 for (i=0 ; i<3 ; i++)
607                 {
608                         clip.mins2[i] = clip.mins[i] - 15;
609                         clip.maxs2[i] = clip.maxs[i] + 15;
610                 }
611         }
612         else
613         {
614                 VectorCopy (clip.mins, clip.mins2);
615                 VectorCopy (clip.maxs, clip.maxs2);
616         }
617
618         bigmins[0] = min(clip.mins2[0], clip.hullmins[0]);
619         bigmaxs[0] = max(clip.maxs2[0], clip.hullmaxs[0]);
620         bigmins[1] = min(clip.mins2[1], clip.hullmins[1]);
621         bigmaxs[1] = max(clip.maxs2[1], clip.hullmaxs[1]);
622         bigmins[2] = min(clip.mins2[2], clip.hullmins[2]);
623         bigmaxs[2] = max(clip.maxs2[2], clip.hullmaxs[2]);
624
625         // clip to world
626         clip.trace = SV_ClipMoveToEntity (sv.edicts, start, mins, maxs, end);
627
628         // clip to entities
629         // create the bounding box of the entire move
630         SV_MoveBounds ( start, bigmins, bigmaxs, end, clip.boxmins, clip.boxmaxs );
631
632         SV_ClipToLinks ( sv_areanodes, &clip );
633
634         return clip.trace;
635 }
636