Creating the EndFrame function

Suppose that a group of entities in our mod are generating a massive excess of sounds, causing packet overflows and clipped audio. We can restrict the group to only play one sound per frame, but if we simply approve the first sound request then the later entities in the group will never get to sound. It might be better to wait for all requests and choose the “loudest” one, and it is possible to keep track of the loudest request so far this frame. However you can’t determine the loudest noise until all the entities think, and once each entity think has run the QuakeC is over for the frame.

One approach is to play the loudest sound at the start of the next frame instead, but this does introduce latency into the audio we’d like to avoid. Doing a similar thing with visual effects instead of sound might be even more apparent. The absence of a partner to StartFrame called EndFrame has been noted previously, as in the Quake Info Pool article. The article offers an engine implementation, and a fallback for QuakeC (which runs EndFrame in StartFrame if the engine doesn’t support EndFrame). Today we’re going to try and create a pure QuakeC version, to enable strange tricks like:

  • Rate limiting network traffic by culling on the QuakeC side
  • Decoupling the visual model of an entity from the physics model
  • Emulating entity attachments with greater reliability

Necessary Assumptions

We need to assume that one behaviour found in standard Quake engines will also hold in custom engines, but I think it’s reasonable. Our assumption is that the nextent function supplies entities in the order that the engine runs think functions on them. While there’s no standards document you can hold QuakeC to, I’d argue the entities must be ordered in some list for a nextent function to make any sense. We just need to believe no engine would have reason to break the connection between this list and the execution order of the entities.

The Backstop

The other concession we need to make to get EndFrame is to use up one entity slot for operational purposes. The plan is to have a entity dedicated to running EndFrame as a think function. The main trick in this article will be to ensure that this entity is always the last one in the list, so that it has the last think function of each frame. We will call this entity the “backstop”. (I was going to use “caboose” but my editor advised me to aim for the American market)

Loading The Bases

We split the task into creating a backstop in the final slot, and keeping it there when future entities are spawned. The way the server in Quake start makes it easy to create an entity which is at the end of the list, 99% of the time. In frame 0, the engine is willing to reuse empty entity slots while loading entities from the map(in case an info_null removes itself and leaves a gap). The result is the entities loaded from the map usually form a continuous block; then running e=spawn(); at the start of frame 1 ensures e will take the slot one past the end of the block.

However, it is not impossible for gaps to appear in the map’s entity block. Suppose entity 10 is the last to load, but it has a bizarre spawn function that removes entity 6! Without any other entities to load from the BSP the gap will remain, and when we try to spawn the backstop, we get spawned in slot 6, which is no good. The trick is put a loop around e=spawn(), testing if e is in the last slot with nextent(e)==world to terminate the loop. We create a linked list of the entities we’ve spawned, and delete them once we’ve created an entity beyond all the map spawns

One Entity, Nearly New

This is all fine until we start spawning more entities. Surely it’s almost inevitable that another call to spawn() will come along, and end up using a slot beyond the one our backstop is in. Plans to pre-fill the entire entity list, in the same way the we plugged the gaps earlier, face two obstacles. Firstly, custom engines often change the limit on how many entities you can spawn, and there’s no reliable way to discern the limit from the QuakeC. Secondly, even if you did know the limit, if you fill every slot, even for an instant, then your mod can’t spawn anything for the next two seconds. Not a good situation to be in at the start of the map.

So we use a more subtle approach. We add a wrapper function to spawn() so that each time we call it, we check if the engine gave us an entity in a slot beyond the backstop. If it did, then we swap the backstop with this new entity. The new entity gets the EndFrame think function and is ready to go. The previous backstop entity is no longer needed, but rather than delete it, we just erase the handful of fields that we used, and return that as the fresh, blank entity for the function that called spawn().

Limitations

So we mentioned there were two conditions that we needed to get this working: firstly that custom engines had to preserve the connection between processing order and nextent order; secondly that we needed a spare entity knocking around to get it rolling. There’s also an important limit we need to apply to the code that we run from EndFrame – it must never call spawn().

