got rid of AreaNode stuff, now only has AreaGrid (had to add sv_areagrid_outside...
authorhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Fri, 7 Mar 2003 09:30:21 +0000 (09:30 +0000)
committerhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Fri, 7 Mar 2003 09:30:21 +0000 (09:30 +0000)
renamed sv_useareanodes to sv_debugmove (inverted behavior)
SV_CreateAreaGrid now has a minimum grid size (sv_areagrid_mingridsize cvar), this greatly improved performance in helm18
SV_ClipToAreaGrid and SV_TouchAreaGrid no longer process any edicts twice (edict_t now has areagridmarknumber for this purpose)
increased AREA_GRID from 16 to 512
added SV_ClipToNode function to get rid of duplicate code in SV_ClipToAreaGrid

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

progs.h
world.c

diff --git a/progs.h b/progs.h
index 6d3fb99..f9d1bde 100644 (file)
--- a/progs.h
+++ b/progs.h
@@ -48,10 +48,11 @@ typedef struct edict_s
 {
        // true if this edict is unused
        qboolean free;
-       // physics area this edict is linked into
-       link_t area;
        // physics grid areas this edict is linked into
        link_t areagrid[ENTITYGRIDAREAS];
+       // since the areagrid can have multiple references to one entity,
+       // we should avoid extensive checking on entities already encountered
+       int areagridmarknumber;
 
        // old entity protocol, not used
 #ifdef QUAKEENTITIES
diff --git a/world.c b/world.c
index 6a7a1a5..de5df5c 100644 (file)
--- a/world.c
+++ b/world.c
@@ -29,13 +29,18 @@ line of sight checks trace->inopen and trace->inwater, but bullets don't
 
 */
 
-cvar_t sv_useareanodes = {CVAR_NOTIFY, "sv_useareanodes", "1"};
+cvar_t sv_debugmove = {CVAR_NOTIFY, "sv_debugmove", "0"};
 cvar_t sv_polygoncollisions = {CVAR_NOTIFY, "sv_polygoncollisions", "0"};
+cvar_t sv_areagrid_mingridsize = {CVAR_NOTIFY, "sv_areagrid_mingridsize", "64"};
+
+void SV_AreaStats_f(void);
 
 void SV_World_Init(void)
 {
-       Cvar_RegisterVariable(&sv_useareanodes);
+       Cvar_RegisterVariable(&sv_debugmove);
        Cvar_RegisterVariable(&sv_polygoncollisions);
+       Cvar_RegisterVariable(&sv_areagrid_mingridsize);
+       Cmd_AddCommand("sv_areastats", SV_AreaStats_f);
        Collision_Init();
 }
 
@@ -111,65 +116,16 @@ ENTITY AREA CHECKING
 ===============================================================================
 */
 
-typedef struct areanode_s
-{
-       // -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 1
-#define AREA_NODES (1 << (AREA_DEPTH + 1))
+int sv_areagrid_stats_calls = 0;
+int sv_areagrid_stats_nodechecks = 0;
+int sv_areagrid_stats_entitychecks = 0;
 
-static areanode_t sv_areanodes[AREA_NODES];
-static int sv_numareanodes;
-
-/*
-===============
-SV_CreateAreaNode
-
-===============
-*/
-areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
+void SV_AreaStats_f(void)
 {
-       areanode_t *anode;
-       vec3_t size, mins1, maxs1, mins2, maxs2;
-
-       anode = &sv_areanodes[sv_numareanodes];
-       sv_numareanodes++;
-
-       ClearLink (&anode->trigger_edicts);
-       ClearLink (&anode->solid_edicts);
-
-       if (depth == AREA_DEPTH)
-       {
-               anode->axis = -1;
-               anode->children[0] = anode->children[1] = NULL;
-               return anode;
-       }
-
-       VectorSubtract (maxs, mins, size);
-       if (size[0] > size[1])
-               anode->axis = 0;
-       else
-               anode->axis = 1;
-
-       anode->dist = 0.5 * (maxs[anode->axis] + mins[anode->axis]);
-       VectorCopy (mins, mins1);
-       VectorCopy (mins, mins2);
-       VectorCopy (maxs, maxs1);
-       VectorCopy (maxs, maxs2);
-
-       maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
-
-       anode->children[0] = SV_CreateAreaNode (depth+1, mins2, maxs2);
-       anode->children[1] = SV_CreateAreaNode (depth+1, mins1, maxs1);
-
-       return anode;
+       Con_Printf("areagrid check stats: %d calls %d nodes (%f per call) %d entities (%f per call)\n", sv_areagrid_stats_calls, sv_areagrid_stats_nodechecks, (double) sv_areagrid_stats_nodechecks / (double) sv_areagrid_stats_calls, sv_areagrid_stats_entitychecks, (double) sv_areagrid_stats_entitychecks / (double) sv_areagrid_stats_calls);
+       sv_areagrid_stats_calls = 0;
+       sv_areagrid_stats_nodechecks = 0;
+       sv_areagrid_stats_entitychecks = 0;
 }
 
 typedef struct areagrid_s
@@ -179,24 +135,40 @@ typedef struct areagrid_s
 }
 areagrid_t;
 
-#define AREA_GRID 16
+#define AREA_GRID 512
 #define AREA_GRIDNODES (AREA_GRID * AREA_GRID)
 
-static areagrid_t sv_areagrid[AREA_GRIDNODES];
-static vec3_t sv_areagridbias, sv_areagridscale;
+static areagrid_t sv_areagrid[AREA_GRIDNODES], sv_areagrid_outside;
+static vec3_t sv_areagrid_bias, sv_areagrid_scale, sv_areagrid_mins, sv_areagrid_maxs, sv_areagrid_size;
+static int sv_areagrid_marknumber = 1;
 
 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]);
