added new method of culling irrelevant entity collisions - a grid of areas
authorhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Fri, 21 Feb 2003 09:24:53 +0000 (09:24 +0000)
committerhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Fri, 21 Feb 2003 09:24:53 +0000 (09:24 +0000)
the areanode system still lingers because it can cope with things the grid can not (entities outside the grid, or too large for the alloted 16 grid links per entity)

git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@2775 d7cf8633-e32d-0410-b094-e92efae38249

progs.h
world.c

diff --git a/progs.h b/progs.h
index 1438dce..6d3fb99 100644 (file)
--- a/progs.h
+++ b/progs.h
@@ -37,9 +37,12 @@ typedef union eval_s
 
 typedef struct link_s
 {
+       void *entity;
        struct link_s   *prev, *next;
 } link_t;
 
+#define ENTITYGRIDAREAS 16
+
 // the entire server entity structure
 typedef struct edict_s
 {
@@ -47,6 +50,8 @@ typedef struct edict_s
        qboolean free;
        // physics area this edict is linked into
        link_t area;
+       // physics grid areas this edict is linked into
+       link_t areagrid[ENTITYGRIDAREAS];
 
        // old entity protocol, not used
 #ifdef QUAKEENTITIES
diff --git a/world.c b/world.c
index 395f54e..7505c86 100644 (file)
--- a/world.c
+++ b/world.c
@@ -25,7 +25,7 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 
 entities never clip against themselves, or their owner
 
-line of sight checks trace->crosscontent, but bullets don't
+line of sight checks trace->inopen and trace->inwater, but bullets don't
 
 */
 
@@ -36,22 +36,46 @@ void SV_World_Init(void)
 {
        Cvar_RegisterVariable(&sv_useareanodes);
        Cvar_RegisterVariable(&sv_polygoncollisions);
-       Collision_Init ();
+       Collision_Init();
 }
 
+typedef struct
+{
+       // bounding box of entire move area
+       vec3_t boxmins, boxmaxs;
+
+       // size of the moving object
+       vec3_t mins, maxs;
+
+       // size when clipping against monsters
+       vec3_t mins2, maxs2;
+
+       // size when clipping against brush models
+       vec3_t hullmins, hullmaxs;
 
-void ClearLink (link_t *l);
-void RemoveLink (link_t *l);
-void InsertLinkBefore (link_t *l, link_t *before);
-void InsertLinkAfter (link_t *l, link_t *after);
+       // start and end origin of move
+       vec3_t start, end;
 
-#define        EDICT_FROM_AREA(l) ((edict_t *)((qbyte *)l - (int)&(((edict_t *)0)->area)))
+       // trace results
+       trace_t trace;
+
+       // type of move (like ignoring monsters, or similar)
+       int type;
+
+       // the edict that is moving (if any)
+       edict_t *passedict;
+}
+moveclip_t;
+
+//#define EDICT_FROM_AREA(l) ((edict_t *)((qbyte *)l - (int)&(((edict_t *)0)->area)))
+#define EDICT_FROM_AREA(l) ((edict_t *)l->entity)
 
 //============================================================================
 
 // ClearLink is used for new headnodes
 void ClearLink (link_t *l)
 {
+       l->entity = NULL;
        l->prev = l->next = l;
 }
 
@@ -61,13 +85,15 @@ void RemoveLink (link_t *l)
        l->prev->next = l->next;
 }
 
-void InsertLinkBefore (link_t *l, link_t *before)
+void InsertLinkBefore (link_t *l, link_t *before, void *ent)
 {
+       l->entity = ent;
        l->next = before;
        l->prev = before->prev;
        l->prev->next = l;
        l->next->prev = l;
 }
+
 void InsertLinkAfter (link_t *l, link_t *after)
 {
        l->next = after->next;
@@ -77,35 +103,6 @@ void InsertLinkAfter (link_t *l, link_t *after)
 }
 
 
