I've done a few practical experiments today to test how BSP responds to the order of the brushes in a map, so I'll write up and post all about that later - and hopefully explain why adding a brush can reduce the marksurfaces. For now, a bit of reassurance for rebb.

Once the compiler has created a list of surfaces from all the brushes in the map, it has to decide which one to compile next. It has two methods of choosing the next surface to split along, which we will call "fast" and "slow".

The slow way is easiest to explain. It tests every surface in the list, and checks exactly how many splits will be made. It then chooses the surface which will create the fewest splits.

The fast way is more complex conceptually, but quicker to compute. The engine looks through the list of remaining surfaces to find the ones which are axis-aligned. Of these, it chooses the one which best splits the area of the map into two evenly sized halves. If there are no axis-aligned surfaces, it just takes the first remaining surface.

The old rule for the bsp tool was to use the slow way for the visible surfaces, on the grounds that reducing visible surfaces matters. For the clipping hulls the fast way was chosen, either to save compile time or to make a more balanced bsp tree, not sure. However, once you're running up against the marksurface limit, then minimising the number of splits in clipping hulls suddenly has value. This is where rebb's modification pays off, as it applies the slow way everywhere.

Fun little idea which has seems to hold up from all that above(bear in mind I'm not that knowledgable on bsp stuff): If you've got big chunks of map with trisoup walls, maybe a cave...if you build some nice axis-aligned brushes to contain the cave walls, even ones which will eventually be clipped away, that ought to improve the compilation in the "fast" phases of compilation. Those brushes should be compiled early, and act like proto-hint brushes.

So coming soon - why all that minimising splits stuff is not what it sounds like. And how adding brushes can reduce splits! 

What if I want to put an enemy into my map (I am making a Quake 1 map) that doesn't appear (or "spawn") until the player walks over or activates some kind of trigger? 

Make a box room in your map, put monsters inside it. Over each monster make a brush entity 'trigger_teleport' and set a 'target' key on that entity with a value of 'Jeffrey' (or whatever). Give it a 'targetname' of something like 'triggerJeffrey'.

In your map make a point entity 'info_teleport_destination' where you want the monster to 'spawn', and call it 'Jeffrey'.

Make a brush entity where you want the player to trigger the spawning. Make it a 'trigger_once' entity. Give it a 'target' key with a value of 'triggerJeffrey'.

Now when the player touches the trigger_once entity, the teleporter in the hidden box room with teleport the monster to the info_teleport_destination. :)

If you are using the Quoth mod, just put the monster where you want it to spawn, give the monster a 'targetname' of 'Jeffrey', and check the 'delayspawn' flag for that entity. Now you can target the monster with a trigger_once brush entity and it will spawn when triggered.

:D :D :D 

Thanks for the help I will try that out!

However, there is one thing I was wondering in regards to the editor I am using (NetRadiant). When I go to "file" there are 2 options I am interested in know what mean. They are "save selected" and "save region". What do those do? Can I save only selected parts of the map or something? 

So here's part II of the weird and wonderful world of BSP Algorithm weirdness.
http://tomeofpreach.wordpress.com/2013/05/31/greedy-algorithms-and-bsp/

If you already know about Greedy Algorithms you can skim through this as it won't teach you much that's new. I hope that it will answer that burning question of how deleting brushes can increase marksurfaces - and please let me know if you are curious but part of the article was incomprehensible! 

A little func_ bonus content from that blog post. I tried some very simple experiments into how the order of brushes in the map file affects the BSP output. It's easy to replicate, just create a single 6 brush box, with a 7th cube floating inside(texture this one differently so you can recognise it). Export the map, and use a text editor to cut & paste the floating brush entry up and down the brush order - you can create 7 different map files in this way.

I then tried compiling all 7 maps with Rebb's compiler, first without the new switch. In this case, there actually was a small change in the number of markfaces: when the floating box was moved high enough in the map file, the number of marksurfaces fell from 193 to 191. Yup, that's a 1% saving!.