+       ClearLink (&sv_areagrid_outside.trigger_edicts);
+       ClearLink (&sv_areagrid_outside.solid_edicts);
+       // choose either the world box size, or a larger box to ensure the grid isn't too fine
+       sv_areagrid_size[0] = max(maxs[0] - mins[0], AREA_GRID * sv_areagrid_mingridsize.value);
+       sv_areagrid_size[1] = max(maxs[1] - mins[1], AREA_GRID * sv_areagrid_mingridsize.value);
+       sv_areagrid_size[2] = max(maxs[2] - mins[2], AREA_GRID * sv_areagrid_mingridsize.value);
+       // figure out the corners of such a box, centered at the center of the world box
+       sv_areagrid_mins[0] = (mins[0] + maxs[0] - sv_areagrid_size[0]) * 0.5f;
+       sv_areagrid_mins[1] = (mins[1] + maxs[1] - sv_areagrid_size[1]) * 0.5f;
+       sv_areagrid_mins[2] = (mins[2] + maxs[2] - sv_areagrid_size[2]) * 0.5f;
+       sv_areagrid_maxs[0] = (mins[0] + maxs[0] + sv_areagrid_size[0]) * 0.5f;
+       sv_areagrid_maxs[1] = (mins[1] + maxs[1] + sv_areagrid_size[1]) * 0.5f;
+       sv_areagrid_maxs[2] = (mins[2] + maxs[2] + sv_areagrid_size[2]) * 0.5f;
+       // now calculate the actual useful info from that
+       VectorNegate(sv_areagrid_mins, sv_areagrid_bias);
+       sv_areagrid_scale[0] = AREA_GRID / sv_areagrid_size[0];
+       sv_areagrid_scale[1] = AREA_GRID / sv_areagrid_size[1];
+       sv_areagrid_scale[2] = AREA_GRID / sv_areagrid_size[2];
        for (i = 0;i < AREA_GRIDNODES;i++)
        {
                ClearLink (&sv_areagrid[i].trigger_edicts);
                ClearLink (&sv_areagrid[i].solid_edicts);
        }