-typedef struct
-{
-       // bounding box of entire move area
-       vec3_t          boxmins, boxmaxs;
-
-       // size of the moving object
-       vec3_t          mins, maxs;
-
-       // size when clipping against monsters
-       vec3_t          mins2, maxs2;
-
-       // size when clipping against brush models
-       vec3_t          hullmins, hullmaxs;
-
-       // start and end origin of move
-       vec3_t          start, end;
-
-       // trace results
-       trace_t         trace;
-
-       // type of move (like ignoring monsters, or similar)
-       int                     type;
-
-       // the edict that is moving (if any)
-       edict_t         *passedict;
-}
-moveclip_t;
-
-
 /*
 ===============================================================================
 
@@ -116,18 +113,20 @@ ENTITY AREA CHECKING
 
 typedef struct areanode_s
 {
-       int             axis;           // -1 = leaf node
-       float   dist;
-       struct areanode_s       *children[2];
-       link_t  trigger_edicts;
-       link_t  solid_edicts;
-} areanode_t;
+       // -1 = leaf node
+       int axis;
+       float dist;
+       struct areanode_s *children[2];
+       link_t trigger_edicts;
+       link_t solid_edicts;
+}
+areanode_t;
 
-#define        AREA_DEPTH      10
-#define        AREA_NODES      (1 << (AREA_DEPTH + 1))
+#define AREA_DEPTH 1
+#define AREA_NODES (1 << (AREA_DEPTH + 1))
 
-static areanode_t      sv_areanodes[AREA_NODES];
-static int                     sv_numareanodes;
+static areanode_t sv_areanodes[AREA_NODES];
+static int sv_numareanodes;
 
 /*
 ===============
@@ -137,9 +136,8 @@ SV_CreateAreaNode
 */
 areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
 {
-       areanode_t      *anode;
-       vec3_t          size;
-       vec3_t          mins1, maxs1, mins2, maxs2;
+       areanode_t *anode;
+       vec3_t size, mins1, maxs1, mins2, maxs2;
 
        anode = &sv_areanodes[sv_numareanodes];
        sv_numareanodes++;
@@ -174,6 +172,33 @@ areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
        return anode;
 }
 
+typedef struct areagrid_s
+{
+       link_t trigger_edicts;
+       link_t solid_edicts;
+}
+areagrid_t;
+
+#define AREA_GRID 32
+#define AREA_GRIDNODES (AREA_GRID * AREA_GRID)
+
+static areagrid_t sv_areagrid[AREA_GRIDNODES];
+static vec3_t sv_areagridbias, sv_areagridscale;
+
+void SV_CreateAreaGrid (vec3_t mins, vec3_t maxs)
+{
+       int i;
+       VectorNegate(mins, sv_areagridbias);
+       sv_areagridscale[0] = AREA_GRID / (maxs[0] + sv_areagridbias[0]);
+       sv_areagridscale[1] = AREA_GRID / (maxs[1] + sv_areagridbias[1]);
+       sv_areagridscale[2] = AREA_GRID / (maxs[2] + sv_areagridbias[2]);
+       for (i = 0;i < AREA_GRIDNODES;i++)
+       {
+               ClearLink (&sv_areagrid[i].trigger_edicts);
+               ClearLink (&sv_areagrid[i].solid_edicts);
+       }
+}
+
 /*
 ===============
 SV_ClearWorld
@@ -182,10 +207,11 @@ SV_ClearWorld
 */
 void SV_ClearWorld (void)
 {
-       memset (sv_areanodes, 0, sizeof(sv_areanodes));
+       memset(sv_areanodes, 0, sizeof(sv_areanodes));
        sv_numareanodes = 0;
        Mod_CheckLoaded(sv.worldmodel);
-       SV_CreateAreaNode (0, sv.worldmodel->normalmins, sv.worldmodel->normalmaxs);
+       SV_CreateAreaNode(0, sv.worldmodel->normalmins, sv.worldmodel->normalmaxs);
+       SV_CreateAreaGrid(sv.worldmodel->normalmins, sv.worldmodel->normalmaxs);
 }
 
 
