Date: Wed, 30 Nov 94 15:53:56 NZD From: greg@cosc.canterbury.ac.nz (Greg Ewing) Subject: Wolfenstein 3D First Encounter Level Format Wolfenstein 3D First Encounter Level Format =========================================== Greg Ewing greg@cosc.canterbury.ac.nz Here is a summary of what I have learned about the format of the level resources used by Wolfenstein 3D First Encounter. 1. Map List resource -------------------- The Map List is in BRGR resource 146. It begins with a 2-word header: Offset Size Description 0 word Number of levels 2 word Resource ID of the first level Following this is a 5-word entry for each level: 0 word Next level (offset from first level ID) 2 word Alternate next level 4 word Par time (seconds) 6 word Major floor number 8 word Minor floor number 2. Level resource ----------------- The levels themselves are also kept in BRGR resources. The ID of the first level resource is determined by the map list as described above. The original levels use IDs 200 and upwards. The level resource consists of a fixed-length part followed by a variable-length part. The fixed-length part can be further subdivided into a map and a zone table, and the variable- length part into a header, an object table and a BSP tree. 2.1 Map ------- The map section is 4096 bytes long, organised as a 64 by 64 grid. Each byte in the map represents either a solid block, a door or an empty space. If bit 7 of the byte is 1, then it represents a solid block or door, and the rest of the bits determine what kind of wall or door it is. If bit 7 is 0, the byte contains a room number. A room is a contiguous space which is completely divided off from other rooms by walls or doors. There may be up to 64 rooms, numbered 0 to 63. Each byte in the map representing an empty space contains the room number to which the space belongs. 2.2 Zone table -------------- This is a 64-byte table containing a zone number for each room. I'm not entirely certain of the function of this table, but it seems to affect which guards are "woken up" when you enter a room. The rooms can be grouped together into zones; when you enter a room, the guards in that room and any other rooms belonging to the same zone are alerted and will seek you out. 2.3 Header of variable-length part ---------------------------------- The variable-length part begins with a 4-word header. Entries marked with * are stored in little-endian byte order (least significant byte first). 0 word Number of objects 2 word Offset from start of resource to object table 4 word Number of entries in BSP tree 6 word Offset from start of resource to BSP tree 2.4 Object table ---------------- The object table contains an entry for each object appearing on the level. Each entry is either 3 or 4 bytes long, depending on the object type. 0 byte x-coordinate of map cell (0 to 63) 1 byte y-coordinate of map cell (0 to 63) 2 byte Object type If the object type is $62, then the object is a secret door. In the map, a secret door appears as an empty space, and there is an extra byte in the object table entry containing the wall type: 3 byte Wall type of secret door (object type $62 only) 2.5 BSP tree ------------ 2.5.1 About the BSP tree A Binary Space Partitioning or BSP tree is used to divide the map space up into portions in such a way that the rendering engine can efficiently determine which parts are visible. The BSP tree consists of two types of nodes, terminal and non-terminal. Each node corresponds to some rectangular portion of the map. A non-terminal node is further subdivided into two child nodes. A terminal node is not subdivided any further and has no children; it is a "leaf" of the tree. A terminal node consists of a collection of segments. A segment represents part of a wall - a boundary between an empty and a filled-in region of the map. The coordinate system used to describe segments has twice the resolution of the map cell coordinate system used in the object table. Furthermore, instead of referring to cells, segment coordinates refer to the dividing lines between cells. So, whereas cell coordinates range from 0 to 63, segment coordinates range from 0 to 128. Even segment coordinates correspond to the lines running between map cells; odd segment coordinates refer to lines which pass through the middle of map cells. (The reason for this will become clear later.) Each segment is described by three coordinates. For segments running east-west these are its position in the y direction and the x-coordinates of its two endpoints. For segments running north-south, the roles of x and y are reversed. Each segment also faces in a particular direction. An east-west segment can face either north or south, and a north-south segment can face either east or west. The direction a segment faces determines from which side it will be visible; the rendering engine doesn't bother drawing segments which are facing away from you. A terminal node of the tree contains a collection of segments such that no segment can obscure part of any other segment from any viewing position. 2.5.2 Format of the BSP tree The BSP tree consists of a sequence of 6-byte entries, numbered from 0. The root node of the tree begins at entry 0. Each non-terminal node takes up one entry structured as follows: 0 byte Split coordinate For an east-west split, this is the y-coordinate of the splitting line; for north-south, the x-coordinate. 1 byte Flags Bit 7 of this byte is 0, indicating a non-terminal node. Bit 0 indicates the direction along which the space covered by this node is split to create the subspaces of its child nodes. 0 means the splitting line runs east-west, 1 north-south. 2 word* First child Entry number of the first child node. The subspace covered by this child is the one with coordinates *greater* than that of the splitting line. 4 word* Second child Entry number of the other child node. The coordinates of the region covered by each node are not explicitly stored in the node; rather, they are implicit in the coordinates of the splitting lines at each step, and the fact that the root node covers the whole of the map. Each terminal node takes up one entry for each segment as follows: 0 byte Segment position For an east-west (or north-south) segment, this is the positition of the segment in the y (or x) direction. 1 byte Flags Bit 7 of this byte is 1, indicating a terminal node. Bit 6 is set to 1 if this is the last segment belonging to this node; 0 if more are to follow. Bits 1 and 0 indicate the orientation of the segment: 00 North-south, facing east 01 East-west, facing south 10 North-south, facing west 11 East-west, facing north 2 byte Start coordinate 3 byte End coordinate For east-west (or north-south) segments, these are the x (or y) coordinates of the segment's endpoints. 4 byte Map row/column For east-west segments, this is the map cell coordinate (0 to 63) of the map row containing the wall block immediately behind the segment. For north-south segments, it is the column number plus 64. (For segments associated with doors, this byte has a different interpretation - see below.) 5 byte Room number This is the room number of the room into which the segment faces. 2.6 Doors --------- A door is represented by an entry in both the map and the object table, the object having the same code as the map entry with bit 7 set to 0. Bit 0 of the door code indicates the direction of the door: 0 for a doorway leading east-west, 1 for north-south. Associated with a door are four special segments, one each side of the door facing inwards, and one along each face of the door itself (the sliding part). The latter two are positioned in the middle of the map cell containing the door. The side segments have byte 4 of the segment entry set to $80. The sliding segments have this byte set to $80 plus the door number: each door on a level has a unique number from 1 upwards. 2.7 Lifts --------- The lift control panel and the side panels with hand railings are represented in the map by the same code ($8F). If you are looking at the east or west face of the block, it appears as a lift control panel; if you are looking at the north or south face, it appears as a hand railing. However, the lift control panel also has an object with a code of $64 at the same location. It is the presence of this object which causes the block to behave like a lift when you operate it. If this object is not present, the control panel is just another piece of wall. Conversely, placing a $64 object on top of some other type of wall will make it behave like a lift. This could allow for some very unfair levels... 2.8 Hidden passages ------------------- The secret blocks which move back when you push on them involve special arrangements in the map, object table and BSP tree. In the map, the location of the secret block is an empty space, and the area to which it leads is part of the same room as the area it leads from. An object with code $62 is placed at this location: this is the object you operate when you push on the block. The object table entry for this object has an extra byte appended, containing the wall code which would otherwise have been placed in the map at that location. The secret block has two segments associated with it. One of them is positioned on the outside of the block in its initial position, facing towards the player as he stands in front of the block ready to push it. The other segment is positioned on the other side of the block, but facing in the same direction - in other words, it is in the place the first segment would end up after the block had been pushed one map cell. Byte 4 of both these segments refer to the block's initial location. It is also necessary to place an ordinary block of the same type two cells away in the direction of motion, i.e. in the place where the secret block will end up after it has been pushed. If this is not done, not only will the block vanish after opening, but for some strange reason it may not display properly in its initial position. 2.9 Map codes ------------- Here is a list of the codes which may be placed in the map for various types of walls and doors. 2.9.1 Wall codes $81 Grey stone $82 Grey stone with archway and eagle emblem $83 Grey stone with swastika wall hanging $84 Grey stone with Hitler portrait $85 Wood panelling $86 Wood panelling with eagle emblem $87 Wood panelling with Hitler portrait $88 Wood panelling with purple cross $89 Blue stone $8A Blue stone with cell door $8B Red brick $8C Red brick with eagle emblem $8F Lift side wall or control panel $91 Metal plate $9A Yellow stone with blood stain $9B Yellow stone blocks $9D Concrete(?) blocks 2.9.2 Door codes $DA Plain east-west $DB Plain north-south $DD Gold key north-south (Note: there is no gold key east-west door!) $DE Silver key east-west $DF Silver key north-south $E0 Lift door east-west $E1 Lift door north-south 2.10 Object codes ----------------- Here is a list of codes which may be placed in the object table. 2.10.1 Player starting positions $13 Facing north $14 Facing east $15 Facing south $16 Facing west 2.10.2 Ornaments $17 Puddle $18 Oil drum $19 Table $1A Standard lamp $1B Chandelier $1E Tree $1F Flag pole $20 Pot plant $21 Urn $22 Bones $23 Ceiling light $24 Bowl $25 Suit of armour $26 Hanging cage $36 Water tub 2.10.3 Useful items $1C Dog food $27 Gold key $28 Silver key $29 Backpack $2A Ammunition box $2B Food $2C First aid kit $2D Ammunition clip $2E Machine gun $2F Gatling gun $34 Extra life 2.10.4 Treasures $30 Jewelled cross $31 Goblet $32 Treasure chest $33 Crown 2.10.5 Enemies $6C Brown uniform $6E Blue uniform $6F Dog $71 Boss $7E Brown uniform, waiting to ambush Greg Ewing, Computer Science Dept, University of Canterbury, Christchurch, New Zealand greg@cosc.canterbury.ac.nz