A minor removal of a few pieces of dead code. Nothing major. This is
[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_HullPointContents
389
390 ==================
391 */
392 int SV_HullPointContents (hull_t *hull, int num, vec3_t p)
393 {
394         while (num >= 0)
395                 num = hull->clipnodes[num].children[(hull->planes[hull->clipnodes[num].planenum].type < 3 ? p[hull->planes[hull->clipnodes[num].planenum].type] : DotProduct (hull->planes[hull->clipnodes[num].planenum].normal, p)) < hull->planes[hull->clipnodes[num].planenum].dist];
396
397         return num;
398 }
399
400 /*
401 ============
402 SV_TestEntityPosition
403
404 This could be a lot more efficient...
405 ============
406 */
407 edict_t *SV_TestEntityPosition (edict_t *ent)
408 {
409         trace_t trace;
410
411         trace = SV_Move (ent->v.origin, ent->v.mins, ent->v.maxs, ent->v.origin, MOVE_NORMAL, ent);
412
413         if (trace.startsolid)
414                 return sv.edicts;
415
416         return NULL;
417 }
418
419
420 /*
421 ===============================================================================
422
423 LINE TESTING IN HULLS
424
425 ===============================================================================
426 */
427
428 /*
429 ==================
430 SV_ClipMoveToEntity
431
432 Handles selection or creation of a clipping hull, and offseting (and
433 eventually rotation) of the end points
434 ==================
435 */
436 trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end)
437 {
438         int i;
439         trace_t trace;
440         model_t *model;
441
442         i = ent->v.modelindex;
443         if ((unsigned int) i >= MAX_MODELS)
444                 PR_RunError("SV_ClipMoveToEntity: invalid modelindex\n");
445         model = sv.models[i];
446         if (i != 0 && model == NULL)
447                 PR_RunError("SV_ClipMoveToEntity: invalid modelindex\n");
448
449         if ((int) ent->v.solid == SOLID_BSP)
450         {
451                 Mod_CheckLoaded(model);
452                 if (model->type != mod_brush)
453                 {
454                         Con_Printf ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model, entity dump:\n");
455                         ED_Print (ent);
456                         Host_Error ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model\n");
457                 }
458                 if (ent->v.movetype != MOVETYPE_PUSH)
459                         Host_Error ("SV_ClipMoveToEntity: SOLID_BSP without MOVETYPE_PUSH");
460         }
461
462         Collision_ClipTrace(&trace, ent, model, ent->v.origin, ent->v.angles, ent->v.mins, ent->v.maxs, start, mins, maxs, end);
463
464         return trace;
465 }
466
467 //===========================================================================
468
469 /*
470 ====================
471 SV_ClipToLinks
472
473 Mins and maxs enclose the entire area swept by the move
474 ====================
475 */
476 void SV_ClipToLinks ( areanode_t *node, moveclip_t *clip )
477 {
478         link_t          *l, *next;
479         edict_t         *touch;
480         trace_t         trace;
481
482 loc0:
483         if (clip->trace.allsolid)
484                 return;
485 // touch linked edicts
486         for (l = node->solid_edicts.next ; l != &node->solid_edicts ; l = next)
487         {
488                 next = l->next;
489                 touch = EDICT_FROM_AREA(l);
490                 if (touch->v.solid == SOLID_NOT)
491                         continue;
492                 if (touch == clip->passedict)
493                         continue;
494                 if (touch->v.solid == SOLID_TRIGGER)
495                         Host_Error ("Trigger in clipping list");
496
497                 if (clip->type == MOVE_NOMONSTERS && touch->v.solid != SOLID_BSP)
498                         continue;
499
500                 if (clip->boxmins[0] > touch->v.absmax[0]
501                  || clip->boxmaxs[0] < touch->v.absmin[0]
502                  || clip->boxmins[1] > touch->v.absmax[1]
503                  || clip->boxmaxs[1] < touch->v.absmin[1]
504                  || clip->boxmins[2] > touch->v.absmax[2]
505                  || clip->boxmaxs[2] < touch->v.absmin[2])
506                         continue;
507
508                 if (clip->passedict)
509                 {
510                         if (clip->passedict->v.size[0] && !touch->v.size[0])
511                                 continue;       // points never interact
512                         if (PROG_TO_EDICT(touch->v.owner) == clip->passedict)
513                                 continue;       // don't clip against own missiles
514                         if (PROG_TO_EDICT(clip->passedict->v.owner) == touch)
515                                 continue;       // don't clip against owner
516                         // LordHavoc: corpse code
517                         if (clip->passedict->v.solid == SOLID_CORPSE && (touch->v.solid == SOLID_SLIDEBOX || touch->v.solid == SOLID_CORPSE))
518                                 continue;
519                         if (clip->passedict->v.solid == SOLID_SLIDEBOX && touch->v.solid == SOLID_CORPSE)
520                                 continue;
521                 }
522
523                 // might interact, so do an exact clip
524                 if ((int)touch->v.flags & FL_MONSTER)
525                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins2, clip->maxs2, clip->end);
526                 else if (touch->v.solid == SOLID_BSP)
527                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->hullmins, clip->hullmaxs, clip->end);
528                 else
529                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins, clip->maxs, clip->end);
530                 // LordHavoc: take the 'best' answers from the new trace and combine with existing data
531                 if (trace.allsolid)
532                         clip->trace.allsolid = true;
533                 if (trace.startsolid)
534                 {
535                         clip->trace.startsolid = true;
536                         if (!clip->trace.ent)
537                                 clip->trace.ent = trace.ent;
538                 }
539                 if (trace.inopen)
540                         clip->trace.inopen = true;
541                 if (trace.inwater)
542                         clip->trace.inwater = true;
543                 if (trace.fraction < clip->trace.fraction)
544                 {
545                         clip->trace.fraction = trace.fraction;
546                         VectorCopy(trace.endpos, clip->trace.endpos);
547                         clip->trace.plane = trace.plane;
548                         clip->trace.endcontents = trace.endcontents;
549                         clip->trace.ent = trace.ent;
550                 }
551         }
552
553 // recurse down both sides
554         if (node->axis == -1)
555                 return;
556
557         if (clip->boxmaxs[node->axis] > node->dist)
558         {
559                 if (clip->boxmins[node->axis] < node->dist)
560                         SV_ClipToLinks(node->children[1], clip);
561                 node = node->children[0];
562                 goto loc0;
563         }
564         else if (clip->boxmins[node->axis] < node->dist)
565         {
566                 node = node->children[1];
567                 goto loc0;
568         }
569 }
570
571
572 /*
573 ==================
574 SV_MoveBounds
575 ==================
576 */
577 void SV_MoveBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
578 {
579 #if 0
580 // debug to test against everything
581 boxmins[0] = boxmins[1] = boxmins[2] = -999999999;
582 boxmaxs[0] = boxmaxs[1] = boxmaxs[2] =  999999999;
583 #else
584         int             i;
585
586         for (i=0 ; i<3 ; i++)
587         {
588                 if (end[i] > start[i])
589                 {
590                         boxmins[i] = start[i] + mins[i] - 1;
591                         boxmaxs[i] = end[i] + maxs[i] + 1;
592                 }
593                 else
594                 {
595                         boxmins[i] = end[i] + mins[i] - 1;
596                         boxmaxs[i] = start[i] + maxs[i] + 1;
597                 }
598         }
599 #endif
600 }
601
602 /*
603 ==================
604 SV_Move
605 ==================
606 */
607 trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, edict_t *passedict)
608 {
609         moveclip_t      clip;
610         vec3_t          bigmins, bigmaxs;
611         int                     i;
612
613         memset ( &clip, 0, sizeof ( moveclip_t ) );
614
615         VectorCopy(start, clip.start);
616         VectorCopy(end, clip.end);
617         VectorCopy(mins, clip.mins);
618         VectorCopy(maxs, clip.maxs);
619         clip.type = type;
620         clip.passedict = passedict;
621
622         Collision_RoundUpToHullSize(sv.worldmodel, clip.mins, clip.maxs, clip.hullmins, clip.hullmaxs);
623
624         if (type == MOVE_MISSILE)
625         {
626                 // LordHavoc: modified this, was = -15, now = clip.mins[i] - 15
627                 for (i=0 ; i<3 ; i++)
628                 {
629                         clip.mins2[i] = clip.mins[i] - 15;
630                         clip.maxs2[i] = clip.maxs[i] + 15;
631                 }
632         }
633         else
634         {
635                 VectorCopy (clip.mins, clip.mins2);
636                 VectorCopy (clip.maxs, clip.maxs2);
637         }
638
639         bigmins[0] = min(clip.mins2[0], clip.hullmins[0]);
640         bigmaxs[0] = max(clip.maxs2[0], clip.hullmaxs[0]);
641         bigmins[1] = min(clip.mins2[1], clip.hullmins[1]);
642         bigmaxs[1] = max(clip.maxs2[1], clip.hullmaxs[1]);
643         bigmins[2] = min(clip.mins2[2], clip.hullmins[2]);
644         bigmaxs[2] = max(clip.maxs2[2], clip.hullmaxs[2]);
645
646         // clip to world
647         clip.trace = SV_ClipMoveToEntity (sv.edicts, start, mins, maxs, end);
648
649         // clip to entities
650         // create the bounding box of the entire move
651         SV_MoveBounds ( start, bigmins, bigmaxs, end, clip.boxmins, clip.boxmaxs );
652
653         SV_ClipToLinks ( sv_areanodes, &clip );
654
655         return clip.trace;
656 }
657