When I repeated the compilation with -forcegoodtree turned on, the marksurfaces held at 177 for all 7 map files, but that's a 9% saving over the earlier worst map. Seeing no variation does not seem surprising after the last post, where we saw that the "slow" method considers all brushes at once. But there were variations in other quantities like edges and clipnodes. How?

Well, I can think of two possible explanations. One is that these other quantities depend on some other part of the compiler we haven't considered, and bit that is sensitive to order of brushes. I think the more likely explanation is that even when always applying the "slow" method there are still occasional "ties" where two splits look as good as each other, and the compiler picks one solely on order in the map file.

This is consistent with the observation that all the faces in our test are axis-aligned, so we don't ever test the code in the "fast" method which compiles brushes strictly in order. It appears that the variations in the former compilations were only due to ties being broken by brush order. The fast way appears to generate more ties than the slow way (which is believable from the code), and these ties might result in greater variation (an interesting result). 

Yes, that is what those two menu items do.

Save selected saves the selected brushes to a map file and save region saves the current region. 

'region' 

Region selection is in the "View" menu. It's basically a way to hide large chunks of the map at once. You can select only a specific area to be visible while editing, this can de-clutter your view of the map a lot.

I've only used the "set xy" option, so I don't really know how the others work. The "set xy" will hide everything that's not in the current xy 2D view

I've never tried saving a region, can't think of any good reason why I'd want to. I guess it just saves the currently viewable stuff in a new map. 

Thanks for those articles, looking forward to the follow-ups :)

If it turns out that the experimental switches like "-forcegoodtree" are indeed not having yet unknown side-effects, like causing one's offspring to be born with a tail, maybe it could be implemented in other tools as well - the code change needed is very minimal. 

 

.. has also this feature: it is possible to hide some part of the design in the editor (3 options are actually possible: visible, hide, or greyed).
Also, vis-grouping allows to be indeed more flexible. It is possible to build only a selected part of the design to check that it looks correct.
Well, I guess more or less all editors have this kind of features :) 

I've always liked quarks tree view that makes map components look like a file system. 

i still like quarks texture applying. 

I tried messing around to figure out how to do it but can't figure this one out. How do I get brushes to move around like you see in many of the areas in the game? (Quake). I am talking about things like platforms that move back and forth and also things like those those cubes at the end of E1M2 that move around. How do I create those? 

thats a lot of questions..
head over to:

quakewiki.org/wiki/mapping

in entities you'll find what you looking for

googling the unofficial quake specs should be helpful too. 

func_train and Path_corner to be more unprecise 

For platforms that only move in one direction like back and forth, or up and down, you can just use a door. For more complex motion you'll need to use a func_train with multiple path_corner entities. 

Moving platforms are func_train entities. They move along an interlinked set of path_corner entities. The plaform starts at the path_corner it targets (if it has a targetname itself, it will only start moving after being triggered); each path_corner targets the next one, and the last one the first. If the platform is supposed to stop at the last path_corner, set "wait" "-1" there. 

Slow typer... 

OK, my next foray into the realm of messing with BSP compilers, and the first real success (sort of).

http://tomeofpreach.wordpress.com/2013/06/07/random-algorithms-and-bsp/

Now with graphs! Yes graphs! 

Very interesting research into the BSP process, Preach.
It's weird how the results we so different from a box map and a full size one.

Have you tried this test with maybe some small maps like DM maps? 

Afraid I didn't try any map in-between. I'd go and give it a shot now, although I expect that the result would be more like the latter than the former. Unfortunately I can't do that easily right now, because I've been revising the code for a future post, and don't have the original compiled at the moment... 

I was mainly interested in pinpointing where it started to become 'bad' and to try to pinpoint what it is about full maps that don't show up in box maps. 

I may have some insight into that from the new tests. It seems like there's a very fine balance to strike with random input - it seems to work best for trying out different ways of resolving "ties". I guess that in the simplest of test maps there really isn't any difference between just tie-breaking and randomising everything - but I think as soon as you add any real detail then the difference matters.