2 Copyright (C) 1996-1997 Id Software, Inc.
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.
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.
13 See the GNU General Public License for more details.
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.
20 // world.c -- world query functions
26 entities never clip against themselves, or their owner
28 line of sight checks trace->crosscontent, but bullets don't
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);
38 #define EDICT_FROM_AREA(l) ((edict_t *)((qbyte *)l - (int)&(((edict_t *)0)->area)))
40 //============================================================================
42 // ClearLink is used for new headnodes
43 void ClearLink (link_t *l)
45 l->prev = l->next = l;
48 void RemoveLink (link_t *l)
50 l->next->prev = l->prev;
51 l->prev->next = l->next;
54 void InsertLinkBefore (link_t *l, link_t *before)
57 l->prev = before->prev;
61 void InsertLinkAfter (link_t *l, link_t *after)
63 l->next = after->next;
72 // bounding box of entire move area
73 vec3_t boxmins, boxmaxs;
75 // size of the moving object
78 // size when clipping against monsters
81 // size when clipping against brush models
82 vec3_t hullmins, hullmaxs;
84 // start and end origin of move
90 // type of move (like ignoring monsters, or similar)
93 // the edict that is moving (if any)
100 ===============================================================================
104 ===============================================================================
107 typedef struct areanode_s
109 int axis; // -1 = leaf node
111 struct areanode_s *children[2];
112 link_t trigger_edicts;
117 #define AREA_NODES 32
119 static areanode_t sv_areanodes[AREA_NODES];
120 static int sv_numareanodes;
128 areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
132 vec3_t mins1, maxs1, mins2, maxs2;
134 anode = &sv_areanodes[sv_numareanodes];
137 ClearLink (&anode->trigger_edicts);
138 ClearLink (&anode->solid_edicts);
140 if (depth == AREA_DEPTH)
143 anode->children[0] = anode->children[1] = NULL;
147 VectorSubtract (maxs, mins, size);
148 if (size[0] > size[1])
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);
159 maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
161 anode->children[0] = SV_CreateAreaNode (depth+1, mins2, maxs2);
162 anode->children[1] = SV_CreateAreaNode (depth+1, mins1, maxs1);
173 void SV_ClearWorld (void)
177 memset (sv_areanodes, 0, sizeof(sv_areanodes));
179 Mod_CheckLoaded(sv.worldmodel);
180 SV_CreateAreaNode (0, sv.worldmodel->normalmins, sv.worldmodel->normalmaxs);
190 void SV_UnlinkEdict (edict_t *ent)
193 return; // not linked in anywhere
194 RemoveLink (&ent->area);
195 ent->area.prev = ent->area.next = NULL;
204 void SV_TouchLinks ( edict_t *ent, areanode_t *node )
208 int old_self, old_other;
211 // touch linked edicts
212 for (l = node->trigger_edicts.next ; l != &node->trigger_edicts ; l = next)
215 touch = EDICT_FROM_AREA(l);
218 if (!touch->v.touch || touch->v.solid != SOLID_TRIGGER)
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])
227 old_self = pr_global_struct->self;
228 old_other = pr_global_struct->other;
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, "");
235 pr_global_struct->self = old_self;
236 pr_global_struct->other = old_other;
239 // recurse down both sides
240 if (node->axis == -1)
243 if (ent->v.absmax[node->axis] > node->dist)
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];
252 if (ent->v.absmin[node->axis] < node->dist)
254 node = node->children[1];
267 void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
273 SV_UnlinkEdict (ent); // unlink from old position
275 if (ent == sv.edicts)
276 return; // don't add the world
283 if (ent->v.solid == SOLID_BSP)
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];
290 if (model->type != mod_brush)
291 PR_RunError("SOLID_BSP with non-BSP model\n");
293 if (ent->v.angles[0] || ent->v.angles[2] || ent->v.avelocity[0] || ent->v.avelocity[2])
295 VectorAdd(ent->v.origin, model->rotatedmins, ent->v.absmin);
296 VectorAdd(ent->v.origin, model->rotatedmaxs, ent->v.absmax);
298 else if (ent->v.angles[1] || ent->v.avelocity[1])
300 VectorAdd(ent->v.origin, model->yawmins, ent->v.absmin);
301 VectorAdd(ent->v.origin, model->yawmaxs, ent->v.absmax);
305 VectorAdd(ent->v.origin, model->normalmins, ent->v.absmin);
306 VectorAdd(ent->v.origin, model->normalmaxs, ent->v.absmax);
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);
318 VectorAdd (ent->v.origin, ent->v.mins, ent->v.absmin);
319 VectorAdd (ent->v.origin, ent->v.maxs, ent->v.absmax);
323 // to make items easier to pick up and allow them to be grabbed off
324 // of shelves, the abs sizes are expanded
326 if ((int)ent->v.flags & FL_ITEM)
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;
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;
347 if (ent->v.solid == SOLID_NOT)
350 // find the first node that the ent's box crosses
354 if (node->axis == -1)
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];
361 break; // crosses the node
366 if (ent->v.solid == SOLID_TRIGGER)
367 InsertLinkBefore (&ent->area, &node->trigger_edicts);
369 InsertLinkBefore (&ent->area, &node->solid_edicts);
371 // if touch_triggers, touch all entities at this node and descend for more
373 SV_TouchLinks ( ent, sv_areanodes );
379 ===============================================================================
381 POINT TESTING IN HULLS
383 ===============================================================================
388 SV_TestEntityPosition
390 This could be a lot more efficient...
393 int SV_TestEntityPosition (edict_t *ent)
395 return SV_Move (ent->v.origin, ent->v.mins, ent->v.maxs, ent->v.origin, MOVE_NORMAL, ent).startsolid;
400 ===============================================================================
402 LINE TESTING IN HULLS
404 ===============================================================================
411 Handles selection or creation of a clipping hull, and offseting (and
412 eventually rotation) of the end points
415 trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end)
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");
428 if ((int) ent->v.solid == SOLID_BSP)
430 Mod_CheckLoaded(model);
431 if (model->type != mod_brush)
433 Con_Printf ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model, entity dump:\n");
435 Host_Error ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model\n");
437 if (ent->v.movetype != MOVETYPE_PUSH)
438 Host_Error ("SV_ClipMoveToEntity: SOLID_BSP without MOVETYPE_PUSH");
441 Collision_ClipTrace(&trace, ent, model, ent->v.origin, ent->v.angles, ent->v.mins, ent->v.maxs, start, mins, maxs, end);
446 //===========================================================================
452 Mins and maxs enclose the entire area swept by the move
455 void SV_ClipToLinks ( areanode_t *node, moveclip_t *clip )
462 if (clip->trace.allsolid)
464 // touch linked edicts
465 for (l = node->solid_edicts.next ; l != &node->solid_edicts ; l = next)
468 touch = EDICT_FROM_AREA(l);
469 if (touch->v.solid == SOLID_NOT)
471 if (touch == clip->passedict)
473 if (touch->v.solid == SOLID_TRIGGER)
474 Host_Error ("Trigger in clipping list");
476 if (clip->type == MOVE_NOMONSTERS && touch->v.solid != SOLID_BSP)
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])
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))
498 if (clip->passedict->v.solid == SOLID_SLIDEBOX && touch->v.solid == SOLID_CORPSE)
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);
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
511 clip->trace.allsolid = true;
512 if (trace.startsolid)
514 clip->trace.startsolid = true;
515 if (!clip->trace.ent)
516 clip->trace.ent = trace.ent;
519 clip->trace.inopen = true;
521 clip->trace.inwater = true;
522 if (trace.fraction < clip->trace.fraction)
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;
532 // recurse down both sides
533 if (node->axis == -1)
536 if (clip->boxmaxs[node->axis] > node->dist)
538 if (clip->boxmins[node->axis] < node->dist)
539 SV_ClipToLinks(node->children[1], clip);
540 node = node->children[0];
543 else if (clip->boxmins[node->axis] < node->dist)
545 node = node->children[1];
556 void SV_MoveBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
559 // debug to test against everything
560 boxmins[0] = boxmins[1] = boxmins[2] = -999999999;
561 boxmaxs[0] = boxmaxs[1] = boxmaxs[2] = 999999999;
565 for (i=0 ; i<3 ; i++)
567 if (end[i] > start[i])
569 boxmins[i] = start[i] + mins[i] - 1;
570 boxmaxs[i] = end[i] + maxs[i] + 1;
574 boxmins[i] = end[i] + mins[i] - 1;
575 boxmaxs[i] = start[i] + maxs[i] + 1;
586 trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, edict_t *passedict)
589 vec3_t bigmins, bigmaxs;
592 memset ( &clip, 0, sizeof ( moveclip_t ) );
594 VectorCopy(start, clip.start);
595 VectorCopy(end, clip.end);
596 VectorCopy(mins, clip.mins);
597 VectorCopy(maxs, clip.maxs);
599 clip.passedict = passedict;
601 Collision_RoundUpToHullSize(sv.worldmodel, clip.mins, clip.maxs, clip.hullmins, clip.hullmaxs);
603 if (type == MOVE_MISSILE)
605 // LordHavoc: modified this, was = -15, now = clip.mins[i] - 15
606 for (i=0 ; i<3 ; i++)
608 clip.mins2[i] = clip.mins[i] - 15;
609 clip.maxs2[i] = clip.maxs[i] + 15;
614 VectorCopy (clip.mins, clip.mins2);
615 VectorCopy (clip.maxs, clip.maxs2);
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]);
626 clip.trace = SV_ClipMoveToEntity (sv.edicts, start, mins, maxs, end);
629 // create the bounding box of the entire move
630 SV_MoveBounds ( start, bigmins, bigmaxs, end, clip.boxmins, clip.boxmaxs );
632 SV_ClipToLinks ( sv_areanodes, &clip );