ST-CS-10-339-75
March 2002

SECTION VII

OBJECT PENETRATION  (U)

1.  Description of the BSP File Format  (U)

Half-life maps are stored using the BSP file format. It is essential to understand how this file format works to understand how object penetration works and so to understand why the length or thickness or exterior texture (wood, metal, concrete, etc) of an object is completely irrelevent to whether or not a projectile can pass through that object.

Imagine a map. It contains many objects - walls, doors, tables, etc. You could store the map by making a complete list of each object, its size, position, texture and so on.

Every time the rendering engine wants to draw a frame on the screen, it needs to know where the player is and what objects he can see, so it knows what to draw and where to draw it. To do this, it has to search the list of objects (remembering that each object has its position stored in the list) in the map to work out which objects are visible from where the player is.

If the list of objects is just one long list, the rendering engine would need to search the entire list to work out which objects were visible. This would take a long time, and so seriously diminish frame rates, since each frame would take a long time to draw because a lot of time would be spent searching the list of objects every time a frame was drawn.

To deal with this problem, the list of objects in the map is organised to make finding out what objects are visible from the players position very very quick - this is what the BSP file format is all about.

When the BSP file is made by a map creation tool, it first makes a single long list of all objects. The map is then split down the middle, into two halves. The list of objects is then divided into two, one list for all the objects in the left half of the map, one list for all the objects in the right half.

Crucially, any object which was split into two (e.g. some of it is in the left hand side and some in the right) gets split into two objects - the part of the object in the left hand side is one new object and the part in the right hand side is another new object. Of course, when drawn on screen by the rendering engine it looks perfectly normal - you don't see a join or edge.

The advantage of splitting the map into two like this, and having two lists of objects, is that the rendering engine can say "which half of the map is the player in?". It knows the answer because it knows the players location. As a result, it can totally ignore all the objects in the other half of the map because it knows the player is nowhere near those objects. (At this point, with just two lists of objects, this is an oversimplification because the player could be near the middle of the map and so could see objects from both sides - however, in reality this isn't what happens as will be explained in the following paragraphs).

Of course, only splitting the map in half wouldn't actually help very much since the list for each half would still be very long. In fact, the splitting process is done many times and both vertically and horizontally, so you end up with many small cubes of map, each with its own list. When the renderer wants to know what it needs to draw, it can rapidly search down the list of cubes, working out which ones are visible, and then getting hold of the list of objects for each cube. This is why there's never a problem with the player being able to see into the "other half of the map". The renderer builds up a list of all the little cubes of the map the player can currently see into.

In practise, the splitting process isn't normally an exactly fifty-fifty split. The map generating tool looks at how many objects would exist after a split and tries to keep roughly the same number of objects in each cube. So if a fifty-fifty split in a room would lead to one half with twenty objects in and the other half with two objects in, then the map creation tool won't do this. It will instead do something like a twenty-eighty split, so that each side has roughly the same number of objects. This is because keeping roughly the same number of objects in each cube area (although it might well not actually be a cube shape in the end because of uneven splits) is crucial to keeping the search speed high.