Hmm. Doesn't the .bsp have primative bounding boxes in it for fast collision testing? Maybe I'm thinking of the wrong thing. I didn't mean to use the .map to create boxes from brushes, I thought they were in the .bsp. I think I used the word "brush" when I shouldn't have, causing confusion.

I hadn't even thought about marking the mesh colliders as convex. That's a great point. I'm about to start doing some System.Stopwatch tests to see what takes the longest and what is worth it to optimize and what isn't.

Still haven't looked into lightmaps, but from a cursory glance it looks like they're not going to be simple; at least not as simple as Quake 3's were. 

no. bounding boxes in bsps are for frustum culling. they're not useful for collisions as the bsp tree will cull all that effectively enough anyway. 

Trying to parse the vis data, and I'm trying to verify that I correctly understand the run-length encoding used. Consider:

10100010

Would that RLE to

1010310
or
10100310

Some places say that Quake vis data only does RLE on runs of zeros, but the only doc I have is the one that has proven to be very outdated. 

Can a face be part of more than one leaf? 

I've sped up start up dramatically. Replaced all remaining Lists with length initialized arrays. This cut startup time on ivory.bsp (which as become my benchmark) from two and a half minutes to two and a half seconds.

I also detect clip/skip faces and don't render them, which makes maps a lot more fun to fly around!

Here is a build for you guys to test out and play with:

https://dl.dropboxusercontent.com/u/5408868/qtest.7z

I've included Sock's ivory.bsp as the default map because it is awesome, and I used the spectacular rockwork to test/verify my texture creation/application was working right, which it is.

If you'd like to try a different map, open the "assets/resources/maps" folder and name the map you'd like to try "map.bsp" and it'll be used. The camera will spawn at the world origin. Mouse1 will move you forward, Mouse2 backwards. No WASD, just mouselook.

Currently there is no vis consideration at all, so what is being rendered is up to Unity. This isn't ideal at all, so the map might chug if your video card isn't up to it. Give smaller maps a try!

Currently only BSP29 maps are supported, but BSP2 support will be trivial to add. I'll do it next session I think, to take a break from fighting with vis data. 

Could you explain, what the main purpose of that uQuake util 

Doesn't run on my rig 

not a valid Win32 application apparently. 

Sorry forgot to mention that build is 64-bit only. I'll build a 32 bit version.

Honestly I'm not sure what the ultimate purpose is/will be. Really I'm just doing it because it's fun to make. Though Unity runs almost everywhere (Windows, OS X, iOS, Android/Ouya, web browser, Windows Store/Phone, etc) so if I can pull it off the end result will be a (free) Quake engine for a bunch of devices. Really now I'm just doing it as a programming project based around one of my favorite games. 