@@ -197,23 +223,33 @@ SV_UnlinkEdict
 */
 void SV_UnlinkEdict (edict_t *ent)
 {
-       if (!ent->area.prev)
-               return;         // not linked in anywhere
-       RemoveLink (&ent->area);
-       ent->area.prev = ent->area.next = NULL;
+       int i;
+       for (i = 0;i < ENTITYGRIDAREAS;i++)
+       {
+               if (ent->areagrid[i].prev)
+               {
+                       RemoveLink (&ent->areagrid[i]);
+                       ent->areagrid[i].prev = ent->areagrid[i].next = NULL;
+               }
+       }
+       if (ent->area.prev)
+       {
+               RemoveLink (&ent->area);
+               ent->area.prev = ent->area.next = NULL;
+       }
 }
 
 
 /*
 ====================
-SV_TouchLinks
+SV_TouchAreaNodes
 ====================
 */
-void SV_TouchLinks ( edict_t *ent, areanode_t *node )
+void SV_TouchAreaNodes ( edict_t *ent, areanode_t *node )
 {
-       link_t          *l, *next;
-       edict_t         *touch;
-       int                     old_self, old_other;
+       link_t *l, *next;
+       edict_t *touch;
+       int old_self, old_other;
 
 loc0:
 // touch linked edicts
@@ -251,7 +287,7 @@ loc0:
        if (ent->v->absmax[node->axis] > node->dist)
        {
                if (ent->v->absmin[node->axis] < node->dist)
-                       SV_TouchLinks(ent, node->children[1]); // order reversed to reduce code
+                       SV_TouchAreaNodes(ent, node->children[1]); // order reversed to reduce code
                node = node->children[0];
                goto loc0;
        }
@@ -265,6 +301,114 @@ loc0:
        }
 }
 
