Extending Quake Limits - Part 2: efrags

[mh]

For part 2 of our series we're going to remove the limit on the number of efrags. This is a required step for part 1 (static entities) as static entities will use efrags, so with unlimited static entities we're going to run out of efrags quite soon.

Concept

What's an efrag? At the most basic level it's just a marker that an entity (either static or not) is currently inhabiting a certain leaf in the world. GLQuake uses them for just static entities whereas software Quake uses them for both types.

The default efrags limit is a piddling 640, and we're going to go through the roof here and get rid of it entirely.

This code will work with both software and GLQuake.

The code

Before we start writing any code, the differences in the two engines means that there are two different code files that handle efrags: gl_refrag.c for GLQuake and r_efrag.c for software Quake. Look at the two files, observe that there's only fairly minor differences between them, observe that the additional code in r_efrag.c has no impact whatsoever on GLQuake.

You could just use r_efrag.c for both, or you could keep them separate if you wish, or you may only maintain one of software or GLQuake. It's entirely up to you, but the code changes are identical for both versions.

On to the code. Open up your chosen efrags file and add this at the top:

Code: Select all

// mh - extended efrags - begin
#define EXTRA_EFRAGS	32

void R_GetMoreEfrags (void)
{
	int i;

	cl.free_efrags = (efrag_t *) Hunk_Alloc (EXTRA_EFRAGS * sizeof (efrag_t));

	for (i = 0; i < EXTRA_EFRAGS - 1; i++)
		cl.free_efrags[i].entnext = &cl.free_efrags[i + 1];

	cl.free_efrags[i].entnext = NULL;
}
// mh - extended efrags - end

Now look for the R_SplitEntityOnNode function, look for the block that begins with "if (!ef)", and replace the contents of that block with this:

Code: Select all

		if (!ef)
		{
			// mh - extended efrags - begin
			R_GetMoreEfrags ();
			ef = cl.free_efrags;
			// mh - extended efrags - end
		}

And that's all that's required. What's going on here is that we're actually keeping the original MAX_EFRAGS array as an initial block that's set up when the client starts. If that block gets exhausted we'll just allocate some more. The extra amount doesn't really matter, I just chose 32 so that we don't have potentially lots of runtime memory allocations and also so that we're not wasting memory by allocating too many. Once again it comes off the hunk so it's automatically released between map loads.

What's really nice about this extension is that it can quite easily be tested by setting your value of MAX_EFRAGS to something like 2, adding a Con_Printf to R_GetMoreEfrags, and just running a map.

Cleaning up

There's not much to be done here to be honest. You might like to change the name of MAX_EFRAGS to something like INITIAL_EFRAGS and maybe even reduce it's value (so that you're not wasting memory on efrags you may not need), or you might like to remove it entirely, set cl.free_efrags to NULL (instead of to cl_efrags) in your CL_ClearState function, and let R_GetMoreEfrags do all the work.

I would have constructed this tutorial around the last way but I like to keep all code-changes in a single file if at all possible.

A Note on Memory Usage

With both this tutorial and with my previous one we're allocating extra objects off the Hunk which will put some pressure on the memory Quake has available to run in. You should either increase the default heapsize a little or use my Quake Memory Manager tutorials (or similar) to avoid any issues from this.

The bottom line though is that the memory for the extra objects has to come from somewhere, and the Hunk is convenient as it is cleared automatically between map loads and will handle error checking for us.

[metlslime]

I was under the impression, when i last went through this code, that you could get rid of efrags entirely and just do client-side PVS checks for each static entity whenever the camera crossed a leaf boundary. That would simplify the code with a negligible performance hit.

On the other hand, I realize this tutorial is for software mode too, so you actually still need the efrags in that case.

[mh]

I was under the impression, when i last went through this code, that you could get rid of efrags entirely and just do client-side PVS checks for each static entity whenever the camera crossed a leaf boundary. That would simplify the code with a negligible performance hit.

On the other hand, I realize this tutorial is for software mode too, so you actually still need the efrags in that case.

Quite correct in both cases.

The approach I use is to store a list of static entities in each leaf that each such entity touches, and if the leaf is in the PVS then so are all of the statics in it.

[revelator]

i believe tochris also uses a different approach for efrags as the code is completly missing ?

instead theres a pvs calculating function in gl_rmain.

tbh if someone was to go about creating an engine from scratch (allmost) tochris might be a very nice starting point. the differences to normal quake
might be a little hard to cope with unless you have a lot of experience though.

mainly the client / server model of the code.

on the good side it includes the software renderer for those who require this still.

[dreadlorde]

I'm having trouble with this, when I compile this with gcc-4.3.3, I get this error

Code: Select all

home/jake/src/proj/quake-git/r_efrag.c
/home/jake/src/proj/quake-git/r_efrag.c: In function ‘R_GetMoreEfrags’:
/home/jake/src/proj/quake-git/r_efrag.c:16: error: incompatible types in assignment
make[1]: *** [release/x11/r_efrag.o] Error 1
make[1]: Leaving directory `/home/jake/tmp/quake-git'
make: *** [release] Error 2

Where line 16 is

Code: Select all

cl.free_efrags[i].entnext[i] = NULL;

I'm not sure what to do. :?

[mh]

It should be:

Code: Select all

cl.free_efrags[i].entnext = NULL;

Note the lack of an "" after "entnext".

[dreadlorde]

It should be:

Code: Select all

cl.free_efrags[i].entnext = NULL;

Note the lack of an "" after "entnext".

Doh!

You changed it when I wasn't here!!

[mh]

Just a quick note that with GLQuake you don't actually need to maintain the free efrags list at all, and can just Hunk_alloc a new efrag as required. This is possible because GLQuake only uses efrags for static entities, which are never moved or freed in-game. Software Quake is different, of course.

It's also the case that with GLQuake you don't really need efrags at all, but they are handy for maintaining a record of which leafs a static entity is in (particularly if you also remove the limit on static entities and therefore don't have an array of them to refer to).