Forum

Areanodes

Post tutorials on how to do certain tasks within game or engine code here.

Moderator: InsideQC Admins

Areanodes

Postby mh » Wed Feb 22, 2017 11:21 pm

Areanodes are used by the Quake engine for entity interaction and collision detection. They are a server-side optimization to prevent each entity having to be tested against every other entity. Instead the map is partitioned into "areas", entities are placed into these areas, and only entities in the same area need be tested against each other (simplified version).

Stock Quake uses 32 areanodes; no more, no less, irrespective of the size of the map. What this means is that bigger maps will generate bigger areas, these bigger areas will have more entities in them, so the number of tests goes up and server performance goes down.

Instead of pulling areanodes from a fixed-size static array we're going to allocate them in Hunk memory. Testing all of the ID1 maps we can see that for 80% to 90% of cases they stop generating areanodes when the node size in x and y goes below about 1024. Cross-checking this final code we can confirm that in the same percentage of ID1 maps it still generates 32 areanodes, so we've confirmed that's a good and valid maximum size.

Let's go.

All code is in world.c; look for the "ENTITY AREA CHECKING" comment heading and replace the existing code under it (down to and including SV_ClearWorld) with this lot:
Code: Select all
#define AREANODE_OPTIMIZATION

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;

#define   AREA_DEPTH   4
#define   AREA_NODES   32

#ifdef AREANODE_OPTIMIZATION
static   areanode_t   *sv_areanodes = NULL;
#else
static   areanode_t   sv_areanodes[AREA_NODES];
static   int         sv_numareanodes;
#endif

/*
===============
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;

#ifdef AREANODE_OPTIMIZATION
   anode = (areanode_t *) Hunk_Alloc (sizeof (areanode_t));
#else
   anode = &sv_areanodes[sv_numareanodes];
   sv_numareanodes++;
#endif

   ClearLink (&anode->trigger_edicts);
   ClearLink (&anode->solid_edicts);

#ifdef AREANODE_OPTIMIZATION
   VectorSubtract (maxs, mins, size);

   // most id1 maps stop creating area nodes at this size
   if (size[0] < 1024 && size[1] < 1024)
   {
      anode->axis = -1;
      anode->children[0] = anode->children[1] = NULL;
      return anode;
   }
#else
   if (depth == AREA_DEPTH)
   {
      anode->axis = -1;
      anode->children[0] = anode->children[1] = NULL;
      return anode;
   }

   VectorSubtract (maxs, mins, size);
#endif

   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;
}

/*
===============
SV_ClearWorld

===============
*/
void SV_ClearWorld (void)
{
   SV_InitBoxHull ();

#ifdef AREANODE_OPTIMIZATION
   sv_areanodes = SV_CreateAreaNode (0, sv.worldmodel->mins, sv.worldmodel->maxs);
#else
   memset (sv_areanodes, 0, sizeof(sv_areanodes));
   sv_numareanodes = 0;
   SV_CreateAreaNode (0, sv.worldmodel->mins, sv.worldmodel->maxs);
#endif
}

You'll see that I've left the original code in-place but marked my changes with a #define; this way you can quickly and easily revert to the original if you have any problems.

In theory Quake servers will now run a little faster; in practice you might have other bottlenecks that prevent you seeing a measurable performance increase.
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
User avatar
mh
 
Posts: 2283
Joined: Sat Jan 12, 2008 1:38 am

Re: Areanodes

Postby frag.machine » Thu Feb 23, 2017 11:46 am

Does this have any influence on the PVS calculation and/or network traffic ? Because if you manage to significantly reduce the number of updated entities per packet the effect is more positive than a simple reduction of server CPU usage.
I know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC :) (LordHavoc)
User avatar
frag.machine
 
Posts: 2031
Joined: Sat Nov 25, 2006 1:49 pm

Re: Areanodes

Postby mh » Thu Feb 23, 2017 7:40 pm

frag.machine wrote:Does this have any influence on the PVS calculation and/or network traffic ?

Not a thing, but...

Single player games have servers too. A CPU load reduction on a 600 monster meat-grinder is anything but "simple".
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
User avatar
mh
 
Posts: 2283
Joined: Sat Jan 12, 2008 1:38 am

Re: Areanodes

Postby frag.machine » Thu Feb 23, 2017 11:26 pm

mh wrote:
frag.machine wrote:Does this have any influence on the PVS calculation and/or network traffic ?

Not a thing, but...

Single player games have servers too. A CPU load reduction on a 600 monster meat-grinder is anything but "simple".


Sorry if sounded like I was implying this was insignificant. Every improvement is always welcome, specially if it's a relatively small tutorial like this one.
I was genuinely intrigued about the potential influence this areanode structure could have in the PVS and network traffic. Maybe I ought to make some tests with a clean FitzQuake against this tutorial when I get some spare time...
I know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC :) (LordHavoc)
User avatar
frag.machine
 
Posts: 2031
Joined: Sat Nov 25, 2006 1:49 pm

Re: Areanodes

Postby mh » Fri Feb 24, 2017 12:19 pm

Not a problem. :)

I don't think you're going to see improvements with a clean Fitz because that's already very significantly CPU-bound elsewhere.
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
User avatar
mh
 
Posts: 2283
Joined: Sat Jan 12, 2008 1:38 am

Re: Areanodes

Postby revelator » Fri Feb 24, 2017 7:15 pm

"600 monster meat-grinder" surviving that sounds easy... :shock: :mrgreen:
Productivity is a state of mind.
User avatar
revelator
 
Posts: 2496
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Re: Areanodes

Postby frag.machine » Fri Feb 24, 2017 8:53 pm

mh wrote:Not a problem. :)

I don't think you're going to see improvements with a clean Fitz because that's already very significantly CPU-bound elsewhere.


Well my idea is to profile the application to have a more precise idea.
I know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC :) (LordHavoc)
User avatar
frag.machine
 
Posts: 2031
Joined: Sat Nov 25, 2006 1:49 pm

Re: Areanodes

Postby Spike » Fri Feb 24, 2017 10:03 pm

there's two sorts of map that come to mind... and an issue with areanodes in general.
1) helm18... 10000 knights all crammed into a small space. such maps will generally require more nodes...
2) maaaaasive terrain-based maps with so much empty space combined with areas of densely packed entities...
3) maps that place a whole load of entities that cross the top-level boundary and thus all fill up the root areanode and are clipped against in every single trace anywhere on the map...
Spike
 
Posts: 2853
Joined: Fri Nov 05, 2004 3:12 am
Location: UK


Return to Programming Tutorials

Who is online

Users browsing this forum: No registered users and 1 guest