Erm, makes them not wake up when they hear something... 

makes them not wake up until they see you -- normally they will also wake up if a nearby monster sees you. 

Kind of general programming question about Quake. How does Quake handle broad-phase collision between entities. Does it store them in each BSP leaf and only collide those in the same leaf? 

There is a bit of a problem with that approach, which is key to understanding how the engine actually does it. The problem is that an entity might occupy more than one bsp leaf at the same time. So you would actually need a list for each entity of all the leaves that it spans.

Since this might get unwieldy the engine does something a bit simpler, and if you're interested in finding all the code behind it then the thing to search the source for is sv_areanodes*. Areanodes actually just split the space occupied by the world into a fixed depth binary tree by repeated partition along the longest axis of the previous areanode.

That last sentence is concise and accurate, so I instantly fear it's not very approachable. It's like making a new binary space partition which almost entirely ignores the geometry of the world and only uses the minimum and maximum points. It then recursive splits the space into two equally sized parts. It does this by splitting the longest side of the remaining space to try and keep the lengths of all the sides as even as possible.

An areanode is one of the dividing lines between two of these areas, or one of the areas themselves in the case of the leaves on the bottom level of the tree. If an entity straddles a division then it is stored within the list attached to that node. If it straddles many divisions then it is stored in the list belonging to the division furthest up the tree. If the entity is wholly contained in a single area, then unsurprisingly it is stored in the list belonging to that "leaf areanode".

It's then fairly simple to pare down the list of entities to collide against. Find the areanode that your collision trace belongs to (imagine the area swept out by the movement as being a big entity), then you need only test all entities in the subtree with that areanode as the root. If you go through the exact centre of the map then you will certainly be testing against all the entities in the map, but it's not often a problem in practice.

It's worth noting that quake actually has a fixed depth for this tree of just 4. This translates to 16 leaf areanodes representing volumes in the map, along with 15 splits separating them. To illustrate the size of that, if your map is 4 times wider in both x and y than it is tall, which it's easy to imagine something like Castle of the Damned might be, then there would be no areanode splits in the z axis at all, instead creating a 4x4 grid over the map.

Presumably custom engine coders who push both the extents of the bsp format and the number of entities in a map do increase these limits somewhat, either dynamically or just to a higher static cap.




*Warning: If you look too carefully in this region of the source you might find this pair of macros which make the Rune of Black Magic look tame...

#define EDICT_FROM_AREA(l) STRUCT_FROM_LINK(l,edict_t,area)
#define STRUCT_FROM_LINK(l,t,m)
������((t *)((byte *)l - (int)&(((t *)0)->m))) 

ic... or at least, I think I do :P So this set up is kind of like a grid containing sub-grids kind of set up (can't remember what they're called)?

How does it manage the list of objects as it changes? ie how does it move an object from one node to another? 

/slaps self for awful grammar. 

The term used within the engine for maintaining these lists is called linking*. You might have heard the term used in QC in discussions about SetOrigin. Typically guides would mention that if you set the origin key directly then the entity will not be correctly linked in the engine. This actually means the entity you moved will still be listed in the collision list for its old position.

In the same way that we have to be responsible and call SetOrigin every time that we move things in QC, the engine code has to call the relinking function every time that it updates the origin of an entity. The nitty-gritty of the relinking is not too complicated, just run through the areanodes until you find one that intersects your entity (or reach a leaf that contains you). Then remove yourself from the old list and append yourself to the new one.



*The term linking does have quite a nice visual metaphor of tying the entities to their areas, but I think it really only arose because the entities are stored in a traditional "linked list" structure. 

It's worth noting that quake actually has a fixed depth for this tree of just 4. This translates to 16 leaf areanodes representing volumes in the map, along with 15 splits separating them.

this is also the thing that causes large bmodels to flicker or disappear, i believe. especially with rotaters because qbsp errs on the side of (paranoid) caution and makes the bboxes massively oversized. it also doesn't take into account the actual rotations that you will be subjecting the rotater to (this is more understandable though), so if you had like a 1024 long brush that had just a 4x4 cross section, the bbox would still be roughly 1024x1024x1024, even if it only rotated along the long axis.
this makes it get connected to tons of those leafs and and overloads the engine. i guess it just either discards the first links it made, or stops linking when it hits the limit. 

you'd think it would simply store the node of the first plane that the bbox is on both sides of. Then when testing two bboxes against each other, find out if their node pointers are related (identical nodes, or ancestor-descendant), then test bboxes directly. Maybe they did that and it wasn't fast enough on the target machines.

One thing to point out -- I attempted making a mapper-oriented console warning in fitzquake that said "entity XYZ touches too many leafs, exceeds MAX_ENT_LEAFS", but what i found was that even tiny id maps had these errors. So even e1m1 breaks the limit on a couple of entities, but you never see a symptom of it unless it goes over so much that none of the 16 leafs are in the current PVS, causing the entity to vanish. 

Interesting... time to go off and read some more about data structures :)