This is because of the tricks we’ve been pulling to ensure that the backstop is always the last entity. The backstop entity will change if we happen to spawn a new last entity during the EndFrame function. Once EndFrame returns, the engine will notice the new backstop in the slot after the former backstop (which it just finished processing), and run the think function on that. The result: EndFrame runs twice in the frame.

You could make the logic that manages the backstop swapping more complicated: detect when a swap happens during EndFrame and schedule the think to occur next frame instead of this. However, you still have a problem if multiple entities spawn – some of them will remain beyond the “former backstop” slot and so have physics processed by the engine later than EndFrame – which breaks the point of EndFrame somewhat. So I recommend avoiding the possibility. Sometimes you might be able to spawn the entity you need earlier in the frame, and save it for use in EndFrame later – this is a better workaround.

To make sure that you don’t call spawn(), you have to be really careful about which functions you call. For example, you can’t call T_Damage, because lots of things you can damage will spawn gibs. So you can’t call functions that might inflict damage. It’s a bad idea to call any function pointers like e.use or e.th_die as it’s too hard to control what’s going on there. Really you should restrict yourself to QuakeC written purely for EndFrame and builtin functions.

Code

Warning(24/05/2014): This code exposed a compiler bug in fteqcc 1.0 when some optimisations are applied. When the optimisations are turned off the code goes into an infinite loop. It’s bad stuff all round. I’ve left the code here to preserve the article as it was, but don’t use it straight away. You can read Fixing the Endframe function to see the investigation of the bug and learn a bit about bytecode, or read Easily fixing the EndFrame function to get a fixed version of the compiler and the bug-fixed version of this code.

We have to modify existing code to implement all of this so it ends up spread out between files. Firstly replace the definition of spawn in defs.qc with

entity() spawn_builtin                = #14;
entity() spawn; //to be defined later

Then in world.qc add the following to the top

entity backstop;
void() EndFrame =
{
    // set ourselves up to think again next frame
    self.nextthink = 0.05;
    // prevent accidental modification of the backstop
    self = world;
    
   // demonstrate the function
   bprint("EndFrame call at time ");
   bprint(ftos(time));
   bprint("\n");
}
entity() spawn =
{
    local entity e;
    e = spawn_builtin();
    if(nextent(e) != world)
        return e;
    // e is now the last entity on the list
    // so we need to swap it with the backstop
    local entity f;
    f = backstop;
    f.think = e.think;
    f.nextthink = e.nextthink;
    f.classname = e.classname;
    
    e.think = EndFrame;
    e.nextthink = 0.05;
    e.classname = "backstop";
    backstop = e;
    
    return f;
}
void() CreateBackstop =
{
    local entity e, head;
//begin our list with the temp backstop
    e = head = backstop;
// spawn() already contains the code to make a backstop
// so we just burn off enough entities that one appears
// at the back
    do
    {
        e.chain = spawn();
        e = e.chain;
    }
    while(nextent(backstop) != world);
    do
    {
        e = head;
        head = e.chain;
        remove(e);
    }
    while(head != world);
}

Two modifications need to be made to existing functions. Firstly, at the very top of worldspawn() add backstop = spawn_builtin();. Because spawn() modifies the current backstop entity while initializing a new one, we will cause a crash if backstop is the world entity. Note that we haven’t yet initialized the backstop, because all of the map loaded entities are yet to spawn – we’re just preventing the crash if one of the spawnfunctions calls spawn() immediately. To perform the initialisation, add the following to the bottom of StartFrame():

    if(framecount == 1)
        CreateBackstop();

   bprint("StartFrame call at time ");
   bprint(ftos(time));
   bprint("\n");

Note the last three lines are part of the demonstration code, rather than necessary components. Compile this all up and you should get a console spammed with matching timestamps. You should also check that the backstop entity is always at the end of the entity list with the edicts command – you can fire a great long stream of nails to spawn extra entities and check that it advances to the end properly.

Advertisements

2 thoughts on “Creating the EndFrame function

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s