=============================================================================
_ ///// ///// ////// ///// /////
__ _ _ _ ___ | | _____ // // // // // //
/ _` | | | |/ _ || |/ / _ \ ///// ///// ////// // ///// 2.2
| (_| | |_| | (_||| < __/ // // // // //
\__, |\__,_|\___||_|\_\___| ///// // ////// ///// /////
|_|
=============================================================================
|
The only purpose of this document is to make you familiar with the
general structures and concepts of Quake editing.
There is not enough information here for you to start writing an editor
for Quake, not even enough to start making an actual Quake level.
But there are enough hints to enable you to prepare the materials,
and start planning things.
There is also more than enough for you to start dreaming a bit,
while the id guys are still busy on the code.
Quake and DOOM are Trademarks of id Software, inc, hereby acknowledged.
The technical details presented here are all Copyright id Software.
This document is not an official id Software publication.
Do not bother id Software concerning the contents of this file.
Descent is a trademark of Interplay. Dark Forces is a trademark of Lucas Art.
This document is copyrighted. You are not allowed to publish it via any
electronic or non-electronic means without the explicit consent of id software.
You are not allowed to put any part of this document on non-free support (like
magasines, newsletter or CD-Rom) without my prior consent.
In no event shall I be held responsible for any degradation of your health,
wealth, mental sanity or social relations.
All rights reserved. No guaranty. That's life!
Special Thanks to Jens Hykkelbjerg for the first HTML version.
// WAD Header
struct QKHEADER
{ char Magic[4]= "WAD2"; // Name of the new WAD format
long NbOfDirEntries; // Number of entries
long DirPosition; // Position of WAD directory
};
// Directory
struct QKENTRY
{ long Start; // Position of the entry in WAD
long Wsize; // Size of the entry in WAD file
long Size; // Size of the entry in memory
char Ident; // Entry identification
char Cmprs; // Compression
short Dummy; // Not used
char Name[16]; // 1 to 16 characters, '\0'-padded
} Dir[NbOfDirEntries]; // like in DOOM
|
This format is Exactly the same as in DOOM:
struct RGB {char R; char G; char B;} Palette[256];
Internally, the color palette is translated into a much
bigger structure, that takes into account the light level,
just like in DOOM. This structure depends on the number of colors
available on the display, so it might be calculated by the engine
at startup.
Modifying the console lump is of very limited interest.
Here is roughly the format:
The console lump is a similar in structure to the flat pictures
of DOOM. It's a simple lump of color indexes:
char Console [192][128]; //This means it's a 128x192 arrayThe first 64 rows are devoted to the decription of the character font (each ASCII character below 0x80 has a 8x8 cell attached to it. The characters below 0x20 are special).
The rest of the picture is made of four 64x64 quadrant: one grid,
and threes other with somewhar random texture. These might be some
background for the level maps. Who cares actually?
1.2 Picture Format
The pictures will probably used for everything concerning the
status bar (animations, numbers, ...). They are not used for
sprites, countrary to DOOM.
This is essentially the same format as in DOOM, except that the picture is drawn by row, not by columns, and that 16-bit numbers are used, because a screen is 320 or 640 wide.
// Picture header
struct QKPIC
{ long Width; // Picture width
long Height; // Picture height
long Row[Height]; // Offset to the rows, from start of picture
}
// Each column is a set of lumps, placed one after the other.
// if for a lump Hpos=0xFFFF, then it's the end of the set.
struct PICLUMP
{ short Hpos; // Horizontal offset
short Count; // number of pixel
char Pixel[Count]; // pixels color index (in current palette)
char Dummy[Count&1]; // to align the structure PICLUMP on 16-bit boundary
}
Those textures are used to cover the walls, the floors, the ceilings and the skies surfaces. Actually, they just cover any surface. Those textures are NOT used for sprites or Entity models, so those models are not (yet?) protected from ugly aliasing effects.
If the texture is not animated, the name can be anything, provided the first character is not '*', the asterisk.
//Texture header
struct TEXHEAD
{ char Name[16] // Texture name, useless. To be removed?
long W; // Width
long H; // Heigth
long Scale1Pos; // pointer to Tex, scaled 1
long Scale2Pos; // pointer to Tex, scaled 1/2
long Scale4Pos; // pointer to Tex, scaled 1/4
long Scale8Pos; // pointer to Tex, scaled 1/8
}
// At offset Scale1Pos, from start of file
// Picture, scale 1
char Tex1[ W*H];
// At offset Scale2Pos, from start of file
// Picture scaled by 1/2
char Tex2[ (W/2)*(H/2)];
// At offset Scale4Pos, from start of file
// Picture scaled by 1/4
char Tex3[ (W/4)*(H/4)];
// At offset Scale8Pos, from start of file
// Picture scaled by 1/8
char Tex4[ (W/8)*(H/8)];
All those Tex1, Tex2, Tex3, Tex4 represent color indexes, And the
picture is 256 colors. The picture palette is usually indicated in
the begining of the WAD that contain a set of textures.
The color palette index zero is used to represent transparency.
The sampling theorem states that when you sample any signal (sound, picture, anything) the highest frequency contained in this signal must be at most one half of the sampling frequency. If there is any frequency above that, the sampling process will map it into a lower frequency, thus creating a terrible mess into the sampled signal. This mess is called Aliasing.
When you try to display a picture on a smaller space, you increase all the frequencies contained in that picture, and thus risk Aliasing. That's basically what happend in DOOM at long distance.
Now, all you need is only to low-pass filter the picture, with a
cut frequency equal to half the sampling frequency. Easy! But...
There is no DSP on the video memory, so those calculations would
take too much time.
It's much easier to pre-calculate 4 scaled down pictures, that
can be used across the most common range of scales:
infinity-1, 1-1/2, 1/2-1/4, 1/4-1/8.
Below 1/8, there will be some aliasing...
Here is how the right texture is selected in Quake:
int R_MipLevelforScale(float scale)
{
if(scale>= 1) return 0; // 1 and above. no aliasing.
if(scale>= 0.4) return 1; // shouldn't it be 1/2 ?
if(scale>= 0.2) return 2; // shouldn't it be 1/4 ?
return 3; // down to 1/8 (below, aliasing!)
}
This 3D structure is real simple compared to the formats used by 3D Studio or even POV, so conversion should be possible.
However, Quake will also necessitate 3 special structures which are not common to 3D graphic packages:
Of course, if you intend to edit Quake levels, chances are that you will never have to deal with the BSP tree itself. What you will edit is a rather complex 3D map, a bit like those of DESCENT, except that almost any shape is allowed, not only combination of cubes.
Quake will require a very clever 3D editor, because there seems to be quite a lot of things to calculate that can't entirely left to the user, light ambient lights, alignement of light maps and texture offsets.
the BSP tree is made of nodes, starting with a root node, which has two childs, which in turn have two childs, and so on, as you go down the branches of the BSP tree. The nodes only represent a way to partition the space, they do no ever appear in a level.
Some of the childs are extremities of the branches. They are called BSP tree leaves, and in fact each branch must be terminated by one leaf. Those leaves are in fact portions of the actual 3D level, and usually they represent portion of rooms. So to any leaf is associated one or more surfaces, that represent the actual walls, floors, ceilings and sky for this portion of level.
Those surfaces are defined by a plane in which they lie, an ordered set of vertex, that define their boundary, an constant base light level, a single texture, and a light map and offsets for the texture.
The textures are defined by a reference to a picture or a set of animated pictures, some base offsets, and some flag that say if they must be flipped horizontally, vertically or both.
I seriously doubt you could make any sense of the above, so there is some
more details, to add to the confusion. If by the end of this chapter you
still don't understand how the level are organised, go play DESCENT to
increase your experience with 3D volumes :-)
2.3 The Tree Leaves (Sectors)
The tree leaves are the Quake equivalent of the sectors in DOOM.
You can imagine them as rooms, or part of rooms, where the monsters,
players and object will be placed.
Actually the tree leaves are the equivalent of the Sub Sectors: each sector in DOOM is decomposed by the BSP into smaller and simpler convex sub sectors, that contain only part of the sector lines.
Technically, each tree leaf, made of some surfaces and bound by the BSP node split lines, appears in 3D space as a convex polytope.
Think of them as big rooms without any corners where you can hide from any part of the room. (Sorry, I'm just trying to be AOLicaly correct).
Well, if you don't understand the above, I'm real sorry but the best you can do is go ask your mother for a system upgrade.
Technically, a tree leaf is defined by
Depending on the name of their texture, they will appear are a sky texture, or as a wall or floor (that can eventually be animated). Note also that though the skies are ordinary wall textures, they are drawn in a very special way, that make them look like skies. That is basically the same trick as in DOOM, except that it doesn't need to use a F_SKY fake sky marker.
The surfaces will be rendered as a texture-mapped polygon. The texture somewhat takes into account the distance, for better realism. Technically, the polygon is split based on the inverse of the distance, and fragments are mapped linearly.
The texture mapping also takes into account the orientation of the surface, because calculations of points in texture space is done by selecting only 2 coordinates among the three coordinates of the points. So depending on the orientation of the surface, the most representative set of coordinates must be chosen.
Technically the surfaces are defined by:
This is a contrast with DOOM, where that kind of passage had to
be indicated by two sided lines. There is no 2 sided surface, unless
you want to create a transparent wall (and even then, it would
be made of two independant surfaces).
2.5 Texture definitions
The texture definitions are not actual textures, but rather special
references to the true textures. One or more texture definition can
point to the same texture data, and it will look somewhat different
each time.
There is no equivalent of this intermediary texture definition in DOOM.
Each texture definition contains:
They are the Quake equivalent of the DOOM Linedefs and Segments.
The planes are defined by a normal vector and a distance. This normal verctor must be of norm 1.
The plane equations are used for distance calculation and to determine if a given vertex (of a surface, or an entity) is on the front side or the back side of the plane.
It is highly recommended that if a node and some set of surface use
the same plane equation, they point to the same plane definition.
2.7 Vertex definitions
The Vertex as the Quake equivalent of the DOOM vertex. the only
difference is that they are in 3D, not in 2D.
There can only be 12 vertex per face, and in fact, 16 vertex when taking into account the clipping of the face by the BSP planes. In fact, there are so many limitations related to this 16 number of vertexes that we can expect it's only temporary.
2.8 BSP tree Nodes definitions
The nodes are the Quake equivalent of the DOOM nodes and also of the
DOOM blockmaps. They are parts of a 3D BSP tree, not a 2D BSP tree
like in DOOM.
The nodes are used for level display, placements of entities and collision detections (and maybe even more). So there is no need for a blockmap in Quake.
Technically, nodes are defined by:
The front child node (and all the nodes below it) is entirely contained in the half-space that is in front of the split plane.
The back child node (and all the nodes below it) is entirely contained
in the half-space that is in the back of the split plane.
(The 'front' and 'back' of a split planes are defined by the plane
equation giving a positive or negative result for any given vertex)
If the split planes reference is -1, then in fact the node is a tree
leaf, see the definition above.
2.9 Visibility list
This tricky structure is the Quake equivalent of the REJECT map
of DOOM. And yes, it will take ages to calculate (I hope not!).
Unfortunately, it is much more important than the REJECT map, since it can be used to make the level rendering much faster. This is due to the fact that sectors are now the leaves of the BSP tree.
The REJECT map in DOOM was only used to control the monster's behaviour. It could not be used for rendering, since it was sector based.
So it can be expected that the REJECT special effects of DOOM (blind monsters and such) are something of the past... though in fact, screwing the visibility list is a very good way to obscure some areas of the levels. But I'm not sure Quake will be of much fun in blindfold mode.
Basically, the Reject map is an array of bits, one array per tree leaf. The bit number n, if set to 1, tells that when laying in the tree leaf, one can see the leaf number n.
When the player is in a leaf, the engine finds all the leaves that
are visible from that leaf, and tag those leaves. Then it tags back
all the nodes that are above the tagged leaves.
That way, only the part of the BSP tree that is really visible will
actually be tagged, and later displayed.
2.10 Lighting
Recent information released by id software indicate that the light
mapping and shadowing in Quake would be done dynamically. The fact
that everyone thinks it's damn impossible to make any dynamic shadowing
on a 486 or pentium is only a minor concern.
I sincerly hope that the description below is outdated.
Quake apparently uses some static light model: the shadows are not calculated for each moving sources, but are pre-determined once for all when the level is finished, taking into account the light sources existing at that moment.
There is no Gouraud or Phong shading calculated in real time. It happens that those hyped shading models are rather meant for curved objects approximated by polygons. Since Quake levels are polygons, not approximations, there is absolutely no reason to use Gouraud or Phong.
The way Quake makes it's surface lighting so realistic is a bit special. It works with each surfaces independently of others, and the lighting is only calculated once for a set of similar surfaces.
The basic idea behind the Quake lighting is to take into account 3 things:
There is one such light level for each surface, and we can assume it depends on the orientation of the surface, and on the static light sources defined before the level is calculated. I suppose that a good Quake editor would let the user define some sources of lights (windows, torches, sky) and then do the lighting calculations once and for all, for all surfaces. Of course, this is fairly primitive (no way to move torches, to switch off lights) but then again the game engine could possibly update this static light in real time, under certain conditions.
It could be that this basic light level, like in DOOM, can evolve dynamically, depending on action on switches. It is even possible that it is calculated in real time, taking into account the moving light sources. That would make only a very crude approximation of a shadow, but maybe that is enough.
This light level is used to select an internal color palette. Then using the texture's color index and an index in this palette, it's possible to find the actual lighted color. This mechanism is basically the same as in DOOM, except that there is 256 (?) color palettes, not 32. This mechanism takes into account both 8-bit or 16-bit color palettes, so Quake will look better on 16-bit per color display, but will still run on 8-bit per color display.
DELETED BECAUSE OBSOLETE
The format will probably be some ASCII.
I'm not going to explain in details how the Quake 3d engine works. It wouldn't be fair to id software, and anyway I still don't understand a lot of critical features. Also, if such an explanation was to be read by the conceptors of Quake, chances are that they would die laughting, and I don't want to take that risk.
Let's say only that the Quake 3D engine looks like an ordinary texture-mapped polygon engine, where the polygon sorting is not done via classical backface elimination and distance sorting, but by using a BSP tree. Of course, there are many more clever tricks, which are not supposed to be made public.
Countrary to DOOM, there is no ray-casting, so some surfaces are sometime rendered, then later overwritten by closer surfaces. Hence the visibility list is critical for this engine, otherwise it might really crawl.
The Quake engine bears definitely no relation to the Descent level display engine, though there might be some similarities with the engine that display the vessels of Descent.
Well, this description gives only the general features of the Quake engine, and actually don't make a lot of sense. Here are some temporary conclusions:
How does it work?
First imagine a wireframe model of the entity, made of triangles. This gives
the general shape of the entity. For instance, imagine you have the general
shape of a cow, made of triangles in 3D space.
The extremities of the triangles are the 3D vertexes, and countrary to level models, there is no need for elaborate stuff like nodes, planes, polygon surfaces. Only triangles and vertex.
Now, there is something missing: the skin. A cow without skin looks
pretty ugly.
Imagine that you have a flat carpet made of the skin of an unlucky cow.
All you need to do is put some parts of this carpet at the relevant place
on the wireframe model of the cow, and you'll get a fairly realistic
(though a bit polygonal) cow.
That's the way if works with the alias models.
For each triangle in the wireframe model of the cow, there will be a corresponding triangle cut from the skin picture. Or, in other words, for each 3D vertex, extremity of a triangle, there will be a corresponding 2D vertex positionned on the skin picture.
It is not necessary that the triangle is 3D space and the triangle on the skin picture have exactly the same shape (in fact, it is not possible for all triangles) but they should have shapes roughly similar, to limit distortion and aliasing.
That's all Quake needs to display an alias model. It's quite easy
to understand, but unfortunately editing such a structure may
be troublesome.
3.2 Animating alias models
Once the general shape of the model (for instance, a cow) is defined,
and the skin is mapped correctly on that shape, animation is pretty
straightforward: just move the triangles around and it will seem
to move.
To move the triangle, you need only modify the position of the 3D vertexes at the extremity. For instance, to move the leg of the cow, you will move the vertexes that define the extremity of the legs. You will also move the other vertexes a bit, so that the movement looks less mechanical.
Chances are that creating a fine looking animation is gonna be a very tough job, a bit like with the DOOM sprites. I would bet that the quality of the animation will be the most critical point.
Note that the animation consists only in changing vertex
positions (and that's why there is one set of vertexes for each
animation frame).
The skin of the cow is not modified, neither are the definition of
the triangles. So blood stains cannot suddenly appear on the skin,
and parts of the cow cannot fly away, separated from the rest.
That is... unless you use some tricks, that I leave to your
imagination.
Note also that the animation is based on frames, like in DOOM.
The animation is defined once and for all, and there is no
squeletal model or any similar physical model involved in the
calculations of the movements.
Of course, nothing in the structure of the Alias model strictly
forbids to use a physical model for the entity.
But is much more clever to write some well thought program to control
the animation sequences (and Quake allows that) than to waste precious
time calculating some approximate physical model.
3.3 Rendering of alias models
The rendering of entities is a bit more complicated than the ordinary
back-face elimination and triangle sorting that is common in games
like X-Wings, Terminal Velocity or the like. It doesn't use a BSP
tree like Descent (or so they say), but it takes into account the
BSP tree structure of the Quake levels.
There is no need to bother about the engine. Just keep this in mind:
DELETED BECAUSE OBSOLETE
The format may become some ASCII.
All you need to know is that there is only one picture, and
that frames are done with vertex, rather than with changes in
the picture.
The sound has to be mono, not stereo, because the stereo effect
is calculated by the game, for spatialisation.
It is possible that the 16-bit sound drivers are not yet written,
but actually since Quake uses many channels and different volumes
per channel, the sum is tantamount to a 16 bit sound.
Note that the 3D engine is using a similar trick: 256 color textures,
converted to 16 or 24 bit colors by using lights.
Now, the file format: the expected file format is WAV, but in fact
the sound loading code is really simplified, and only a very special
sub case of the WAV format is tolerated: a 8 bit mono sound, with
no special features and especially no built-in comments.
If you are using a good WAV program, it is possible that it uses a
more complex format. So don't be surprised if your file is rejected.
Location of sound sources toward player
The sound spatialisation is done by using a simplified model,
that doesn't take into account difference in phases, and echoes.
Basically, the sound itself is not modified, only the volume of the right and left channels are affected.
Let's just say that Quake maintains a representation of the world were
entities can be added an removed dynamicaly, and players can log in
at any moment. Not really surprising...
The server seems to sends continuous updates the clients, but these updates are non-synchronous, contrary to DOOM. That means server and clients go at their own pace, but it's the server that keeps track of the game time.
The data exchanged is not compressed, and thus only suitable for transmission over a LAN, certainly not a 14.4k modem. This will change.
This part will be updated later.
The description of the language here is totally outdated. It was probably rewritten for efficiency. Since it must be parsed during the game play, it had better be simple to parse, so the C-like syntax will have to be improved.
The names of variables in the code are reminiscent of MUDs code,
and there is all reason to believe Qu*ke will be MUD-like.
Of course, there isn't much code compared to even the simplest MUDs.
There is code that describe how the Qu*ke server should handle
the clients, as they join an existing world. BTW, they can join
dynamically, like in DESCENT. And they can join the level they wish.
The Things are all represented by C-like objects, with a set of attributes whose name are fairly intuitive (frags, velocity, health...) and the language provides a set of functions of the basic stuff.
Vectors values are represented as character strings like "1 2 3", and can be added, scaled and multiplicated. The attribute think is used to tell or what code function the object shall apply. The attribute nextthink is used to tell when the next call to the object's code shall happen.
Like in DOOM, the Object/monsters will be implemented as finite state automats, based on frames. But you won't need DeHacked to read them. The Objects frame tables are provided in the code (with a special macro structure, that expands trivialy into code)
The language seems syntacticaly clean, but there seem to be no strict type checking anywhere, so odds are that any complex code module will be real difficult to debug. Not to mention the 'goto' lying around. I wonder what happen when one mixup frames from different monsters... Apparently the language is entirely event driven (not a surprise) and timers can be set for certain events. Mind the event loops!
No details will be given on the actual code: the parser and probably the language were rewritten by id, for more efficiency.
It is not known if some fair level of AI can be implemented using this
language. I seriously doubt it is possible to manipulate some accurate
representation of the world. Quake isn't really a wargame, is it? ;-)
6.2 List of Entities
The entities represent the monsters, players, objects and probably
various other stuff.
Each type of entity is much like an object class, with a list of
parameters that define various default parameters, like the model
used fo represetn the entity, the Quake Programming language
file that defines the behaviour of the entity (the 'think' parameter)
and similar properties.
Here is an example of entity type definition. It looks like some LISP syntax, with { } instead of ( ). This is probably because the parsing of LISP syntax is real easy and non-ambiguous.
{
{classname "bestiole"}
{color "1.0 0.9 0.4"}
{orgofs "64 64 80"}
{size "32 32 70"}
{model "s_bestiole"}
}
The light maps were a trick used in early versions of the Quake engine. It was a way to implement some cool shadows without too many calculations involved. Countrary to what was supposed initially, it bears no relation to dynamic changes in the light level.
Example:
ccmdefabcdefgmmmmaahijlkmmaamm 9 BOUGIE (third variety)See the level description to know how these light maps are used in levels. They don't seem to be used with entities.
Here are the known movements:
turn left/right, up/down, move front/back strafe left/right, up/downno key is defined for roll turn, jump, climb, fly. This may/should change.
Let's just say that the code if id is characterised by... the absence of almost all security tests. That means that if the data structures are not 100% perfect, the code will bug or crash without warning. This is especially true when you deal with indexes. Don't even make a mistake on an index, in a file.
It can be noted that the code was not optimised at all and used floating numbers (and thus, used the floating point unit). This makes it especially unsuitable for 386 (no surprise) and in fact unsuitable for anything below an helium-cooled 300 Mhz 686, with 500k of primary cache and 20 meg of s econdary cache. However the code was certainly completely rewritten and optimised since these first experiments, and it will run at decent speed even on a DX2/66 (Or, shall I say, DESCENT's speed. At least.)