+void SV_TouchAreaGrid(edict_t *ent, areanode_t *node)
+{
+       link_t *l, *next;
+       edict_t *touch;
+       areagrid_t *grid;
+       int old_self, old_other, igrid[3], igridmins[3], igridmaxs[3];
+
+       igridmins[0] = (int) ((ent->v->absmin[0] + sv_areagridbias[0]) * sv_areagridscale[0]);
+       igridmins[1] = (int) ((ent->v->absmin[1] + sv_areagridbias[1]) * sv_areagridscale[1]);
+       //igridmins[2] = (int) ((ent->v->absmin[2] + sv_areagridbias[2]) * sv_areagridscale[2]);
+       igridmaxs[0] = (int) ((ent->v->absmax[0] + sv_areagridbias[0]) * sv_areagridscale[0]) + 1;
+       igridmaxs[1] = (int) ((ent->v->absmax[1] + sv_areagridbias[1]) * sv_areagridscale[1]) + 1;
+       //igridmaxs[2] = (int) ((ent->v->absmax[2] + sv_areagridbias[2]) * sv_areagridscale[2]) + 1;
+       igridmins[0] = max(0, igridmins[0]);
+       igridmins[1] = max(0, igridmins[1]);
+       //igridmins[2] = max(0, igridmins[2]);
+       igridmaxs[0] = min(AREA_GRID, igridmaxs[0]);
+       igridmaxs[1] = min(AREA_GRID, igridmaxs[1]);
+       //igridmaxs[2] = min(AREA_GRID, igridmaxs[2]);
+
+       for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++)
+       {
+               grid = sv_areagrid + igrid[1] * AREA_GRID + igridmins[0];
+               for (igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++)
+               {
+                       for (l = grid->trigger_edicts.next;l != &grid->trigger_edicts;l = next)
+                       {
+                               next = l->next;
+                               touch = EDICT_FROM_AREA(l);
+                               if (touch == ent)
+                                       continue;
+                               if (!touch->v->touch || touch->v->solid != SOLID_TRIGGER)
+                                       continue;
+                               if (ent->v->absmin[0] > touch->v->absmax[0]
+                                || ent->v->absmin[1] > touch->v->absmax[1]
+                                || ent->v->absmin[2] > touch->v->absmax[2]
+                                || ent->v->absmax[0] < touch->v->absmin[0]
+                                || ent->v->absmax[1] < touch->v->absmin[1]
+                                || ent->v->absmax[2] < touch->v->absmin[2])
+                                       continue;
+                               old_self = pr_global_struct->self;
+                               old_other = pr_global_struct->other;
+
+                               pr_global_struct->self = EDICT_TO_PROG(touch);
+                               pr_global_struct->other = EDICT_TO_PROG(ent);
+                               pr_global_struct->time = sv.time;
+                               PR_ExecuteProgram (touch->v->touch, "");
+
+                               pr_global_struct->self = old_self;
+                               pr_global_struct->other = old_other;
+                       }
+               }
+       }
+}
+
+void SV_LinkEdict_AreaNode(edict_t *ent)
+{
+       areanode_t *node;
+       // find the first node that the ent's box crosses
+       node = sv_areanodes;
+       while (1)
+       {
+               if (node->axis == -1)
+                       break;
+               if (ent->v->absmin[node->axis] > node->dist)
+                       node = node->children[0];
+               else if (ent->v->absmax[node->axis] < node->dist)
+                       node = node->children[1];
+               else
+                       break;          // crosses the node
+       }
+
+       // link it in
+
+       if (ent->v->solid == SOLID_TRIGGER)
+               InsertLinkBefore (&ent->area, &node->trigger_edicts, ent);
+       else
+               InsertLinkBefore (&ent->area, &node->solid_edicts, ent);
+}
+
+int SV_LinkEdict_AreaGrid(edict_t *ent)
+{
+       areagrid_t *grid;
+       int igrid[3], igridmins[3], igridmaxs[3], gridnum;
+
+       igridmins[0] = (int) ((ent->v->absmin[0] + sv_areagridbias[0]) * sv_areagridscale[0]);
+       igridmins[1] = (int) ((ent->v->absmin[1] + sv_areagridbias[1]) * sv_areagridscale[1]);
+       //igridmins[2] = (int) ((ent->v->absmin[2] + sv_areagridbias[2]) * sv_areagridscale[2]);
+       igridmaxs[0] = (int) ((ent->v->absmax[0] + sv_areagridbias[0]) * sv_areagridscale[0]) + 1;
+       igridmaxs[1] = (int) ((ent->v->absmax[1] + sv_areagridbias[1]) * sv_areagridscale[1]) + 1;
+       //igridmaxs[2] = (int) ((ent->v->absmax[2] + sv_areagridbias[2]) * sv_areagridscale[2]) + 1;
+       if (igridmins[0] < 0 || igridmaxs[0] > AREA_GRID || igridmins[1] < 0 || igridmaxs[1] > AREA_GRID || ((igridmaxs[0] - igridmins[0]) * (igridmaxs[1] - igridmins[1])) > ENTITYGRIDAREAS)
+               return false;
+
+       gridnum = 0;
+       for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++)
+       {
+               grid = sv_areagrid + igrid[1] * AREA_GRID + igridmins[0];
+               for (igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++, gridnum++)
+               {
+                       if (ent->v->solid == SOLID_TRIGGER)
+                               InsertLinkBefore (&ent->areagrid[gridnum], &grid->trigger_edicts, ent);
+                       else
+                               InsertLinkBefore (&ent->areagrid[gridnum], &grid->solid_edicts, ent);
+               }
+       }
+       return true;
+}
 
 /*
 ===============
@@ -274,10 +418,9 @@ SV_LinkEdict
 */
 void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
 {
-       model_t         *model;
-       areanode_t      *node;
+       model_t *model;
 
-       if (ent->area.prev)
+       if (ent->area.prev || ent->areagrid[0].prev)
                SV_UnlinkEdict (ent);   // unlink from old position
 
        if (ent == sv.edicts)
@@ -317,14 +460,14 @@ void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
                else
                {
                        // SOLID_BSP with no model is valid, mainly because some QC setup code does so temporarily
-                       VectorAdd (ent->v->origin, ent->v->mins, ent->v->absmin);
-                       VectorAdd (ent->v->origin, ent->v->maxs, ent->v->absmax);
+                       VectorAdd(ent->v->origin, ent->v->mins, ent->v->absmin);
+                       VectorAdd(ent->v->origin, ent->v->maxs, ent->v->absmax);
                }
        }
        else
        {
-               VectorAdd (ent->v->origin, ent->v->mins, ent->v->absmin);
-               VectorAdd (ent->v->origin, ent->v->maxs, ent->v->absmax);
+               VectorAdd(ent->v->origin, ent->v->mins, ent->v->absmin);
+               VectorAdd(ent->v->origin, ent->v->maxs, ent->v->absmax);
        }
 
 //