You might also need the Visual C++ runtime on 64 bit, which is here (it's tiny) http://www.microsoft.com/en-gb/download/confirmation.aspx?id=14632 

Not had much chance to get things on my blog recently, but put out a short article today.

http://tomeofpreach.wordpress.com/2013/10/19/random-entities-find/

It's a combination of a neat mathematical trick and a little bit of glue code which allows you to select one entity at random from find or findradius result sets. There's also a pattern at the end for writing find loops, so you don't have to repeat your find code at all. Whether it's an actual improvement or not is up for discussion... 

Sorry for the 64-bit snafu. Also sorry for using Dropbox, it's not the best for sharing public files. Lets try Github instead.

https://github.com/mikezila/uQuake1/tree/master/Builds

Pick your favorite flavor, 32 or 64. You might need the Visual C++ 2010 runtime if it complains about Mono. 

I'm thinking on the problem of using the vis data from the maps in my renderer, and I'm running into a few snags. Some of these snags are no doubt a result of me trying to take shortcuts.

At first I thought I could use the bounding boxes for the leafs, and just check against them using the player/camera position. This would make it very easy, as each leaf knows what other leafs to render. Problem is that the only bounding boxes in the .bsp are stored as shorts, not floats. The problem with that is that to convert "Quake space" to "Unity space", I have to scale (and rearrange) the vector3s by 0.03! That's a pretty extreme scale, but it wouldn't be a problem if the bounding boxes were stored as floats, but they're not. Once I do this scale, the boxes are not accurate enough, they're obviously off center, and not shaped/proportioned correctly. I thought I could work around this by making a bounding box myself that encompassed all of the faces in a leaf, but there is a lot of overlap in many places, even if I just overlap the center of the faces and not their whole bounds. On the plus side I accidentally made a pretty nice tool to check if parts of your map geometry are producing shitloads of leafs.

I also made a bad assumption that a given face could only be a member of one leaf, but it looks like that's not the case. I should have known better, as if a face could only be in one leaf it'd probably be listed in the face struct.

Is there any shortcut I can take, as opposed to just implementing the bsp tree wholesale? I'm thinking pretty hard, because with all the modern tools available it seems like it'd be easy, but I can't come up with anything. 

It sounds at first blush like you're doing something wrong with the bounding box scaling. Scaling it should be perfectly doable without it shifting off center. There must be an incorrect assumption you're making there or something. 

I agree with Willem, are you sure you are not somehow casting the result of the scaling back to short? Although if you multiply a short and a float, the result should be a float, also. 

Yeah I was botching it. I was reading the 12 bytes that contain the shorts and passing them to be handled by the leaf constructor, but in that constructor I was only using the first six bytes to make my six floats (ugh). Corrected that and now the boxes are placed and rendered correctly. I'm currently fighting with Unity's local vs worldspace shenanigans, but it looks like this might just work.

Thanks for calling me out on my assumption. 

There's also a pattern at the end for writing find loops, so you don't have to repeat your find code at all. Whether it's an actual improvement or not is up for discussion...

How does it compare to using a for loop to find, instead? 

How does it compare to using a for loop to find, instead?

It generates essentially the same code, so it's just a trade-off in human terms. The for loop is a bit more explicit on what's going on, but the while loop is shorter and better from the Don't Repeat Yourself point of view. 

your two loops are not equal. the for loop will ensure initialisation.
the while loop will run slightly faster - the way its written will consume one less instruction (additionally the progs will be a smidge smaller due to the reduced repeats).

modern qccs (including recent fteqcc builds) will be able to optimise more agressively if all locals are initialised before use, reducing the number of temps used (because initialised locals will not have undefined values when recursion or overlapping is used). Plus its good practise if you ever write C code. :P
Also, fteqcc likes to warn about unintended assignments within conditionals, which can be fixed with an otherwise redundant extra parenthesis (consistant with gcc).
Put that all together and the ideal loop is something like:

for(candidate = world; (candidate = find(candidate,classname,"monster_ogre")); )
{
foo(candidate);
}

Yeah, it costs an extra vm cycle, and an extra instruction to go with it, but it potentially saves as many 'globals' as you have locals in your function, including localised temps (assuming the qcc doesn't detect any other uninitialised locals).
It definitely saves a few headaches too, when you use the same variable in multiple loops in the function.

Of course, if you want compatibility, the for loop is an extension. Only while and do while loops are supported in all qccs. 

That's interesting to know, thanks! So if I explicitly initialise a local I get can get a reduction in stack size. Is that at the cost of additional length in function size? I think it's right that the extra instruction doesn't cost execution time because an extra temp would also mean an extra zeroing-out. Guess there's no benefit if you're not under pressure for temporary variables in that function?

The ability to suppress the warning is a massive boon though! I'm back down to zero warnings and blissful silence... 

Are there any occasions where the optimising code takes advantage of "leaf functions" i.e. functions which call no other functions? It seems like a category of function which would be easy to identify at compile time, and where you could go very aggressive in terms of reusing variables as you don't have to worry about recursion or anything needing to be restored later... 

QC stack:
when a function is called, the current locals are copied off to some hidden stack. the 'globals' (globals is definitely the wrong word to use here... in this post this is the only meaning of the word 'global') that hold the locals are not overwritten automatically when the function then runs.
when the function returns, the globals that are used for the function's locals are reset to their original values, thus they are cleared or so again ready for the next time its called.
if you have a recursive function, those locals will thus be set to the value they had in the parent (even if its not the direct parent). which is probably not what you want.

the optimisation the qcc is trying to use here is to overlap all locals from all functions using the same set of globals. this means you don't waste globals on other things. the engine still does the same amount of archiving (to preserve the caller's locals), just it deals with the same block every time.
the requirement that things are manually initialised avoids bugs with legacy code where unitialised variables are expected to be 0 (despite there being cases in vanilla where they are not - recursion).

Where the function looks like it has at least one uninitialised (read-before-write) local, the function's locals are given a unique non-shared location for all of its locals, as the engine supports only a single globals block for the locals stack.

While its possible that better cache utilisataion might make the code faster, the reality is that the actual cpu will need to execute more instructions than it previously would have. 

That's a fascinatingly weird glitch I'd never heard of before - I'd held the zero initialisation as being a fundamental property of the language! For those who like demonstration code, the following shows off the important properties:

void() Recurse =
{
��local float delta;
// note we use delta here uninitialised on the
// RHS before the assignment happens
��delta = delta + 1;
��dprint("IN: ",ftos(delta),"n");
��if(delta < 5)
����Recurse();

��dprint("OUT: ",ftos(delta),"n");
}


This outputs:
IN: 1
IN: 2
IN: 3
IN: 4
IN: 5
OUT: 5
OUT: 4
OUT: 3
OUT: 2
OUT: 1

The value of delta is retained between calls as we recurse deeper onto the stack, but is restored to the value the caller had when we return to her. No doubt someone can do something creative with this, I'm gonna go audit all my code for correctness again... 

the prerelease had no local stack. Essentually it had no locals at all.
carmack really loved his globals...

Using fteqcc, try:
#pragma warning enable F302
Might have false positives - but let me know if you do spot any false negatives. 

I assumed '0' was correct behaviour.

What would coders expect to be correct for an undefined variable? A null value?