+       Con_DPrintf("sv_areagrid settings: divisions %ix%ix1 : box %f %f %f : %f %f %f size %f %f %f grid %f %f %f (mingrid %f)\n", AREA_GRID, AREA_GRID, sv_areagrid_mins[0], sv_areagrid_mins[1], sv_areagrid_mins[2], sv_areagrid_maxs[0], sv_areagrid_maxs[1], sv_areagrid_maxs[2], sv_areagrid_size[0], sv_areagrid_size[1], sv_areagrid_size[2], 1.0f / sv_areagrid_scale[0], 1.0f / sv_areagrid_scale[1], 1.0f / sv_areagrid_scale[2], sv_areagrid_mingridsize.value);
 }
 
 /*
@@ -207,10 +179,7 @@ SV_ClearWorld
 */
 void SV_ClearWorld (void)
 {
-       memset(sv_areanodes, 0, sizeof(sv_areanodes));
-       sv_numareanodes = 0;
        Mod_CheckLoaded(sv.worldmodel);
-       SV_CreateAreaNode(0, sv.worldmodel->normalmins, sv.worldmodel->normalmaxs);
        SV_CreateAreaGrid(sv.worldmodel->normalmins, sv.worldmodel->normalmaxs);
 }
 
@@ -232,42 +201,45 @@ void SV_UnlinkEdict (edict_t *ent)
                        ent->areagrid[i].prev = ent->areagrid[i].next = NULL;
                }
        }
-       if (ent->area.prev)
-       {
-               RemoveLink (&ent->area);
-               ent->area.prev = ent->area.next = NULL;
-       }
 }
 
 
-/*
-====================
-SV_TouchAreaNodes
-====================
-*/
-void SV_TouchAreaNodes ( edict_t *ent, areanode_t *node )
+void SV_TouchAreaGrid(edict_t *ent)
 {
        link_t *l, *next;
        edict_t *touch;
-       int old_self, old_other;
+       areagrid_t *grid;
+       int old_self, old_other, igrid[3], igridmins[3], igridmaxs[3];
 
-loc0:
-// touch linked edicts
-       for (l = node->trigger_edicts.next ; l != &node->trigger_edicts ; l = next)
+       sv_areagrid_marknumber++;
+       igridmins[0] = (int) ((ent->v->absmin[0] + sv_areagrid_bias[0]) * sv_areagrid_scale[0]);
+       igridmins[1] = (int) ((ent->v->absmin[1] + sv_areagrid_bias[1]) * sv_areagrid_scale[1]);
+       //igridmins[2] = (int) ((ent->v->absmin[2] + sv_areagrid_bias[2]) * sv_areagrid_scale[2]);
+       igridmaxs[0] = (int) ((ent->v->absmax[0] + sv_areagrid_bias[0]) * sv_areagrid_scale[0]) + 1;
+       igridmaxs[1] = (int) ((ent->v->absmax[1] + sv_areagrid_bias[1]) * sv_areagrid_scale[1]) + 1;
+       //igridmaxs[2] = (int) ((ent->v->absmax[2] + sv_areagrid_bias[2]) * sv_areagrid_scale[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 (l = sv_areagrid_outside.trigger_edicts.next;l != &sv_areagrid_outside.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->absmin[1] > touch->v->absmax[1]
                 || ent->v->absmax[1] < touch->v->absmin[1]
+                || ent->v->absmin[2] > touch->v->absmax[2]
                 || ent->v->absmax[2] < touch->v->absmin[2])
                        continue;
+               if (touch == ent)
+                       continue;
+               if (!touch->v->touch || touch->v->solid != SOLID_TRIGGER)
+                       continue;
                old_self = pr_global_struct->self;
                old_other = pr_global_struct->other;
 
@@ -280,47 +252,6 @@ loc0:
                pr_global_struct->other = old_other;
        }
 
-// recurse down both sides
-       if (node->axis == -1)
-               return;
-
-       if (ent->v->absmax[node->axis] > node->dist)
-       {
-               if (ent->v->absmin[node->axis] < node->dist)
-                       SV_TouchAreaNodes(ent, node->children[1]); // order reversed to reduce code
-               node = node->children[0];
-               goto loc0;
-       }
-       else
-       {
-               if (ent->v->absmin[node->axis] < node->dist)
-               {
-                       node = node->children[1];
-                       goto 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];
@@ -330,17 +261,20 @@ void SV_TouchAreaGrid(edict_t *ent, areanode_t *node)
                        {
                                next = l->next;
                                touch = EDICT_FROM_AREA(l);
-                               if (touch == ent)
-                                       continue;
-                               if (!touch->v->touch || touch->v->solid != SOLID_TRIGGER)
+                               if (touch->areagridmarknumber == sv_areagrid_marknumber)
                                        continue;
+                               touch->areagridmarknumber = sv_areagrid_marknumber;
                                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->absmin[1] > touch->v->absmax[1]
                                 || ent->v->absmax[1] < touch->v->absmin[1]
+                                || ent->v->absmin[2] > touch->v->absmax[2]
                                 || ent->v->absmax[2] < touch->v->absmin[2])
                                        continue;
+                               if (touch == ent)
+                                       continue;
+                               if (!touch->v->touch || touch->v->solid != SOLID_TRIGGER)
+                                       continue;
                                old_self = pr_global_struct->self;
                                old_other = pr_global_struct->other;
 
@@ -356,44 +290,26 @@ void SV_TouchAreaGrid(edict_t *ent, areanode_t *node)
        }
 }
 
