home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Amiga 14 / MA_Cover_14.iso / source / c / q1source_amy / qw / server / world.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-12-21  |  20.1 KB  |  925 lines
  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 "qwsvdef.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. typedef struct
  34. {
  35.     vec3_t        boxmins, boxmaxs;// enclose the test object along entire move
  36.     float        *mins, *maxs;    // size of the moving object
  37.     vec3_t        mins2, maxs2;    // size when clipping against mosnters
  38.     float        *start, *end;
  39.     trace_t        trace;
  40.     int            type;
  41.     edict_t        *passedict;
  42. } moveclip_t;
  43.  
  44.  
  45. int SV_HullPointContents (hull_t *hull, int num, vec3_t p);
  46.  
  47. /*
  48. ===============================================================================
  49.  
  50. HULL BOXES
  51.  
  52. ===============================================================================
  53. */
  54.  
  55.  
  56. static    hull_t        box_hull;
  57. static    dclipnode_t    box_clipnodes[6];
  58. static    mplane_t    box_planes[6];
  59.  
  60. /*
  61. ===================
  62. SV_InitBoxHull
  63.  
  64. Set up the planes and clipnodes so that the six floats of a bounding box
  65. can just be stored out and get a proper hull_t structure.
  66. ===================
  67. */
  68. void SV_InitBoxHull (void)
  69. {
  70.     int        i;
  71.     int        side;
  72.  
  73.     box_hull.clipnodes = box_clipnodes;
  74.     box_hull.planes = box_planes;
  75.     box_hull.firstclipnode = 0;
  76.     box_hull.lastclipnode = 5;
  77.  
  78.     for (i=0 ; i<6 ; i++)
  79.     {
  80.         box_clipnodes[i].planenum = i;
  81.         
  82.         side = i&1;
  83.         
  84.         box_clipnodes[i].children[side] = CONTENTS_EMPTY;
  85.         if (i != 5)
  86.             box_clipnodes[i].children[side^1] = i + 1;
  87.         else
  88.             box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
  89.         
  90.         box_planes[i].type = i>>1;
  91.         box_planes[i].normal[i>>1] = 1;
  92.     }
  93.     
  94. }
  95.  
  96.  
  97. /*
  98. ===================
  99. SV_HullForBox
  100.  
  101. To keep everything totally uniform, bounding boxes are turned into small
  102. BSP trees instead of being compared directly.
  103. ===================
  104. */
  105. hull_t    *SV_HullForBox (vec3_t mins, vec3_t maxs)
  106. {
  107.     box_planes[0].dist = maxs[0];
  108.     box_planes[1].dist = mins[0];
  109.     box_planes[2].dist = maxs[1];
  110.     box_planes[3].dist = mins[1];
  111.     box_planes[4].dist = maxs[2];
  112.     box_planes[5].dist = mins[2];
  113.  
  114.     return &box_hull;
  115. }
  116.  
  117.  
  118.  
  119. /*
  120. ================
  121. SV_HullForEntity
  122.  
  123. Returns a hull that can be used for testing or clipping an object of mins/maxs
  124. size.
  125. Offset is filled in to contain the adjustment that must be added to the
  126. testing object's origin to get a point to use with the returned hull.
  127. ================
  128. */
  129. hull_t *SV_HullForEntity (edict_t *ent, vec3_t mins, vec3_t maxs, vec3_t offset)
  130. {
  131.     model_t        *model;
  132.     vec3_t        size;
  133.     vec3_t        hullmins, hullmaxs;
  134.     hull_t        *hull;
  135.  
  136. // decide which clipping hull to use, based on the size
  137.     if (ent->v.solid == SOLID_BSP)
  138.     {    // explicit hulls in the BSP model
  139.         if (ent->v.movetype != MOVETYPE_PUSH)
  140.             SV_Error ("SOLID_BSP without MOVETYPE_PUSH");
  141.  
  142.         model = sv.models[ (int)ent->v.modelindex ];
  143.  
  144.         if (!model || model->type != mod_brush)
  145.             SV_Error ("MOVETYPE_PUSH with a non bsp model");
  146.  
  147.         VectorSubtract (maxs, mins, size);
  148.         if (size[0] < 3)
  149.             hull = &model->hulls[0];
  150.         else if (size[0] <= 32)
  151.             hull = &model->hulls[1];
  152.         else
  153.             hull = &model->hulls[2];
  154.  
  155. // calculate an offset value to center the origin
  156.         VectorSubtract (hull->clip_mins, mins, offset);
  157.         VectorAdd (offset, ent->v.origin, offset);
  158.     }
  159.     else
  160.     {    // create a temp hull from bounding box sizes
  161.  
  162.         VectorSubtract (ent->v.mins, maxs, hullmins);
  163.         VectorSubtract (ent->v.maxs, mins, hullmaxs);
  164.         hull = SV_HullForBox (hullmins, hullmaxs);
  165.         
  166.         VectorCopy (ent->v.origin, offset);
  167.     }
  168.  
  169.  
  170.     return hull;
  171. }
  172.  
  173. /*
  174. ===============================================================================
  175.  
  176. ENTITY AREA CHECKING
  177.  
  178. ===============================================================================
  179. */
  180.  
  181.  
  182. areanode_t    sv_areanodes[AREA_NODES];
  183. int            sv_numareanodes;
  184.  
  185. /*
  186. ===============
  187. SV_CreateAreaNode
  188.  
  189. ===============
  190. */
  191. areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
  192. {
  193.     areanode_t    *anode;
  194.     vec3_t        size;
  195.     vec3_t        mins1, maxs1, mins2, maxs2;
  196.  
  197.     anode = &sv_areanodes[sv_numareanodes];
  198.     sv_numareanodes++;
  199.  
  200.     ClearLink (&anode->trigger_edicts);
  201.     ClearLink (&anode->solid_edicts);
  202.     
  203.     if (depth == AREA_DEPTH)
  204.     {
  205.         anode->axis = -1;
  206.         anode->children[0] = anode->children[1] = NULL;
  207.         return anode;
  208.     }
  209.     
  210.     VectorSubtract (maxs, mins, size);
  211.     if (size[0] > size[1])
  212.         anode->axis = 0;
  213.     else
  214.         anode->axis = 1;
  215.     
  216.     anode->dist = 0.5 * (maxs[anode->axis] + mins[anode->axis]);
  217.     VectorCopy (mins, mins1);    
  218.     VectorCopy (mins, mins2);    
  219.     VectorCopy (maxs, maxs1);    
  220.     VectorCopy (maxs, maxs2);    
  221.     
  222.     maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
  223.     
  224.     anode->children[0] = SV_CreateAreaNode (depth+1, mins2, maxs2);
  225.     anode->children[1] = SV_CreateAreaNode (depth+1, mins1, maxs1);
  226.  
  227.     return anode;
  228. }
  229.  
  230. /*
  231. ===============
  232. SV_ClearWorld
  233.  
  234. ===============
  235. */
  236. void SV_ClearWorld (void)
  237. {
  238.     SV_InitBoxHull ();
  239.     
  240.     memset (sv_areanodes, 0, sizeof(sv_areanodes));
  241.     sv_numareanodes = 0;
  242.     SV_CreateAreaNode (0, sv.worldmodel->mins, sv.worldmodel->maxs);
  243. }
  244.  
  245.  
  246. /*
  247. ===============
  248. SV_UnlinkEdict
  249.  
  250. ===============
  251. */
  252. void SV_UnlinkEdict (edict_t *ent)
  253. {
  254.     if (!ent->area.prev)
  255.         return;        // not linked in anywhere
  256.     RemoveLink (&ent->area);
  257.     ent->area.prev = ent->area.next = NULL;
  258. }
  259.  
  260.  
  261. /*
  262. ====================
  263. SV_TouchLinks
  264. ====================
  265. */
  266. void SV_TouchLinks ( edict_t *ent, areanode_t *node )
  267. {
  268.     link_t        *l, *next;
  269.     edict_t        *touch;
  270.     int            old_self, old_other;
  271.  
  272. // touch linked edicts
  273.     for (l = node->trigger_edicts.next ; l != &node->trigger_edicts ; l = next)
  274.     {
  275.         next = l->next;
  276.         touch = EDICT_FROM_AREA(l);
  277.         if (touch == ent)
  278.             continue;
  279.         if (!touch->v.touch || touch->v.solid != SOLID_TRIGGER)
  280.             continue;
  281.         if (ent->v.absmin[0] > touch->v.absmax[0]
  282.         || ent->v.absmin[1] > touch->v.absmax[1]
  283.         || ent->v.absmin[2] > touch->v.absmax[2]
  284.         || ent->v.absmax[0] < touch->v.absmin[0]
  285.         || ent->v.absmax[1] < touch->v.absmin[1]
  286.         || ent->v.absmax[2] < touch->v.absmin[2] )
  287.             continue;
  288.             
  289.         old_self = pr_global_struct->self;
  290.         old_other = pr_global_struct->other;
  291.  
  292.         pr_global_struct->self = EDICT_TO_PROG(touch);
  293.         pr_global_struct->other = EDICT_TO_PROG(ent);
  294.         pr_global_struct->time = sv.time;
  295.         PR_ExecuteProgram (touch->v.touch);
  296.  
  297.         pr_global_struct->self = old_self;
  298.         pr_global_struct->other = old_other;
  299.     }
  300.     
  301. // recurse down both sides
  302.     if (node->axis == -1)
  303.         return;
  304.     
  305.     if ( ent->v.absmax[node->axis] > node->dist )
  306.         SV_TouchLinks ( ent, node->children[0] );
  307.     if ( ent->v.absmin[node->axis] < node->dist )
  308.         SV_TouchLinks ( ent, node->children[1] );
  309. }
  310.  
  311.  
  312. /*
  313. ===============
  314. SV_FindTouchedLeafs
  315.  
  316. ===============
  317. */
  318. void SV_FindTouchedLeafs (edict_t *ent, mnode_t *node)
  319. {
  320.     mplane_t    *splitplane;
  321.     mleaf_t        *leaf;
  322.     int            sides;
  323.     int            leafnum;
  324.  
  325.     if (node->contents == CONTENTS_SOLID)
  326.         return;
  327.     
  328. // add an efrag if the node is a leaf
  329.  
  330.     if ( node->contents < 0)
  331.     {
  332.         if (ent->num_leafs == MAX_ENT_LEAFS)
  333.             return;
  334.  
  335.         leaf = (mleaf_t *)node;
  336.         leafnum = leaf - sv.worldmodel->leafs - 1;
  337.  
  338.         ent->leafnums[ent->num_leafs] = leafnum;
  339.         ent->num_leafs++;            
  340.         return;
  341.     }
  342.     
  343. // NODE_MIXED
  344.  
  345.     splitplane = node->plane;
  346.     sides = BOX_ON_PLANE_SIDE(ent->v.absmin, ent->v.absmax, splitplane);
  347.     
  348. // recurse down the contacted sides
  349.     if (sides & 1)
  350.         SV_FindTouchedLeafs (ent, node->children[0]);
  351.         
  352.     if (sides & 2)
  353.         SV_FindTouchedLeafs (ent, node->children[1]);
  354. }
  355.  
  356. /*
  357. ===============
  358. SV_LinkEdict
  359.  
  360. ===============
  361. */
  362. void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
  363. {
  364.     areanode_t    *node;
  365.     
  366.     if (ent->area.prev)
  367.         SV_UnlinkEdict (ent);    // unlink from old position
  368.         
  369.     if (ent == sv.edicts)
  370.         return;        // don't add the world
  371.  
  372.     if (ent->free)
  373.         return;
  374.  
  375. // set the abs box
  376.     VectorAdd (ent->v.origin, ent->v.mins, ent->v.absmin);    
  377.     VectorAdd (ent->v.origin, ent->v.maxs, ent->v.absmax);
  378.  
  379. //
  380. // to make items easier to pick up and allow them to be grabbed off
  381. // of shelves, the abs sizes are expanded
  382. //
  383.     if ((int)ent->v.flags & FL_ITEM)
  384.     {
  385.         ent->v.absmin[0] -= 15;
  386.         ent->v.absmin[1] -= 15;
  387.         ent->v.absmax[0] += 15;
  388.         ent->v.absmax[1] += 15;
  389.     }
  390.     else
  391.     {    // because movement is clipped an epsilon away from an actual edge,
  392.         // we must fully check even when bounding boxes don't quite touch
  393.         ent->v.absmin[0] -= 1;
  394.         ent->v.absmin[1] -= 1;
  395.         ent->v.absmin[2] -= 1;
  396.         ent->v.absmax[0] += 1;
  397.         ent->v.absmax[1] += 1;
  398.         ent->v.absmax[2] += 1;
  399.     }
  400.     
  401. // link to PVS leafs
  402.     ent->num_leafs = 0;
  403.     if (ent->v.modelindex)
  404.         SV_FindTouchedLeafs (ent, sv.worldmodel->nodes);
  405.  
  406.     if (ent->v.solid == SOLID_NOT)
  407.         return;
  408.  
  409. // find the first node that the ent's box crosses
  410.     node = sv_areanodes;
  411.     while (1)
  412.     {
  413.         if (node->axis == -1)
  414.             break;
  415.         if (ent->v.absmin[node->axis] > node->dist)
  416.             node = node->children[0];
  417.         else if (ent->v.absmax[node->axis] < node->dist)
  418.             node = node->children[1];
  419.         else
  420.             break;        // crosses the node
  421.     }
  422.     
  423. // link it in    
  424.  
  425.     if (ent->v.solid == SOLID_TRIGGER)
  426.         InsertLinkBefore (&ent->area, &node->trigger_edicts);
  427.     else
  428.         InsertLinkBefore (&ent->area, &node->solid_edicts);
  429.     
  430. // if touch_triggers, touch all entities at this node and decend for more
  431.     if (touch_triggers)
  432.         SV_TouchLinks ( ent, sv_areanodes );
  433. }
  434.  
  435.  
  436.  
  437. /*
  438. ===============================================================================
  439.  
  440. POINT TESTING IN HULLS
  441.  
  442. ===============================================================================
  443. */
  444.  
  445. #if    !id386
  446.  
  447. /*
  448. ==================
  449. SV_HullPointContents
  450.  
  451. ==================
  452. */
  453. int SV_HullPointContents (hull_t *hull, int num, vec3_t p)
  454. {
  455.     float        d;
  456.     dclipnode_t    *node;
  457.     mplane_t    *plane;
  458.  
  459.     while (num >= 0)
  460.     {
  461.         if (num < hull->firstclipnode || num > hull->lastclipnode)
  462.             SV_Error ("SV_HullPointContents: bad node number");
  463.     
  464.         node = hull->clipnodes + num;
  465.         plane = hull->planes + node->planenum;
  466.         
  467.         if (plane->type < 3)
  468.             d = p[plane->type] - plane->dist;
  469.         else
  470.             d = DotProduct (plane->normal, p) - plane->dist;
  471.         if (d < 0)
  472.             num = node->children[1];
  473.         else
  474.             num = node->children[0];
  475.     }
  476.     
  477.     return num;
  478. }
  479.  
  480. #endif    // !id386
  481.  
  482.  
  483. /*
  484. ==================
  485. SV_PointContents
  486.  
  487. ==================
  488. */
  489. int SV_PointContents (vec3_t p)
  490. {
  491.     return SV_HullPointContents (&sv.worldmodel->hulls[0], 0, p);
  492. }
  493.  
  494. //===========================================================================
  495.  
  496. /*
  497. ============
  498. SV_TestEntityPosition
  499.  
  500. A small wrapper around SV_BoxInSolidEntity that never clips against the
  501. supplied entity.
  502. ============
  503. */
  504. edict_t    *SV_TestEntityPosition (edict_t *ent)
  505. {
  506.     trace_t    trace;
  507.  
  508.     trace = SV_Move (ent->v.origin, ent->v.mins, ent->v.maxs, ent->v.origin, 0, ent);
  509.     
  510.     if (trace.startsolid)
  511.         return sv.edicts;
  512.         
  513.     return NULL;
  514. }
  515.  
  516. /*
  517. ===============================================================================
  518.  
  519. LINE TESTING IN HULLS
  520.  
  521. ===============================================================================
  522. */
  523.  
  524. // 1/32 epsilon to keep floating point happy
  525. #define    DIST_EPSILON    (0.03125)
  526.  
  527. /*
  528. ==================
  529. SV_RecursiveHullCheck
  530.  
  531. ==================
  532. */
  533. qboolean SV_RecursiveHullCheck (hull_t *hull, int num, float p1f, float p2f, vec3_t p1, vec3_t p2, trace_t *trace)
  534. {
  535.     dclipnode_t    *node;
  536.     mplane_t    *plane;
  537.     float        t1, t2;
  538.     float        frac;
  539.     int            i;
  540.     vec3_t        mid;
  541.     int            side;
  542.     float        midf;
  543.  
  544. // check for empty
  545.     if (num < 0)
  546.     {
  547.         if (num != CONTENTS_SOLID)
  548.         {
  549.             trace->allsolid = false;
  550.             if (num == CONTENTS_EMPTY)
  551.                 trace->inopen = true;
  552.             else
  553.                 trace->inwater = true;
  554.         }
  555.         else
  556.             trace->startsolid = true;
  557.         return true;        // empty
  558.     }
  559.  
  560.     if (num < hull->firstclipnode || num > hull->lastclipnode)
  561.         SV_Error ("SV_RecursiveHullCheck: bad node number");
  562.  
  563. //
  564. // find the point distances
  565. //
  566.     node = hull->clipnodes + num;
  567.     plane = hull->planes + node->planenum;
  568.  
  569.     if (plane->type < 3)
  570.     {
  571.         t1 = p1[plane->type] - plane->dist;
  572.         t2 = p2[plane->type] - plane->dist;
  573.     }
  574.     else
  575.     {
  576.         t1 = DotProduct (plane->normal, p1) - plane->dist;
  577.         t2 = DotProduct (plane->normal, p2) - plane->dist;
  578.     }
  579.     
  580. #if 1
  581.     if (t1 >= 0 && t2 >= 0)
  582.         return SV_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
  583.     if (t1 < 0 && t2 < 0)
  584.         return SV_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
  585. #else
  586.     if ( (t1 >= DIST_EPSILON && t2 >= DIST_EPSILON) || (t2 > t1 && t1 >= 0) )
  587.         return SV_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
  588.     if ( (t1 <= -DIST_EPSILON && t2 <= -DIST_EPSILON) || (t2 < t1 && t1 <= 0) )
  589.         return SV_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
  590. #endif
  591.  
  592. // put the crosspoint DIST_EPSILON pixels on the near side
  593.     if (t1 < 0)
  594.         frac = (t1 + DIST_EPSILON)/(t1-t2);
  595.     else
  596.         frac = (t1 - DIST_EPSILON)/(t1-t2);
  597.     if (frac < 0)
  598.         frac = 0;
  599.     if (frac > 1)
  600.         frac = 1;
  601.         
  602.     midf = p1f + (p2f - p1f)*frac;
  603.     for (i=0 ; i<3 ; i++)
  604.         mid[i] = p1[i] + frac*(p2[i] - p1[i]);
  605.  
  606.     side = (t1 < 0);
  607.  
  608. // move up to the node
  609.     if (!SV_RecursiveHullCheck (hull, node->children[side], p1f, midf, p1, mid, trace) )
  610.         return false;
  611.  
  612. #ifdef PARANOID
  613.     if (SV_HullPointContents (sv_hullmodel, mid, node->children[side])
  614.     == CONTENTS_SOLID)
  615.     {
  616.         Con_Printf ("mid PointInHullSolid\n");
  617.         return false;
  618.     }
  619. #endif
  620.     
  621.     if (SV_HullPointContents (hull, node->children[side^1], mid)
  622.     != CONTENTS_SOLID)
  623. // go past the node
  624.         return SV_RecursiveHullCheck (hull, node->children[side^1], midf, p2f, mid, p2, trace);
  625.     
  626.     if (trace->allsolid)
  627.         return false;        // never got out of the solid area
  628.         
  629. //==================
  630. // the other side of the node is solid, this is the impact point
  631. //==================
  632.     if (!side)
  633.     {
  634.         VectorCopy (plane->normal, trace->plane.normal);
  635.         trace->plane.dist = plane->dist;
  636.     }
  637.     else
  638.     {
  639.         VectorSubtract (vec3_origin, plane->normal, trace->plane.normal);
  640.         trace->plane.dist = -plane->dist;
  641.     }
  642.  
  643.     while (SV_HullPointContents (hull, hull->firstclipnode, mid)
  644.     == CONTENTS_SOLID)
  645.     { // shouldn't really happen, but does occasionally
  646.         frac -= 0.1;
  647.         if (frac < 0)
  648.         {
  649.             trace->fraction = midf;
  650.             VectorCopy (mid, trace->endpos);
  651.             Con_Printf ("backup past 0\n");
  652.             return false;
  653.         }
  654.         midf = p1f + (p2f - p1f)*frac;
  655.         for (i=0 ; i<3 ; i++)
  656.             mid[i] = p1[i] + frac*(p2[i] - p1[i]);
  657.     }
  658.  
  659.     trace->fraction = midf;
  660.     VectorCopy (mid, trace->endpos);
  661.  
  662.     return false;
  663. }
  664.  
  665.  
  666. /*
  667. ==================
  668. SV_ClipMoveToEntity
  669.  
  670. Handles selection or creation of a clipping hull, and offseting (and
  671. eventually rotation) of the end points
  672. ==================
  673. */
  674. trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end)
  675. {
  676.     trace_t        trace;
  677.     vec3_t        offset;
  678.     vec3_t        start_l, end_l;
  679.     hull_t        *hull;
  680.  
  681. // fill in a default trace
  682.     memset (&trace, 0, sizeof(trace_t));
  683.     trace.fraction = 1;
  684.     trace.allsolid = true;
  685.     VectorCopy (end, trace.endpos);
  686.  
  687. // get the clipping hull
  688.     hull = SV_HullForEntity (ent, mins, maxs, offset);
  689.  
  690.     VectorSubtract (start, offset, start_l);
  691.     VectorSubtract (end, offset, end_l);
  692.  
  693. // trace a line through the apropriate clipping hull
  694.     SV_RecursiveHullCheck (hull, hull->firstclipnode, 0, 1, start_l, end_l, &trace);
  695.  
  696. // fix trace up by the offset
  697.     if (trace.fraction != 1)
  698.         VectorAdd (trace.endpos, offset, trace.endpos);
  699.  
  700. // did we clip the move?
  701.     if (trace.fraction < 1 || trace.startsolid  )
  702.         trace.ent = ent;
  703.  
  704.     return trace;
  705. }
  706.  
  707. //===========================================================================
  708.  
  709. /*
  710. ====================
  711. SV_ClipToLinks
  712.  
  713. Mins and maxs enclose the entire area swept by the move
  714. ====================
  715. */
  716. void SV_ClipToLinks ( areanode_t *node, moveclip_t *clip )
  717. {
  718.     link_t        *l, *next;
  719.     edict_t        *touch;
  720.     trace_t        trace;
  721.  
  722. // touch linked edicts
  723.     for (l = node->solid_edicts.next ; l != &node->solid_edicts ; l = next)
  724.     {
  725.         next = l->next;
  726.         touch = EDICT_FROM_AREA(l);
  727.         if (touch->v.solid == SOLID_NOT)
  728.             continue;
  729.         if (touch == clip->passedict)
  730.             continue;
  731.         if (touch->v.solid == SOLID_TRIGGER)
  732.             SV_Error ("Trigger in clipping list");
  733.  
  734.         if (clip->type == MOVE_NOMONSTERS && touch->v.solid != SOLID_BSP)
  735.             continue;
  736.  
  737.         if (clip->boxmins[0] > touch->v.absmax[0]
  738.         || clip->boxmins[1] > touch->v.absmax[1]
  739.         || clip->boxmins[2] > touch->v.absmax[2]
  740.         || clip->boxmaxs[0] < touch->v.absmin[0]
  741.         || clip->boxmaxs[1] < touch->v.absmin[1]
  742.         || clip->boxmaxs[2] < touch->v.absmin[2] )
  743.             continue;
  744.  
  745.         if (clip->passedict && clip->passedict->v.size[0] && !touch->v.size[0])
  746.             continue;    // points never interact
  747.  
  748.     // might intersect, so do an exact clip
  749.         if (clip->trace.allsolid)
  750.             return;
  751.         if (clip->passedict)
  752.         {
  753.              if (PROG_TO_EDICT(touch->v.owner) == clip->passedict)
  754.                 continue;    // don't clip against own missiles
  755.             if (PROG_TO_EDICT(clip->passedict->v.owner) == touch)
  756.                 continue;    // don't clip against owner
  757.         }
  758.  
  759.         if ((int)touch->v.flags & FL_MONSTER)
  760.             trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins2, clip->maxs2, clip->end);
  761.         else
  762.             trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins, clip->maxs, clip->end);
  763.         if (trace.allsolid || trace.startsolid ||
  764.         trace.fraction < clip->trace.fraction)
  765.         {
  766.             trace.ent = touch;
  767.              if (clip->trace.startsolid)
  768.             {
  769.                 clip->trace = trace;
  770.                 clip->trace.startsolid = true;
  771.             }
  772.             else
  773.                 clip->trace = trace;
  774.         }
  775.         else if (trace.startsolid)
  776.             clip->trace.startsolid = true;
  777.     }
  778.     
  779. // recurse down both sides
  780.     if (node->axis == -1)
  781.         return;
  782.  
  783.     if ( clip->boxmaxs[node->axis] > node->dist )
  784.         SV_ClipToLinks ( node->children[0], clip );
  785.     if ( clip->boxmins[node->axis] < node->dist )
  786.         SV_ClipToLinks ( node->children[1], clip );
  787. }
  788.  
  789.  
  790. /*
  791. ==================
  792. SV_MoveBounds
  793. ==================
  794. */
  795. void SV_MoveBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
  796. {
  797. #if 0
  798. // debug to test against everything
  799. boxmins[0] = boxmins[1] = boxmins[2] = -9999;
  800. boxmaxs[0] = boxmaxs[1] = boxmaxs[2] = 9999;
  801. #else
  802.     int        i;
  803.     
  804.     for (i=0 ; i<3 ; i++)
  805.     {
  806.         if (end[i] > start[i])
  807.         {
  808.             boxmins[i] = start[i] + mins[i] - 1;
  809.             boxmaxs[i] = end[i] + maxs[i] + 1;
  810.         }
  811.         else
  812.         {
  813.             boxmins[i] = end[i] + mins[i] - 1;
  814.             boxmaxs[i] = start[i] + maxs[i] + 1;
  815.         }
  816.     }
  817. #endif
  818. }
  819.  
  820. /*
  821. ==================
  822. SV_Move
  823. ==================
  824. */
  825. trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, edict_t *passedict)
  826. {
  827.     moveclip_t    clip;
  828.     int            i;
  829.  
  830.     memset ( &clip, 0, sizeof ( moveclip_t ) );
  831.  
  832. // clip to world
  833.     clip.trace = SV_ClipMoveToEntity ( sv.edicts, start, mins, maxs, end );
  834.  
  835.     clip.start = start;
  836.     clip.end = end;
  837.     clip.mins = mins;
  838.     clip.maxs = maxs;
  839.     clip.type = type;
  840.     clip.passedict = passedict;
  841.  
  842.     if (type == MOVE_MISSILE)
  843.     {
  844.         for (i=0 ; i<3 ; i++)
  845.         {
  846.             clip.mins2[i] = -15;
  847.             clip.maxs2[i] = 15;
  848.         }
  849.     }
  850.     else
  851.     {
  852.         VectorCopy (mins, clip.mins2);
  853.         VectorCopy (maxs, clip.maxs2);
  854.     }
  855.     
  856. // create the bounding box of the entire move
  857.     SV_MoveBounds ( start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs );
  858.  
  859. // clip to entities
  860.     SV_ClipToLinks ( sv_areanodes, &clip );
  861.  
  862.     return clip.trace;
  863. }
  864.  
  865. //=============================================================================
  866.  
  867. /*
  868. ============
  869. SV_TestPlayerPosition
  870.  
  871. ============
  872. */
  873. edict_t    *SV_TestPlayerPosition (edict_t *ent, vec3_t origin)
  874. {
  875.     hull_t    *hull;
  876.     edict_t    *check;
  877.     vec3_t    boxmins, boxmaxs;
  878.     vec3_t    offset;
  879.     int        e;
  880.     
  881. // check world first
  882.     hull = &sv.worldmodel->hulls[1];
  883.     if ( SV_HullPointContents (hull, hull->firstclipnode, origin) != CONTENTS_EMPTY )
  884.         return sv.edicts;
  885.  
  886. // check all entities
  887.     VectorAdd (origin, ent->v.mins, boxmins);
  888.     VectorAdd (origin, ent->v.maxs, boxmaxs);
  889.     
  890.     check = NEXT_EDICT(sv.edicts);
  891.     for (e=1 ; e<sv.num_edicts ; e++, check = NEXT_EDICT(check))
  892.     {
  893.         if (check->free)
  894.             continue;
  895.         if (check->v.solid != SOLID_BSP &&
  896.             check->v.solid != SOLID_BBOX &&
  897.             check->v.solid != SOLID_SLIDEBOX)
  898.             continue;
  899.  
  900.         if (boxmins[0] > check->v.absmax[0]
  901.         || boxmins[1] > check->v.absmax[1]
  902.         || boxmins[2] > check->v.absmax[2]
  903.         || boxmaxs[0] < check->v.absmin[0]
  904.         || boxmaxs[1] < check->v.absmin[1]
  905.         || boxmaxs[2] < check->v.absmin[2] )
  906.             continue;
  907.  
  908.         if (check == ent)
  909.             continue;
  910.  
  911.     // get the clipping hull
  912.         hull = SV_HullForEntity (check, ent->v.mins, ent->v.maxs, offset);
  913.     
  914.         VectorSubtract (origin, offset, offset);
  915.     
  916.     // test the point
  917.         if ( SV_HullPointContents (hull, hull->firstclipnode, offset) != CONTENTS_EMPTY )
  918.             return check;
  919.     }
  920.  
  921.     return NULL;
  922. }
  923.  
  924.  
  925.