So far we have talked about the movement of the player interacting with certain planes (horizontal, vertical, inclined). To move forward, we need to look at the essence of this interaction, both from the map and the game engine sides. In this article we will discuss the basic concepts related to the map design. For creating test maps I will use only the most basic functions of the map editor J.A.C.K., so that users of Valve Hammer Editor shouldn't notice any difference.



When creating a map, the mapper uses Block Creation Tool to add parallelepiped blocks, and, if necessary, cuts, stretches and symmetrically reflects them. Moreover, no matter what combinations of these transformations are applied, the block remains a convex polyhedron. There is a special term for it in mapping called brush. By increasing the number of faces, mappers can create shapes from a set of brushes that look cylindrical or spherical to the player, but they are actually still polyhedra.

Together, the brushes form a model. The geometry of the model can be defined using its bounding planes. These planes can be arranged into a single structure in the form of a binary tree. It is this tree that is the basis of the *.bsp map file. Actually, the bsp extension itself means binary space partitioning. Let's see what this tree looks like using the example of a simple test map.

The J.A.C.K. editor, in which I created a new map, by default places us inside an empty room made of six parallelepiped blocks. I placed another block near one of the walls and compiled a map, calling it hull_1model:


The map file hull_1model.bsp consists of sections called lumps, each of which contains information of a certain type (the format of all sections is described here). I extracted from the file only the lumps of interest and saved them in a digestible form into the file hull_1model.txt (all map files can be downloaded here). From the LUMP_MODELS section we can understand that all map brushes are combined into one model, constrained by fMins and fMaxs parameters:

Model #0: fMins -288.000000 -288.000000 -32.000000 fMaxs 288.000000 288.000000 192.000000 iHeadnodes 0 0 10 20

Here you can also see iHeadnodes indices, the first of which specifies the beginning (top) of the binary tree. This top is the node #0 in the LUMP_NODES section:

Node #0: plane 0 childnodes 1 -1
Node #1: plane 1 childnodes -1 2
Node #2: plane 2 childnodes 3 -1
Node #3: plane 3 childnodes -1 4
Node #4: plane 4 childnodes 5 6
Node #5: plane 5 childnodes -1 -2
Node #6: plane 6 childnodes 7 -1
Node #7: plane 7 childnodes -3 8
Node #8: plane 8 childnodes -4 9
Node #9: plane 9 childnodes 10 -6
Node #10: plane 10 childnodes -1 -5