-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)
+void 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;
+       igridmins[0] = (int) ((ent->v->absmin[0] + sv_areagrid_bias[0]) * sv_areagrid_scale[0]);
+       igridmins[1] = (int) ((ent->v->absmin[1] + sv_areagrid_bias[1]) * sv_areagrid_scale[1]);
+       //igridmins[2] = (int) ((ent->v->absmin[2] + sv_areagrid_bias[2]) * sv_areagrid_scale[2]);
+       igridmaxs[0] = (int) ((ent->v->absmax[0] + sv_areagrid_bias[0]) * sv_areagrid_scale[0]) + 1;
+       igridmaxs[1] = (int) ((ent->v->absmax[1] + sv_areagrid_bias[1]) * sv_areagrid_scale[1]) + 1;
+       //igridmaxs[2] = (int) ((ent->v->absmax[2] + sv_areagrid_bias[2]) * sv_areagrid_scale[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;
+       {
+               // wow, something outside the grid, store it as such
+               if (ent->v->solid == SOLID_TRIGGER)
+                       InsertLinkBefore (&ent->areagrid[0], &sv_areagrid_outside.trigger_edicts, ent);
+               else
+                       InsertLinkBefore (&ent->areagrid[0], &sv_areagrid_outside.solid_edicts, ent);
+               return;
+       }
 
        gridnum = 0;
        for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++)
@@ -407,7 +323,6 @@ int SV_LinkEdict_AreaGrid(edict_t *ent)
                                InsertLinkBefore (&ent->areagrid[gridnum], &grid->solid_edicts, ent);
                }
        }
-       return true;
 }
 
 /*
@@ -420,7 +335,7 @@ void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
 {
        model_t *model;
 
-       if (ent->area.prev || ent->areagrid[0].prev)
+       if (ent->areagrid[0].prev)
                SV_UnlinkEdict (ent);   // unlink from old position
 
        if (ent == sv.edicts)
@@ -498,16 +413,11 @@ void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
        if (ent->v->solid == SOLID_NOT)
                return;
 
-       // try to link into areagrid, if that fails fall back on areanode
-       if (!SV_LinkEdict_AreaGrid(ent))
-               SV_LinkEdict_AreaNode(ent);
+       SV_LinkEdict_AreaGrid(ent);
 
 // if touch_triggers, touch all entities at this node and descend for more
        if (touch_triggers)
-       {
-               SV_TouchAreaNodes(ent, sv_areanodes);
-               SV_TouchAreaGrid(ent, sv_areanodes);
-       }
+               SV_TouchAreaGrid(ent);
 }
 
 
@@ -585,39 +495,21 @@ trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t max
 
 //===========================================================================
 
-/*
-====================
-SV_ClipToAreaNodes
-
-Mins and maxs enclose the entire area swept by the move
-====================
-*/
-void SV_ClipToAreaNodes ( areanode_t *node, moveclip_t *clip )
+void SV_ClipToNode(moveclip_t *clip, link_t *list)
 {
        link_t *l, *next;
        edict_t *touch;
        trace_t trace;
 
-loc0:
-       if (clip->trace.allsolid)
-               return;
-// touch linked edicts
-       for (l = node->solid_edicts.next ; l != &node->solid_edicts ; l = next)
+       sv_areagrid_stats_nodechecks++;
+       for (l = list->next;l != list;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)
+               if (touch->areagridmarknumber == sv_areagrid_marknumber)
                        continue;
+               touch->areagridmarknumber = sv_areagrid_marknumber;
+               sv_areagrid_stats_entitychecks++;
 
                if (clip->boxmins[0] > touch->v->absmax[0]
                 || clip->boxmaxs[0] < touch->v->absmin[0]
@@ -627,11 +519,17 @@ loc0:
                 || clip->boxmaxs[2] < touch->v->absmin[2])
                        continue;
 
+               if (clip->type == MOVE_NOMONSTERS && touch->v->solid != SOLID_BSP)
+                       continue;
+
+               if (touch->v->solid == SOLID_NOT)
+                       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)
+                       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
@@ -642,6 +540,14 @@ loc0:
                                continue;
                }
 
