BSP Trees, Part 2: Making the Tree
Nobody wants to edit a BSP tree by hand. It can get very, very ugly. Hideous, in fact. Nobody even wants to write a level editor that makes BSP trees. When you make a Quake level, you aren’t actually making a BSP tree. All you have to do is put solid objects (called brushes — I don’t know why) into the Big Empty Void™. Here is the first level many Quake level makers ever make — a square room (of course in Quake it would be a cubical room).
When you want to play the level you have made in Quake, you have to run a program called — gasp — BSP. The program takes a .MAP file containing brushes and turns it into a BSP tree. Each brush is actually a list of planes, so it is easy for the program to take those planes and use them to carve up the space. Here is the room made into a BSP tree, the tree diagram is omitted.
The BSP program is pretty smart — it can figrue out which part of the level is the inside and which part is the outside. The inside is simply the part which has entities (players, guns, lights, ammo, monsters, teleport destinations etc.) in it. The outside is everything that is closed off and impossible to get to. Sometimes it is not really outside, just a room that you accidentally closed off. Those areas are filled in, or marked solid.
Once these areas are marked solid, there is bound to be a lot of wasted information. What use is a partition if both sides are solid? Partitions where both children are solid were colored red in the diagram.
Quake deletes them. Much simpler, eh?