What bits of source code should I look up to take a peek at the game loop? Interested in how it sorts through objects and knows what to do with each object :E 

I'd say SV_Physics() in sv_phys.c is the main loop to start with. It runs once per frame, looping through all the entities, running physics and QC functions on them. It doesn't give you everything the server does in a frame, stuff like creating the updates to be sent out to the network and parsing the input from the client is elsewhere. But it is the heart of the matter.

One thing that I've found extremely helpful in tackling the quake source code is loading it into a proper IDE like Visual Studio. Being able to right click a function name or typedef and select "go to definition" allows you to focus on figuring out what the functions do, rather than having to switch your train of thought to hunting down the function manually. The history buttons are likewise important so that you can return to the original function just as easily.

Finally "Find All References" allows you to step outwards, for instance to go from Sv_Physics back out to the rest of the server code, and see where it fits in. 

of looking far too closely at the engine physics source, is this a mistake?

trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end)
{
��trace_t���trace;
��vec3_t����offset;
��vec3_t����start_l, end_l;
��hull_t����*hull;

// fill in a default trace
��memset (&trace, 0, sizeof(trace_t));
��trace.fraction = 1;
��trace.allsolid = true;
��VectorCopy (end, trace.endpos);

// get the clipping hull
��hull = SV_HullForEntity (ent, mins, maxs, offset);

��VectorSubtract (start, offset, start_l);
��VectorSubtract (end, offset, end_l);

// trace a line through the apropriate clipping hull
��SV_RecursiveHullCheck (hull, hull->firstclipnode, 0, 1, start_l, end_l, &trace);

// fix trace up by the offset
��if (trace.fraction != 1)
����VectorAdd (trace.endpos, offset, trace.endpos);

// did we clip the move?
��if (trace.fraction < 1 || trace.startsolid )
����trace.ent = ent;

��return trace;
}

Quoting from fitzquake source but I think it's unaltered. I've bolded the references to offset, because as far as I can see it never gets initialised. It doesn't actually matter in the call to SV_HullForEntity because that function never reads the offset parameter, just uses it as a local variable for internal calculations!

Still, since it's not passed by reference there presumably the same junk sitting there from the uninitialised starting state. Is it just by fortunate placement on the stack that it always gets zero initialised or something? It looks like it should at least mess up trace_endpos if it really contained garbage, or worse the whole SV_RecursiveHullCheck call... 

It's only evident when you check the definition of vec3_t in q_stdinc.h:

typedef float vec_t;
typedef vec_t vec3_t[3];

vec3_t is an array type, so it is always passed by reference in a function call. In this case, it looks like SV_HullForEntity always writes to the offset variable, so there's no problem.

That is really confusing, though - at first I though vec3_t was a type that is passed by value, like struct { float x; float y; float z}. 

that's what i suspected too, looking at that code. 

Do you write about code elsewhere? 

inertia: No, this is basically my one coding outlet! I've got a little article coming up on names in qc which lead me to look up this function and get confused.

ercw: Thanks! Been away from c coding too long I missed that vector thing. And I really should have seen it given the way that the VectorAdd function works, clearly taking a pass by reference in order to mutate the third parameter. Ah well... 

how does a for loop initialise an integer automatically?

int a;
for (a=1; a<150; a++){cout << a;}


Works, buuuut:


int a; cout << a;


throws a compiler error with


"Run-Time Check Failure #3 - The variable 'a' is being used without being initialized."


Now obviously i could start with:


int a=0;


But what gives the for loop the right to initialise the variable before it begins testing it? 

for (a=1; ...

The a=1 is the part that initializes the variable 

Hmmmmm. I kinda suspected that. I guess I'm mis-understanding the for part. I can't help but think of it as an if.

The excercise which has gotten me confused is the following:

int i, j;
bool isprime;
for(i=1; i<100; i++){
isprime = true;
// see if the number is evenly divisible
for(j=2; j<= i/2; j++)
// if it is then it is not prime
if ((i%j) == 0) isprime = false;
if (isprime) cout << i << " is prime. \n";


It's the modulus test part, and my understanding of prime numbers which has gotten me confused.

I inserted this after the second last 'if':

cout << "i=" << i << ", j=" << j << " ";


This way it shows me what the two variables are. I don't understand why the test works. 

cout << "i=" << i << ", j=" << j << " ";

looks suspiciously like some of the stuff i've been learning about linux and input redirection... 

What exactly don't you understand?
The if (isprime)? If you test a variable without explictly writing eg isprime == 42 it will test if the variable is true (or not false or something like that). 

%

% is what i dont understand lol.

Why is 2%3 equal to 2 ?

Why is 45%89 equal to 45 ? 

http://en.wikipedia.org/wiki/Modulo_operation 

The most useful bit of information I could find on that page was:

^ ISO/IEC 14882:2003 : Programming languages -- C++. 5.6.4: ISO, IEC. 2003. "the binary % operator yields the remainder from the division of the first expression by the second. .... If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined".

The word "nonnegative" scares me a bit TBH.