+               if (touch == clip->passedict)
+                       continue;
+               if (touch->v->solid == SOLID_TRIGGER)
+               {
+                       ED_Print(touch);
+                       Host_Error ("Trigger in clipping list");
+               }
+
                // 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);
@@ -670,23 +576,8 @@ loc0:
                        clip->trace.endcontents = trace.endcontents;
                        clip->trace.ent = trace.ent;
                }
-       }
-
-// recurse down both sides
-       if (node->axis == -1)
-               return;
-
-       if (clip->boxmaxs[node->axis] > node->dist)
-       {
-               if (clip->boxmins[node->axis] < node->dist)
-                       SV_ClipToAreaNodes(node->children[1], clip);
-               node = node->children[0];
-               goto loc0;
-       }
-       else if (clip->boxmins[node->axis] < node->dist)
-       {
-               node = node->children[1];
-               goto loc0;
+               if (clip->trace.allsolid)
+                       return;
        }
 }
 
@@ -699,21 +590,20 @@ 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;
+       sv_areagrid_stats_calls++;
+       sv_areagrid_marknumber++;
+       igridmins[0] = (int) ((clip->boxmins[0] + sv_areagrid_bias[0]) * sv_areagrid_scale[0]);
+       igridmins[1] = (int) ((clip->boxmins[1] + sv_areagrid_bias[1]) * sv_areagrid_scale[1]);
+       //igridmins[2] = (int) ((clip->boxmins[2] + sv_areagrid_bias[2]) * sv_areagrid_scale[2]);
+       igridmaxs[0] = (int) ((clip->boxmaxs[0] + sv_areagrid_bias[0]) * sv_areagrid_scale[0]) + 1;
+       igridmaxs[1] = (int) ((clip->boxmaxs[1] + sv_areagrid_bias[1]) * sv_areagrid_scale[1]) + 1;
+       //igridmaxs[2] = (int) ((clip->boxmaxs[2] + sv_areagrid_bias[2]) * sv_areagrid_scale[2]) + 1;
        igridmins[0] = max(0, igridmins[0]);
        igridmins[1] = max(0, igridmins[1]);
        //igridmins[2] = max(0, igridmins[2]);
@@ -721,84 +611,13 @@ void SV_ClipToAreaGrid(moveclip_t *clip)
        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 (sv_areagrid_outside.solid_edicts.next != &sv_areagrid_outside.solid_edicts)
+               SV_ClipToNode(clip, &sv_areagrid_outside.solid_edicts);
 
-                               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;
-                       }
-               }
-       }
+       for (igrid[1] = igridmins[1];igrid[1] < igridmaxs[1];igrid[1]++)
+               for (grid = sv_areagrid + igrid[1] * AREA_GRID + igridmins[0], igrid[0] = igridmins[0];igrid[0] < igridmaxs[0];igrid[0]++, grid++)
+                       if (grid->solid_edicts.next != &grid->solid_edicts)
+                               SV_ClipToNode(clip, &grid->solid_edicts);
 }
 
 
@@ -809,7 +628,7 @@ SV_MoveBounds
 */
 void SV_MoveBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
 {
-       if (sv_useareanodes.integer)
+       if (!sv_debugmove.integer)
        {
                int i;
 
@@ -886,7 +705,6 @@ 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_ClipToAreaNodes(sv_areanodes, &clip);
        SV_ClipToAreaGrid(&clip);
 
        return clip.trace;