@@ -355,30 +498,16 @@ void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
        if (ent->v->solid == SOLID_NOT)
                return;
 
-// find the first node that the ent's box crosses
-       node = sv_areanodes;
-       while (1)
-       {
-               if (node->axis == -1)
-                       break;
-               if (ent->v->absmin[node->axis] > node->dist)
-                       node = node->children[0];
-               else if (ent->v->absmax[node->axis] < node->dist)
-                       node = node->children[1];
-               else
-                       break;          // crosses the node
-       }
-
-// link it in
-
-       if (ent->v->solid == SOLID_TRIGGER)
-               InsertLinkBefore (&ent->area, &node->trigger_edicts);
-       else
-               InsertLinkBefore (&ent->area, &node->solid_edicts);
+       // try to link into areagrid, if that fails fall back on areanode
+       if (!SV_LinkEdict_AreaGrid(ent))
+               SV_LinkEdict_AreaNode(ent);
 
 // if touch_triggers, touch all entities at this node and descend for more
        if (touch_triggers)
-               SV_TouchLinks ( ent, sv_areanodes );
+       {
+               SV_TouchAreaNodes(ent, sv_areanodes);
+               SV_TouchAreaGrid(ent, sv_areanodes);
+       }
 }
 
 
@@ -458,16 +587,16 @@ trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t max
 
 /*
 ====================
-SV_ClipToLinks
+SV_ClipToAreaNodes
 
 Mins and maxs enclose the entire area swept by the move
 ====================
 */
-void SV_ClipToLinks ( areanode_t *node, moveclip_t *clip )
+void SV_ClipToAreaNodes ( areanode_t *node, moveclip_t *clip )
 {
-       link_t          *l, *next;
-       edict_t         *touch;
-       trace_t         trace;
+       link_t *l, *next;
+       edict_t *touch;
+       trace_t trace;
 
 loc0:
        if (clip->trace.allsolid)
@@ -550,7 +679,7 @@ loc0:
        if (clip->boxmaxs[node->axis] > node->dist)
        {
                if (clip->boxmins[node->axis] < node->dist)
-                       SV_ClipToLinks(node->children[1], clip);
+                       SV_ClipToAreaNodes(node->children[1], clip);
                node = node->children[0];
                goto loc0;
        }
@@ -561,6 +690,117 @@ loc0:
        }
 }
 
