Extending Quake Limits - Part 1: Static Entities

Post tutorials on how to do certain tasks within game or engine code here.
Post Reply
mh
Posts: 2292
Joined: Sat Jan 12, 2008 1:38 am

Extending Quake Limits - Part 1: Static Entities

Post by mh »

We all know that Quake has some quite annoying built-in limits, so let's deal with some of them. I don't think I've ever seen any practical tutorials on extending limits, and it's time to put that right.

Hopefully this will be part 1 of an extended - but quite irregular - series, and hopefully other people will also join in.

For part 1 we're going to do static entities, probably the easiest of them all, but with a time-bomb to catch the unwary.

Concept

A static entity is sent from QC to the client when the server spawns, and from that point onwards it lives only on the client. The server doesn't know about it, the server doesn't care about it, the server cannot interact with it. Once spawned it exists for the full lifetime of the map and nothing can remove it, not even the most agile of QC ninjas, as Quake does not provide an interface for doing anything other than spawning a static entity. A static entity is like the Duracell bunny on nuclear power.

Quake has a hard-coded maximum of 128 static entities, so let's get rid of it.

This code will work with both software and GLQuake.

The Code

Open your cl_parse.c file, find the CL_ParseStatic function, and replace it with this:

Code: Select all

void CL_ParseStatic (void)
{
	entity_t *ent;

	// mh - extended static entities begin
	ent = (entity_t *) Hunk_Alloc (sizeof (entity_t));
	CL_ParseBaseline (ent);
	// mh - extended static entities end

	// copy it to the current state
	ent->model = cl.model_precache[ent->baseline.modelindex];
	ent->frame = ent->baseline.frame;
	ent->colormap = vid.colormap;
	ent->skinnum = ent->baseline.skin;
	ent->effects = ent->baseline.effects;

	VectorCopy (ent->baseline.origin, ent->origin);
	VectorCopy (ent->baseline.angles, ent->angles);	
	R_AddEfrags (ent);
}
That's it. Easiest tutorial ever!

If you study the differences between the old and the new, you'll see that instead of pulling a new static entity from a fixed size array I am instead allocating it directly on the Hunk. This way it will be automatically free'ed between map loads, and we no longer need to worry about managing anything.

Beware!

That time bomb I mentioned earlier? It's right there in the last line - the call to R_AddEfrags. Although we no longer have a limit on the number of static entities we still have a limit on the number of efrags, and removing this requires a little bit more work. That's what I'm going to show one way of doing in the next part.

Cleaning up

We can now remove the rest of the code relating to this limit. The num_statics member from client_state_t, the MAX_STATIC_ENTITIES define and the cl_static_entities array itself.
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
mankrip
Posts: 924
Joined: Fri Jul 04, 2008 3:02 am

Re: Extending Quake Limits - Part 1: Static Entities

Post by mankrip »

mh wrote: Fri Jan 08, 2010 5:00 pm Although we no longer have a limit on the number of static entities we still have a limit on the number of efrags
I'm trying to figure out how to remove this limit. It is hit in the function R_SplitEntityOnNode, when cl.free_efrags goes full.

When the map starts, cl.free_efrags is initialized as a pointer to cl_efrags, which is a struct array defined in cl_main.c:

Code: Select all

efrag_t			cl_efrags[MAX_EFRAGS];
This array is then set up as a linked list by CL_ClearState:

Code: Select all

	cl.free_efrags = cl_efrags;
	for (i=0 ; i<MAX_EFRAGS-1 ; i++)
		cl.free_efrags[i].entnext = &cl.free_efrags[i+1];
	cl.free_efrags[i].entnext = NULL;
... which is an indication that id already wanted to use dynamically alocated linked lists to eliminate this limitation, because I don't think it makes enough sense to treat a static array as a linked list.

Anyway, what needs to be done is to turn cl.free_efrags into a dynamically alocated linked list.

A different approach would be to simply realloc the array as needed, but that would require all links to be updated, which would be slower.

I noticed that some engines doesn't have a r_efrag.c file at all, which indicates that they fully replaced the efrags system with something else.
Ph'nglui mglw'nafh mankrip Hell's end wgah'nagl fhtagn.
==-=-=-=-=-=-=-=-=-=-==
Dev blog / Twitter / YouTube
mankrip
Posts: 924
Joined: Fri Jul 04, 2008 3:02 am

Re: Extending Quake Limits - Part 1: Static Entities

Post by mankrip »

Alright, here's how to eliminate the limit of efrags.

Add this prototype above CL_ClearState:

Code: Select all

extern void CL_Init_EFrags (void);
In CL_ClearState, delete this line:

Code: Select all

	memset (cl_efrags, 0, sizeof(cl_efrags));
And replace these lines...

Code: Select all

//
// allocate the efrags and chain together into a free list
//
	cl.free_efrags = cl_efrags;
	for (i=0 ; i<MAX_EFRAGS-1 ; i++)
		cl.free_efrags[i].entnext = &cl.free_efrags[i+1];
	cl.free_efrags[i].entnext = NULL;
... with this:

Code: Select all

	CL_Init_EFrags ();
Now open r_efrag.c, and add these functions at the top:

Code: Select all

void CL_Init_EFrags (void)
{
	cl.free_efrags = (efrag_t *) Hunk_Alloc (sizeof (efrag_t));
	memset (cl.free_efrags, 0, sizeof (efrag_t));
}

void CL_Next_Free_EFrag (void)
{
	// advance the linked list, growing it as needed
	if (cl.free_efrags->entnext == NULL)
	{
		cl.free_efrags->entnext = (efrag_t *) Hunk_Alloc (sizeof (efrag_t));
		memset (cl.free_efrags->entnext, 0, sizeof (efrag_t));
	}
	cl.free_efrags = cl.free_efrags->entnext;
}
In R_SplitEntityOnNode, replace these lines...

Code: Select all

		if (!ef)
		{
			Con_Printf ("Too many efrags!\n");
			return;		// no free fragments...
		}
		cl.free_efrags = cl.free_efrags->entnext;
... with this:

Code: Select all

		CL_Next_Free_EFrag ();
And to finish this tutorial, delete all ocurrences of these:
cl_efrags
MAX_EFRAGS
Ph'nglui mglw'nafh mankrip Hell's end wgah'nagl fhtagn.
==-=-=-=-=-=-=-=-=-=-==
Dev blog / Twitter / YouTube
mankrip
Posts: 924
Joined: Fri Jul 04, 2008 3:02 am

Re: Extending Quake Limits - Part 1: Static Entities

Post by mankrip »

An extra info: R_RemoveEfrags is completely useless.

It is only called when ent->model is false, but the entity efrags are only generated for static entities where ent->model is true. So, every time R_RemoveEfrags is called it does nothing, because ent->efrag is already NULL.

I suspect that R_RemoveEfrags was intended to allow the engine to make static entities dynamic again, but this was never fully implemented. R_RemoveEfrags also seems to not deal correctly with the cl.free_efrags linked list.
Ph'nglui mglw'nafh mankrip Hell's end wgah'nagl fhtagn.
==-=-=-=-=-=-=-=-=-=-==
Dev blog / Twitter / YouTube
Post Reply