The section contains 11 plane nodes: the floor, the ceiling and 4 walls of the room, as well as 5 planes that bound the block near the wall (the map compiler did not include planes outside the room, since we won't see them). Node #0 corresponds to Plane #0, which can be found in LUMP_PLANES:

Plane #0: flNormal 0.000000 0.000000 1.000000 flDist 0.000000

The plane is given by the equation flNormal[0] * x + flNormal[1] * y + flNormal[2] * z = flDist. In our case, the normal flNormal is directed upward along the +Z axis and has zero Z offset. In other words, this is the plane of the floor. According to the bsp principle, space is divided into what is below this plane (negative normal direction) and what is above it (positive normal direction). Next, for the right child node you need to select one of the planes under the floor, and for the left one, one of the planes above it. Since there are no other planes under the floor, a negative index is written to the right child node of the tree, and this branch does not develop further. The compiler chose Plane #1 as the left Node #1:

Plane #1: flNormal 0.000000 0.000000 1.000000 flDist 160.000000

This is the ceiling plane, and the normal is also directed to +Z, so this time the left child node has become negative, and Plane #2 is selected as the right Node #2. The rest of the tree is constructed in the same way. At the same time, at Node #4 we find ourselves in a situation where there is another plane on both sides of its plane, and on Node #5, on the contrary, there is nothing on both sides. The resulting tree looks like this:


Negative indices of child nodes actually also store useful information. If we take the bitwise inversion of such an index, we get the index of the element from the LUMP_LEAVES section. For example, for Node #5, inverting the child nodes -1 and -2 will produce 0 and 1, respectively. We look for Leaf #0 and Leaf #1 in LUMP_LEAVES:

Leaf #0: iContents -2
Leaf #1: iContents -1
Leaf #2: iContents -1
Leaf #3: iContents -1
Leaf #4: iContents -1
Leaf #5: iContents -1

On the page describing the format (or directly in compiler sources we can find:

#define CONTENTS_EMPTY -1
#define CONTENTS_SOLID -2
#define CONTENTS_WATER -3
#define CONTENTS_SLIME -4
#define CONTENTS_LAVA -5
#define CONTENTS_SKY -6
#define CONTENTS_ORIGIN -7

It means that the left child node corresponds to CONTENTS_SOLID, that is, there is a solid wall there, with which the player will interact, and the right node corresponds to CONTENTS_EMPTY, that is, there is nothing in the other half of the space (inside the room), so the player moves freely there.



Another important concept in mapping is entity. Conceptually, it is an object that has some properties. If we look at the LUMP_ENTITIES section in hull_1model.txt, we will find three entity of different classes there: worldspawn contains the name of the compiler and properties that are common to the entire map; info_player_start and light are so-called point entities that specify the player’s spawn location and the location of the light source using the "origin" property. Worldspawn is not clearly visible in the map editor, but this entity is always present in bsp. J.A.C.K. added two other entities automatically at the moment of creating the map project.

Besides point entities there are also brush entities that consist of one or more brushes. I've created another test map hull_2models, which differs from the first map only in that the block near the wall is turned into an entity of the class func_wall (you can download the map files here). In appearance, the map looks exactly the same, but if we open hull_2models.txt with information about sections, we will immediately notice that there are two models:

Model #0: fMins -288.000000 -288.000000 -32.000000 fMaxs 288.000000 288.000000 192.000000 iHeadnodes 0 0 6 12
Model #1: fMins 80.000000 -64.000000 0.000000 fMaxs 240.000000 64.000000 48.000000 iHeadnodes 6 18 24 30

At the same time, another entity func_wall appeared in the LUMP_ENTITIES section, and one of its fields is "model" "*1", that is, when processing the entity brush, the compiler separated the brush related to it into a Model #1, so that it is clear what exactly the func_wall properties should be applied to. Since the block near the wall has become an independent object, it is now defined not by 5 planes, but by all 6, so there is one more node in the LUMP_NODES section. The top of the binary tree for Model #0 is still Node #0, and for Model #1 the first iHeadnodes index points us to Node #6:


Thus, each new entity will be, from the compiler’s point of view, a separate independent model with its own binary tree.



The binary tree from the LUMP_NODES section describes the geometry of the map, but is not used for player movement. In addition to the first index, iHeadnodes has three more, each of which points to the beginning of its binary tree in the LUMP_CLIPNODES section (we will call them cliptrees, and the tree from LUMP_NODES the main tree). These cliptrees are obtained from the main one by shifting all the forming planes towards the void by half the size of the model. For example, for a standing player, the walls will move inside the room by 16 units, the ceiling will lower by 36, and the floor will rise by 36 units. The block near the wall will accordingly become larger, and the gap between it and the wall will actually disappear. Why is such a cramped room needed?

When we talked about the movement of the player in previous articles, we imagined it as a shell called hull in the form of a parallelepiped with a height of 72 (in a squat 36) and a width of 32 units on each axis, which, regardless of the direction of view, always retained its orientation. In fact, this “clumsiness” of the hull is due to the fact that for the CS engine the player is actually a point that moves between planes shifted from the brushes by half the size of the parallelepiped.

Of the three cliptrees in the LUMP_CLIPNODES section, the first is needed for a standing player model, the second for some object with dimensions 64x64x64 (we won't be interested in it), and the third for a sitting player model. We will call the nodes of such trees clipnodes. Generally speaking, the number of clipnodes in these trees may differ from the number of nodes in the main tree. For example, if you cover part of the map brushes with a CLIP texture, making them so-called clip brushes, their planes will not participate in the formation of the main tree, and therefore the main tree will have fewer nodes, while these brushes will be invisible in the game. At the same time, this will not affect the clipnodes, and the player’s movement will be impeded by invisible brushes in the same way as visible ones (by the way, the familiar noclip essentially puts the player into a state in which clipnodes are ignored). Another difference between clipnodes is the presence of only two negative index values: -1 indicates the space outside the block and -2 indicates its interior. This is enough to process the player's movement.



Finally, let's look at the list of all sections of the *.bsp file in order to get a more complete picture:

LUMP_ENTITIES - list of entities and their properties
LUMP_MODELS - models (entity brushes refer to models using the key "model")
LUMP_NODES - nodes of the main binary tree corresponding to the brush planes
LUMP_LEAVES - nodes of the main binary tree that describe the contents of the space and correspond to the faces of the brushes
LUMP_CLIPNODES - clipnodes of binary trees for collision handling
LUMP_PLANES - brush planes
LUMP_FACES - brush faces
LUMP_EDGES - brush edges defined by two vertices
LUMP_VERTICES - brush vertices
LUMP_SURFEDGES - indices of edges, with the help of which edges are assigned to the faces containing them
LUMP_MARKSURFACES - indices of faces, with the help of which faces are assigned to nodes from LUMP_LEAVES
LUMP_TEXTURES - textures
LUMP_TEXINFO - coordinates and indices of textures, with the help of which textures are assigned to faces
LUMP_LIGHTING - map lighting data
LUMP_VISIBILITY - data that allows engine to exclude from rendering areas that are obviously not in the player’s field of view

All sections are in close connection with each other and refer to each other (except, perhaps, visibility):



We will continue to look at the features of map compilers and how the game engine works with clipnodes in future articles.