+/*
+====================
+SV_ClipToAreaGrid
+
+Mins and maxs enclose the entire area swept by the move
+====================
+*/
+void SV_ClipToAreaGrid(moveclip_t *clip)
+{
+       link_t *l, *next;
+       edict_t *touch;
+       areagrid_t *grid;
+       int igrid[3], igridmins[3], igridmaxs[3];
+       trace_t trace;
+
+       if (clip->trace.allsolid)
+               return;
+
+       igridmins[0] = (int) ((clip->boxmins[0] + sv_areagridbias[0]) * sv_areagridscale[0]);
+       igridmins[1] = (int) ((clip->boxmins[1] + sv_areagridbias[1]) * sv_areagridscale[1]);
+       //igridmins[2] = (int) ((clip->boxmins[2] + sv_areagridbias[2]) * sv_areagridscale[2]);
+       igridmaxs[0] = (int) ((clip->boxmaxs[0] + sv_areagridbias[0]) * sv_areagridscale[0]) + 1;
+       igridmaxs[1] = (int) ((clip->boxmaxs[1] + sv_areagridbias[1]) * sv_areagridscale[1]) + 1;
+       //igridmaxs[2] = (int) ((clip->boxmaxs[2] + sv_areagridbias[2]) * sv_areagridscale[2]) + 1;
+       igridmins[0] = max(0, igridmins[0]);
+       igridmins[1] = max(0, igridmins[1]);
+       //igridmins[2] = max(0, igridmins[2]);
+       igridmaxs[0] = min(AREA_GRID, igridmaxs[0]);
+       igridmaxs[1] = min(AREA_GRID, igridmaxs[1]);
+       //igridmaxs[2] = min(AREA_GRID, igridmaxs[2]);
+
+       for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++)
+       {
+               grid = sv_areagrid + igrid[1] * AREA_GRID + igridmins[0];
+               for (igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++)
+               {
+                       for (l = grid->solid_edicts.next;l != &grid->solid_edicts;l = next)
+                       {
+                               next = l->next;
+                               touch = EDICT_FROM_AREA(l);
+                               if (touch->v->solid == SOLID_NOT)
+                                       continue;
+                               if (touch == clip->passedict)
+                                       continue;
+                               if (touch->v->solid == SOLID_TRIGGER)
+                               {
+                                       ED_Print(touch);
+                                       Host_Error ("Trigger in clipping list");
+                               }
+
+                               if (clip->type == MOVE_NOMONSTERS && touch->v->solid != SOLID_BSP)
+                                       continue;
+
+                               if (clip->boxmins[0] > touch->v->absmax[0]
+                                || clip->boxmaxs[0] < touch->v->absmin[0]
+                                || clip->boxmins[1] > touch->v->absmax[1]
+                                || clip->boxmaxs[1] < touch->v->absmin[1]
+                                || clip->boxmins[2] > touch->v->absmax[2]
+                                || clip->boxmaxs[2] < touch->v->absmin[2])
+                                       continue;
+
+                               if (clip->passedict)
+                               {
+                                       if (clip->passedict->v->size[0] && !touch->v->size[0])
+                                               continue;       // points never interact
+                                       if (PROG_TO_EDICT(touch->v->owner) == clip->passedict)
+                                               continue;       // don't clip against own missiles
+                                       if (PROG_TO_EDICT(clip->passedict->v->owner) == touch)
+                                               continue;       // don't clip against owner
+                                       // LordHavoc: corpse code
+                                       if (clip->passedict->v->solid == SOLID_CORPSE && (touch->v->solid == SOLID_SLIDEBOX || touch->v->solid == SOLID_CORPSE))
+                                               continue;
+                                       if (clip->passedict->v->solid == SOLID_SLIDEBOX && touch->v->solid == SOLID_CORPSE)
+                                               continue;
+                               }
+
+                               // might interact, so do an exact clip
+                               if (touch->v->solid == SOLID_BSP)
+                                       trace = SV_ClipMoveToEntity (touch, clip->start, clip->hullmins, clip->hullmaxs, clip->end);
+                               else if ((int)touch->v->flags & FL_MONSTER)
+                                       trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins2, clip->maxs2, clip->end);
+                               else
+                                       trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins, clip->maxs, clip->end);
+                               // LordHavoc: take the 'best' answers from the new trace and combine with existing data
+                               if (trace.allsolid)
+                                       clip->trace.allsolid = true;
+                               if (trace.startsolid)
+                               {
+                                       clip->trace.startsolid = true;
+                                       if (!clip->trace.ent)
+                                               clip->trace.ent = trace.ent;
+                               }
+                               if (trace.inopen)
+                                       clip->trace.inopen = true;
+                               if (trace.inwater)
+                                       clip->trace.inwater = true;
+                               if (trace.fraction < clip->trace.fraction)
+                               {
+                                       clip->trace.fraction = trace.fraction;
+                                       VectorCopy(trace.endpos, clip->trace.endpos);
+                                       clip->trace.plane = trace.plane;
+                                       clip->trace.endcontents = trace.endcontents;
+                                       clip->trace.ent = trace.ent;
+                               }
+                               if (clip->trace.allsolid)
+                                       return;
+                       }
+               }
+       }
+}
+
 
 /*
 ==================
@@ -646,7 +886,8 @@ trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, e
        // create the bounding box of the entire move
        SV_MoveBounds ( start, bigmins, bigmaxs, end, clip.boxmins, clip.boxmaxs );
 
-       SV_ClipToLinks ( sv_areanodes, &clip );
+       SV_ClipToAreaNodes(sv_areanodes, &clip);
+       SV_ClipToAreaGrid(&clip);
 
        return clip.trace;
 }