ModdingWiki - User contributions [en-gb]

GameMaps Format

2024-10-22T00:14:25Z

VKokielov: removed misinformation -- I forgot to add pragma pack() to my struct declarations

{{Map Infobox
| Type = 2D tile-based
| Layers = 3
| Viewport = ''Varies by game''
| Games =
{{Game|Bio Menace}}
{{Game|Blake Stone}}
{{Game|Catacomb 3-D}}
{{Game|Catacomb Abyss}}
{{Game|Commander Keen Dreams}}
{{Game|Commander Keen 4-6}}
{{Game|Corridor 7 Alien Invasion}}
{{Game|Dangerous Dave 3}}
{{Game|Dangerous Dave 4}}
{{Game|Super 3-D Noah's Ark}}
{{Game|Operation Body Count}}
{{Game|Rescue Rover 2}}
{{Game|Spear of Destiny}}
{{Game|Wolfenstein 3-D}}
}}

The '''GameMaps Format''' stores levels in a number of [[:Category:id Software|id Software]] games. The filenames and compression varies somewhat across different games but all files stored in this format were produced by the [[TED5]] level editor.

There are three main varieties of the file format. The most basic version is just [[RLEW compression|RLEW compressed]], the other two are either [[Carmack compression|carmackized]] or [[Huffman Compression|Huffman compressed]] on top of the RLEW compression. Each variation has its own file naming scheme and pattern of external/internal files.

There are two main components to the format. The game maps proper, which contain the actual level data, and the map headers, which contain both the location of each level's data within the game maps file, and the tile info for the game.

== Variants ==

{|class="wikitable"
! Game !! RLEW !! Carmackization !! Huffman !! Head || Gamemaps || Notes
|-
| Bio Menace || Yes || No || No || maphead.bm[123] || maptemp.bm[123] || gamemaps.bm[123] and mapthead.bm[123] are present but not used
|-
| Blake Stone: Aliens of Gold || Yes || No || No || maphead.bs[16] || maptemp.bs[16] ||
|-
| Blake Stone: Planet Strike || Yes || No || No || maphead.vsi || maptemp.vsi ||
|-
| Catacomb 3-D || Yes || Yes || No || Inside .exe || gamemaps.c3d ||
|-
| Catacomb Abyss || Yes || Yes || No || Inside .exe || gamemaps.abs ||
|-
| Catacomb Apocalypse || Yes || Yes || No || Inside .exe || gamemaps.apc ||
|-
| Catacomb Armageddon || Yes || Yes || No || Inside .exe || gamemaps.arm ||
|-
| Commander Keen Dreams || Yes || No || Yes || Inside .exe || gamemaps.kdr (v1.00), kdreams.map (v1.01+) ||
|-
| Commander Keen 4-6 || Yes || Yes || No || Inside .exe || gamemaps.ck[456] ||
|-
| Corridor 7 Alien Invasion || Yes || No || No || Inside .exe (cd, disk), maphead.dmo (demo) || maptemp.co7 (cd, disk), maptemp.dmo (demo) || Uses MAPTEMP.xxx (only RLEW compression)
|-
| Dangerous Dave 3 || Yes || No || Yes || Inside .exe || gamemaps.dav ||
|-
| Dangerous Dave 4 || Yes || No || Yes || Inside .exe || gamemaps.dav ||
|-
| Super 3-D Noah's Ark || Yes || Yes || No || maphead.n3d || gamemaps.n3d ||
|-
| Operation Body Count || Yes || No || No || maphead.bc (cd, disk, demo 2), maphead.co7 (demo 1) || maptemp.bc (cd, disk, demo 2), maptemp.co7 (demo 1) || Uses MAPTEMP.xxx (only RLEW compression)
|-
| Rescue Rover 2 || Yes || Yes || No || Inside .exe || gamemaps.rr2 ||
|-
| Spear of Destiny || Yes || Yes || No || maphead.sod || gamemaps.sod ||
|-
| Wolfenstein 3-D (v1.0) || Yes || No || No || maphead.wl1 || maptemp.wl1 ||
|-
| Wolfenstein 3-D (v1.1 and above)|| Yes || Yes || No || maphead.wl[16] || gamemaps.wl[16] ||
|}

The games that use Huffman compression will have a MAPDICT (embedded in the game's main executable). Those missing the map dictionary are not Huffman encoded.

To work out whether Carmackization is used, read the first UINT16LE in a map plane (the field storing the decompressed size). If the value matches the expected size of the plane (i.e. width * height * 2), then only RLEW compression is used. If it doesn't match, check the second UINT16LE in the file (which will become the first UINT16LE once Carmackization has been removed). If this matches the expected plane size then the plane must first have Carmackization removed followed by removal of RLEW. The exception to this rule are plane sizes that have either 0xA7 or 0xA8 as the high byte (i.e. any value from 0xA700 to 0xA8FF), as those values would have been encoded differently by the [[Carmack compression]] algorithm.

== Data structures==

The map data is split into two files: The map header (<tt>MAPHEAD.xxx</tt>) and the main map file (usually <tt>MAPTEMP.xxx</tt> or <tt>GAMEMAPS.xxx</tt>). The map header may be embedded in the game's main executable.

<tt>MAPTEMP.xxx</tt> is the working format saved by [[TED5]] when maps are being edited and can be directly accessed and edited by this utility, allowing changes to be made to the game. Note that if the MAPHEAD file exists as an external file, the game always reads it from a file named named <tt>MAPHEAD.xxx</tt> for both the <tt>GAMEMAPS.xxx</tt> and the <tt>MAPTEMP.xxx</tt> variation. TED5 also saves a <tt>MAPTHEAD.xx</tt> file when editing maps, but that file is only used by TED5 and usually omitted from any game release.

The maps were often compressed even further for the public release versions of the games. This more compressed version of the map file was saved as <tt>GAMEMAPS.xxx</tt> by TED5. Later releases would omit the additional compression layer and ship with the <tt>MAPTEMP.xxx</tt> file instead. One possible reason for this could be that the size of the games grew to the point where they would no longer fit onto and be playable from a single floppy disk, and therefore the additional compression was no longer worth the amount of time it took to compress the maps and re-compile the code.

=== Map headers (MAPHEAD) ===

{|class="wikitable"
! Offset !! Type !! Name !! Description
|-
| 0 || [[UINT16LE]] || magic || Magic word signalling [[RLEW compression]]
|-
| 2 || [[INT32LE]][100] || ptr || 100 pointers to start of level 0-99 data in the game maps file
|-
| 402 || {{TODO|Unknown}} || tileinfo || Optional tileinfo data
|}

The map header file (MAPHEAD) is of varying length and contains three main types of data.

* The first is the magic word or flag used for RLEW compression, which is almost always $ABCD in the original files. It could be changed to any other value if necessary.

* The second is 100 level pointers which give the location of the start of level data in the GAMEMAPS file, relative to the start of that file. A value less than 1 indicates no level (generally 0, but occasionally -1 (0xFFFFFFFF) is used). Using -1 should be preferred over 0, as the pre-Wolf3D version of the engine will treat any negative value as "a non existant map" [sic!] and quit with an appropriate error message, while 0 will cause it to try reading a level header at offset 0 (where the "TED5v1.0" string is usually stored), which will cause all kinds of errors as there is clearly no valid level header at that offset.

* The third is the tileinfo data, which contains tile properties for each tile used in level creation. (These are masked and unmasked and either 8x8, 16x16 or 32x32.)

Many programs treat the tileinfo as a separate file from the MAPHEAD and it is possible to modify a game in this manner. Indeed, some games such as Wolfenstein 3-D do not have any tileinfo data at all in the map header file (giving a total file length of 402 bytes.) However TED5 works with any tileinfo data in the MAPHEAD.

=== Map data (GAMEMAPS) ===

The GAMEMAPS file consists of the string "TED5v1.0" and a number of compressed chunks of varying length. Each level in the file will have from two to four chunks (usually four) depending on the game, with all levels in a given game having the same number of chunks. These are the level header and 1-3 planes (foreground, background and sprite/info.) The chunks are in no particular order and it is possible to read through the entire file decompressing chunks as they're found.

Chunks are ordered by the MAPHEAD file, which will point to the GAMEMAPS level header chunks which in turn contain pointers to the other GAMEMAPS chunks used by that level.

All level data is in the form of [[UINT16LE]] values (or in the case of pointers, [[UINT32LE]].)

==== Level headers ====

The header for each level inside the GAMEMAPS file (which is pointed to by MAPHEAD) is 38 bytes long and ''never'' RLEW compressed. If the GAMEMAPS file is using Huffman compression, the level header itself is Huffman-compressed. In that case, the size of the compressed level header can be found in the MAPHEAD file. Since the uncompressed level header always has a size of 38 bytes, that size is not stored at the beginning of the compressed data. The header is sometimes followed by a signature "!ID!" string, which would give the header a total size of 42 bytes, but that string is not part of the actual level header.

The expanded size of each map plane is the size of a word ([[UINT16LE]]) times the width times the height. This is the final, expected size and can be precomputed even if there are two layers of compression.

Plane 0 is background using unmasked tiles, plane 1 is foreground and uses masked tiles, and plane 2 is sprite/info. Levels must contain a background plane and usually an infoplane.

For the compressed size of each level plane, a value of 0 indicates the plane does not exist. The offset value for unused planes appears to be set to a random number with the most significant byte set to 0xFF, making it either a negative number or an offset close to the 4 gigabyte range. The games only check the compressed size and ignore the offset if the size is 0.

Note that Wolf3D is hard-coded to always load the first two planes, even if the compressed size of a plane is 0. Wolf3D also ignores the width and height stored in the level header and just assumes the level is 64x64 tiles. This also applies to Blake Stone and probably any other game based on the Wolf3D code.

All versions of the "Id Software Caching Manager" ignore the expanded size value at the beginning of the RLEW data and just assume that the size is the same as the size of the plane (width * height * 2).

{|class="wikitable"
! Offset !! Type !! Name !! Description
|-
| 0 || [[INT32LE]] || offPlane0 || Offset in GAMEMAPS to beginning of compressed plane 0 data (or <= 0 if plane is not present)
|-
| 4 || INT32LE || offPlane1 || Offset in GAMEMAPS to beginning of compressed plane 1 data (or <= 0 if plane is not present)
|-
| 8 || INT32LE || offPlane2 || Offset in GAMEMAPS to beginning of compressed plane 2 data (or <= 0 if plane is not present)
|-
| 12 || UINT16LE || lenPlane0 || Length of compressed plane 0 data (in bytes)
|-
| 14 || UINT16LE || lenPlane1 || Length of compressed plane 1 data (in bytes)
|-
| 16 || UINT16LE || lenPlane2 || Length of compressed plane 2 data (in bytes)
|-
| 18 || UINT16LE || width || Width of level (in tiles)
|-
| 20 || UINT16LE || height || Height of level (in tiles)
|-
| 22 || char[16] || name || Internal name for level (used only by editor, not displayed in-game. null-terminated)
|}

Note that for Wolfenstein 3D, a 4-byte signature string ("!ID!") will normally be present directly after the level name. The signature does not appear to be used anywhere, but is useful for distinguishing between v1.0 files (the signature string is missing), and files for v1.1 and later (includes the signature string).

== Carmack compression ==

[[Carmack compression]] is the method used to compress later ''id Software'' games, when file size was still a concern. It is the most efficient and complex compression method and was created specifically to work with the 16-bit word structure of the GameMaps file. The compression is detailed on its [[Carmack compression|own page.]]

Carmackized game maps files are external <tt>GAMEMAPS.xxx</tt> files and the map header is usually (but not always) stored internally in the executable. The map header must be extracted and the game maps decompressed before TED5 can access them. TED5 itself can produce carmackized files and external <tt>MAPHEAD.xxx</tt> files. Carmackization does not replace the RLEW compression used in uncompressed data, but compresses this data, that is, the data is doubly compressed.

Note that for Wolfenstein 3D v1.0, map files are not carmackized, only RLEW compression is applied.

== Huffman compression ==

[[Huffman Compression]] was probably used by earlier versions of TED5 (but possibly not TED5 at all) before carmackization was introduced. It uses the same method to compress its data as is used by ''id Software'' games to compress their graphics and sounds. Again this compression method works with RLEW compressed data and has its [[Huffman Compression|own page.]]

Huffman compression is easily detected since it works on the bit level and thus disrupts the word structure of the game data. This is easily seen in a hex editor. Compressed data will not contain the string $00 $00 or indeed even $00 very often. (In contrast, even carmackized data contains both strings hundreds of times.)

There will be two internal files for this format: the map header and the Huffman dictionary (which is always the first dictionary in the executable.) The map header format is also slightly different, being 502 bytes long, the extra 100 bytes being the length of the compressed level headers in the game maps data, which occur immediately after the normal level header offsets and before the tileinfo. Each entry is one octet indicating the decompressed header length in bytes or zero if the level does not exist. (These can be ignored when decompressing since Huffman data can be read until the decompressed level header's fixed size is reached, but if they are omitted when writing the MAPHEAD, the game may experience a buffer overflow when reading the maps.)

== Location of internal files ==

The GAMEMAPS file itself is always external, but in the case of compression, the MAPHEAD is stored internally in the main .exe file. Executables are themselves compressed with either with LZEXE or PKLite. Once the .exe has been decompressed it is a trivial task to find the MAPHEAD as it will start with the UINT16LE value $ABCD (i.e. the byte $CD followed by the byte $AB.) For level editing purposes only the first 402 (or 502) bytes of the file need to be extracted, though it is possible to read the MAPHEAD file to calculate its length.

The following table lists the offsets of the MAPHEAD file for various games, relative to the start of the decompressed game .exe file.

{{TODO|TODO: Add all known versions of all games}}

{|class="wikitable"
! Game !! Version !! Location !! Filename !! Offset !! Notes
|-
| [[Bio Menace]] || Freeware || External || <tt>MAPHEAD.BM[123]</tt> || - ||
|-
|rowspan=2| [[Blake Stone]]: Aliens of Gold || Shareware || External || <tt>MAPHEAD.BS1</tt> || - ||
|-
| Registered|| External || <tt>MAPHEAD.BS6</tt> || - ||
|-
| [[Blake Stone]] 2: Planet Strike || All || External || <tt>MAPHEAD.VSI</tt> || - ||
|-
| [[Catacomb 3-D]] (3) || 1.00 || Internal || <tt>CAT3D.EXE</tt> || $1C570 || After UNLZEXE
|-
| [[Catacomb Abyss]] (4) || 1.13 || Internal || <tt>CATABYSS.EXE</tt> || $1C510 || After UNLZEXE
|-
| [[Catacomb Armageddon]] (5) || 1.01a || Internal || <tt>CATARMA.EXE</tt> || $1D900 || After UNLZEXE
|-
| [[Catacomb Apocalypse]] (6) || 1.00b || Internal || <tt>CATAPOC.EXE</tt> || $1DD50 || After UNLZEXE
|-
|rowspan=3| [[Corridor 7 Alien Invasion]] || Demo || External || <tt>MAPHEAD.DMO</tt> || - ||
|-
|| CD || Internal || <tt>CORR7CD.EXE</tt> || $30D50 || File is not compressed
|-
| Floppy || Internal || <tt>C7.EXE</tt> || $24BF0 || File is not compressed
|-
|rowspan=2| [[Commander Keen 4-6|Keen 4]] || Special Demo || ? || ? || ? || File is PKLite compressed
|-
| 1.4 EGA || Internal || <tt>KEEN4E.EXE</tt> || $24830 || After UNLZEXE
|-
| [[Commander Keen 4-6|Keen 5]] || 1.4 EGA || Internal || <tt>KEEN5E.EXE</tt> || $25990 || After UNLZEXE
|-
| [[Commander Keen 4-6|Keen 6]] || 1.4 EGA || Internal || <tt>KEEN6.EXE</tt> || $25080 || After UNLZEXE
|-
| [[Commander Keen Dreams]] || 1.13 || Internal || ? || $1FA50 || After UNLZEXE
|-
| [[Super 3-D Noah's Ark]] || All || External || <tt>maphead.n3d</tt> || - ||
|-
| [[Operation Body Count]] || All || External || <tt>MAPHEAD.BC</tt> || - ||
|-
| [[Spear of Destiny]] || All || External || <tt>MAPHEAD.SOD</tt> || - ||
|-
|rowspan=2| [[Wolfenstein 3-D]] || Shareware || External || <tt>MAPHEAD.WL1</tt> || - ||
|-
| Registered || External || <tt>MAPHEAD.WL6</tt> || - ||
|}

== Utilities ==

* [[TED5]] can edit the <tt>GAMEMAPS</tt> format of any games that use it. It is the original editor used to create these files.

== Credits ==

This file format was reverse engineered by Andrew Durdin (adurdin). If you find this information helpful in a project you're working on, please give credit where credit is due. (A link back to this wiki would be nice too!)

GameMaps Format

2024-10-21T23:43:25Z

VKokielov: important clarifying point for Wolf3d

{{Map Infobox
| Type = 2D tile-based
| Layers = 3
| Viewport = ''Varies by game''
| Games =
{{Game|Bio Menace}}
{{Game|Blake Stone}}
{{Game|Catacomb 3-D}}
{{Game|Catacomb Abyss}}
{{Game|Commander Keen Dreams}}
{{Game|Commander Keen 4-6}}
{{Game|Corridor 7 Alien Invasion}}
{{Game|Dangerous Dave 3}}
{{Game|Dangerous Dave 4}}
{{Game|Super 3-D Noah's Ark}}
{{Game|Operation Body Count}}
{{Game|Rescue Rover 2}}
{{Game|Spear of Destiny}}
{{Game|Wolfenstein 3-D}}
}}

The '''GameMaps Format''' stores levels in a number of [[:Category:id Software|id Software]] games. The filenames and compression varies somewhat across different games but all files stored in this format were produced by the [[TED5]] level editor.

There are three main varieties of the file format. The most basic version is just [[RLEW compression|RLEW compressed]], the other two are either [[Carmack compression|carmackized]] or [[Huffman Compression|Huffman compressed]] on top of the RLEW compression. Each variation has its own file naming scheme and pattern of external/internal files.

There are two main components to the format. The game maps proper, which contain the actual level data, and the map headers, which contain both the location of each level's data within the game maps file, and the tile info for the game.

== Variants ==

{|class="wikitable"
! Game !! RLEW !! Carmackization !! Huffman !! Head || Gamemaps || Notes
|-
| Bio Menace || Yes || No || No || maphead.bm[123] || maptemp.bm[123] || gamemaps.bm[123] and mapthead.bm[123] are present but not used
|-
| Blake Stone: Aliens of Gold || Yes || No || No || maphead.bs[16] || maptemp.bs[16] ||
|-
| Blake Stone: Planet Strike || Yes || No || No || maphead.vsi || maptemp.vsi ||
|-
| Catacomb 3-D || Yes || Yes || No || Inside .exe || gamemaps.c3d ||
|-
| Catacomb Abyss || Yes || Yes || No || Inside .exe || gamemaps.abs ||
|-
| Catacomb Apocalypse || Yes || Yes || No || Inside .exe || gamemaps.apc ||
|-
| Catacomb Armageddon || Yes || Yes || No || Inside .exe || gamemaps.arm ||
|-
| Commander Keen Dreams || Yes || No || Yes || Inside .exe || gamemaps.kdr (v1.00), kdreams.map (v1.01+) ||
|-
| Commander Keen 4-6 || Yes || Yes || No || Inside .exe || gamemaps.ck[456] ||
|-
| Corridor 7 Alien Invasion || Yes || No || No || Inside .exe (cd, disk), maphead.dmo (demo) || maptemp.co7 (cd, disk), maptemp.dmo (demo) || Uses MAPTEMP.xxx (only RLEW compression)
|-
| Dangerous Dave 3 || Yes || No || Yes || Inside .exe || gamemaps.dav ||
|-
| Dangerous Dave 4 || Yes || No || Yes || Inside .exe || gamemaps.dav ||
|-
| Super 3-D Noah's Ark || Yes || Yes || No || maphead.n3d || gamemaps.n3d ||
|-
| Operation Body Count || Yes || No || No || maphead.bc (cd, disk, demo 2), maphead.co7 (demo 1) || maptemp.bc (cd, disk, demo 2), maptemp.co7 (demo 1) || Uses MAPTEMP.xxx (only RLEW compression)
|-
| Rescue Rover 2 || Yes || Yes || No || Inside .exe || gamemaps.rr2 ||
|-
| Spear of Destiny || Yes || Yes || No || maphead.sod || gamemaps.sod ||
|-
| Wolfenstein 3-D (v1.0) || Yes || No || No || maphead.wl1 || maptemp.wl1 ||
|-
| Wolfenstein 3-D (v1.1 and above)|| Yes || Yes || No || maphead.wl[16] || gamemaps.wl[16] ||
|}

The games that use Huffman compression will have a MAPDICT (embedded in the game's main executable). Those missing the map dictionary are not Huffman encoded.

To work out whether Carmackization is used, read the first UINT16LE in a map plane (the field storing the decompressed size). If the value matches the expected size of the plane (i.e. width * height * 2), then only RLEW compression is used. If it doesn't match, check the second UINT16LE in the file (which will become the first UINT16LE once Carmackization has been removed). If this matches the expected plane size then the plane must first have Carmackization removed followed by removal of RLEW. The exception to this rule are plane sizes that have either 0xA7 or 0xA8 as the high byte (i.e. any value from 0xA700 to 0xA8FF), as those values would have been encoded differently by the [[Carmack compression]] algorithm.

== Data structures==

The map data is split into two files: The map header (<tt>MAPHEAD.xxx</tt>) and the main map file (usually <tt>MAPTEMP.xxx</tt> or <tt>GAMEMAPS.xxx</tt>). The map header may be embedded in the game's main executable.

<tt>MAPTEMP.xxx</tt> is the working format saved by [[TED5]] when maps are being edited and can be directly accessed and edited by this utility, allowing changes to be made to the game. Note that if the MAPHEAD file exists as an external file, the game always reads it from a file named named <tt>MAPHEAD.xxx</tt> for both the <tt>GAMEMAPS.xxx</tt> and the <tt>MAPTEMP.xxx</tt> variation. TED5 also saves a <tt>MAPTHEAD.xx</tt> file when editing maps, but that file is only used by TED5 and usually omitted from any game release.

The maps were often compressed even further for the public release versions of the games. This more compressed version of the map file was saved as <tt>GAMEMAPS.xxx</tt> by TED5. Later releases would omit the additional compression layer and ship with the <tt>MAPTEMP.xxx</tt> file instead. One possible reason for this could be that the size of the games grew to the point where they would no longer fit onto and be playable from a single floppy disk, and therefore the additional compression was no longer worth the amount of time it took to compress the maps and re-compile the code.

=== Map headers (MAPHEAD) ===

{|class="wikitable"
! Offset !! Type !! Name !! Description
|-
| 0 || [[UINT16LE]] || magic || Magic word signalling [[RLEW compression]]
|-
| 2 || [[INT32LE]][100] || ptr || 100 pointers to start of level 0-99 data in the game maps file
|-
| 402 || {{TODO|Unknown}} || tileinfo || Optional tileinfo data
|}

The map header file (MAPHEAD) is of varying length and contains three main types of data.

* The first is the magic word or flag used for RLEW compression, which is almost always $ABCD in the original files. It could be changed to any other value if necessary.

* The second is 100 level pointers which give the location of the start of level data in the GAMEMAPS file, relative to the start of that file. A value less than 1 indicates no level (generally 0, but occasionally -1 (0xFFFFFFFF) is used). Using -1 should be preferred over 0, as the pre-Wolf3D version of the engine will treat any negative value as "a non existant map" [sic!] and quit with an appropriate error message, while 0 will cause it to try reading a level header at offset 0 (where the "TED5v1.0" string is usually stored), which will cause all kinds of errors as there is clearly no valid level header at that offset.
** For Wolf3D, take only the 16 high-order bits of the resulting 32-bit value (0x12340000 means a map at offset 0x1234)

* The third is the tileinfo data, which contains tile properties for each tile used in level creation. (These are masked and unmasked and either 8x8, 16x16 or 32x32.)

Many programs treat the tileinfo as a separate file from the MAPHEAD and it is possible to modify a game in this manner. Indeed, some games such as Wolfenstein 3-D do not have any tileinfo data at all in the map header file (giving a total file length of 402 bytes.) However TED5 works with any tileinfo data in the MAPHEAD.

=== Map data (GAMEMAPS) ===

The GAMEMAPS file consists of the string "TED5v1.0" and a number of compressed chunks of varying length. Each level in the file will have from two to four chunks (usually four) depending on the game, with all levels in a given game having the same number of chunks. These are the level header and 1-3 planes (foreground, background and sprite/info.) The chunks are in no particular order and it is possible to read through the entire file decompressing chunks as they're found.

Chunks are ordered by the MAPHEAD file, which will point to the GAMEMAPS level header chunks which in turn contain pointers to the other GAMEMAPS chunks used by that level.

All level data is in the form of [[UINT16LE]] values (or in the case of pointers, [[UINT32LE]].)

==== Level headers ====

The header for each level inside the GAMEMAPS file (which is pointed to by MAPHEAD) is 38 bytes long and ''never'' RLEW compressed. If the GAMEMAPS file is using Huffman compression, the level header itself is Huffman-compressed. In that case, the size of the compressed level header can be found in the MAPHEAD file. Since the uncompressed level header always has a size of 38 bytes, that size is not stored at the beginning of the compressed data. The header is sometimes followed by a signature "!ID!" string, which would give the header a total size of 42 bytes, but that string is not part of the actual level header.

The expanded size of each map plane is the size of a word ([[UINT16LE]]) times the width times the height. This is the final, expected size and can be precomputed even if there are two layers of compression.

Plane 0 is background using unmasked tiles, plane 1 is foreground and uses masked tiles, and plane 2 is sprite/info. Levels must contain a background plane and usually an infoplane.

For the compressed size of each level plane, a value of 0 indicates the plane does not exist. The offset value for unused planes appears to be set to a random number with the most significant byte set to 0xFF, making it either a negative number or an offset close to the 4 gigabyte range. The games only check the compressed size and ignore the offset if the size is 0.

Note that Wolf3D is hard-coded to always load the first two planes, even if the compressed size of a plane is 0. Wolf3D also ignores the width and height stored in the level header and just assumes the level is 64x64 tiles. This also applies to Blake Stone and probably any other game based on the Wolf3D code.

All versions of the "Id Software Caching Manager" ignore the expanded size value at the beginning of the RLEW data and just assume that the size is the same as the size of the plane (width * height * 2).

{|class="wikitable"
! Offset !! Type !! Name !! Description
|-
| 0 || [[INT32LE]] || offPlane0 || Offset in GAMEMAPS to beginning of compressed plane 0 data (or <= 0 if plane is not present)
|-
| 4 || INT32LE || offPlane1 || Offset in GAMEMAPS to beginning of compressed plane 1 data (or <= 0 if plane is not present)
|-
| 8 || INT32LE || offPlane2 || Offset in GAMEMAPS to beginning of compressed plane 2 data (or <= 0 if plane is not present)
|-
| 12 || UINT16LE || lenPlane0 || Length of compressed plane 0 data (in bytes)
|-
| 14 || UINT16LE || lenPlane1 || Length of compressed plane 1 data (in bytes)
|-
| 16 || UINT16LE || lenPlane2 || Length of compressed plane 2 data (in bytes)
|-
| 18 || UINT16LE || width || Width of level (in tiles)
|-
| 20 || UINT16LE || height || Height of level (in tiles)
|-
| 22 || char[16] || name || Internal name for level (used only by editor, not displayed in-game. null-terminated)
|}

Note that for Wolfenstein 3D, a 4-byte signature string ("!ID!") will normally be present directly after the level name. The signature does not appear to be used anywhere, but is useful for distinguishing between v1.0 files (the signature string is missing), and files for v1.1 and later (includes the signature string).

== Carmack compression ==

[[Carmack compression]] is the method used to compress later ''id Software'' games, when file size was still a concern. It is the most efficient and complex compression method and was created specifically to work with the 16-bit word structure of the GameMaps file. The compression is detailed on its [[Carmack compression|own page.]]

Carmackized game maps files are external <tt>GAMEMAPS.xxx</tt> files and the map header is usually (but not always) stored internally in the executable. The map header must be extracted and the game maps decompressed before TED5 can access them. TED5 itself can produce carmackized files and external <tt>MAPHEAD.xxx</tt> files. Carmackization does not replace the RLEW compression used in uncompressed data, but compresses this data, that is, the data is doubly compressed.

Note that for Wolfenstein 3D v1.0, map files are not carmackized, only RLEW compression is applied.

== Huffman compression ==

[[Huffman Compression]] was probably used by earlier versions of TED5 (but possibly not TED5 at all) before carmackization was introduced. It uses the same method to compress its data as is used by ''id Software'' games to compress their graphics and sounds. Again this compression method works with RLEW compressed data and has its [[Huffman Compression|own page.]]

Huffman compression is easily detected since it works on the bit level and thus disrupts the word structure of the game data. This is easily seen in a hex editor. Compressed data will not contain the string $00 $00 or indeed even $00 very often. (In contrast, even carmackized data contains both strings hundreds of times.)

There will be two internal files for this format: the map header and the Huffman dictionary (which is always the first dictionary in the executable.) The map header format is also slightly different, being 502 bytes long, the extra 100 bytes being the length of the compressed level headers in the game maps data, which occur immediately after the normal level header offsets and before the tileinfo. Each entry is one octet indicating the decompressed header length in bytes or zero if the level does not exist. (These can be ignored when decompressing since Huffman data can be read until the decompressed level header's fixed size is reached, but if they are omitted when writing the MAPHEAD, the game may experience a buffer overflow when reading the maps.)

== Location of internal files ==

The GAMEMAPS file itself is always external, but in the case of compression, the MAPHEAD is stored internally in the main .exe file. Executables are themselves compressed with either with LZEXE or PKLite. Once the .exe has been decompressed it is a trivial task to find the MAPHEAD as it will start with the UINT16LE value $ABCD (i.e. the byte $CD followed by the byte $AB.) For level editing purposes only the first 402 (or 502) bytes of the file need to be extracted, though it is possible to read the MAPHEAD file to calculate its length.

The following table lists the offsets of the MAPHEAD file for various games, relative to the start of the decompressed game .exe file.

{{TODO|TODO: Add all known versions of all games}}

{|class="wikitable"
! Game !! Version !! Location !! Filename !! Offset !! Notes
|-
| [[Bio Menace]] || Freeware || External || <tt>MAPHEAD.BM[123]</tt> || - ||
|-
|rowspan=2| [[Blake Stone]]: Aliens of Gold || Shareware || External || <tt>MAPHEAD.BS1</tt> || - ||
|-
| Registered|| External || <tt>MAPHEAD.BS6</tt> || - ||
|-
| [[Blake Stone]] 2: Planet Strike || All || External || <tt>MAPHEAD.VSI</tt> || - ||
|-
| [[Catacomb 3-D]] (3) || 1.00 || Internal || <tt>CAT3D.EXE</tt> || $1C570 || After UNLZEXE
|-
| [[Catacomb Abyss]] (4) || 1.13 || Internal || <tt>CATABYSS.EXE</tt> || $1C510 || After UNLZEXE
|-
| [[Catacomb Armageddon]] (5) || 1.01a || Internal || <tt>CATARMA.EXE</tt> || $1D900 || After UNLZEXE
|-
| [[Catacomb Apocalypse]] (6) || 1.00b || Internal || <tt>CATAPOC.EXE</tt> || $1DD50 || After UNLZEXE
|-
|rowspan=3| [[Corridor 7 Alien Invasion]] || Demo || External || <tt>MAPHEAD.DMO</tt> || - ||
|-
|| CD || Internal || <tt>CORR7CD.EXE</tt> || $30D50 || File is not compressed
|-
| Floppy || Internal || <tt>C7.EXE</tt> || $24BF0 || File is not compressed
|-
|rowspan=2| [[Commander Keen 4-6|Keen 4]] || Special Demo || ? || ? || ? || File is PKLite compressed
|-
| 1.4 EGA || Internal || <tt>KEEN4E.EXE</tt> || $24830 || After UNLZEXE
|-
| [[Commander Keen 4-6|Keen 5]] || 1.4 EGA || Internal || <tt>KEEN5E.EXE</tt> || $25990 || After UNLZEXE
|-
| [[Commander Keen 4-6|Keen 6]] || 1.4 EGA || Internal || <tt>KEEN6.EXE</tt> || $25080 || After UNLZEXE
|-
| [[Commander Keen Dreams]] || 1.13 || Internal || ? || $1FA50 || After UNLZEXE
|-
| [[Super 3-D Noah's Ark]] || All || External || <tt>maphead.n3d</tt> || - ||
|-
| [[Operation Body Count]] || All || External || <tt>MAPHEAD.BC</tt> || - ||
|-
| [[Spear of Destiny]] || All || External || <tt>MAPHEAD.SOD</tt> || - ||
|-
|rowspan=2| [[Wolfenstein 3-D]] || Shareware || External || <tt>MAPHEAD.WL1</tt> || - ||
|-
| Registered || External || <tt>MAPHEAD.WL6</tt> || - ||
|}

== Utilities ==

* [[TED5]] can edit the <tt>GAMEMAPS</tt> format of any games that use it. It is the original editor used to create these files.

== Credits ==

This file format was reverse engineered by Andrew Durdin (adurdin). If you find this information helpful in a project you're working on, please give credit where credit is due. (A link back to this wiki would be nice too!)

EGA Font format

2023-01-27T16:44:09Z

VKokielov: A more clear explanation -- I hope -- based on my investigations

The 'EGA Font format' is used to store a monochrome font used in many [[Softdisk]] and [[ID Software]] games. While the font is functionally monochrome is is related to [[Raw EGA data|EGA]] and used solely by EGA games. There are two versions of the font, differing slightly in format. This is because the first format was dropped due to limitations in what it could display (256 characters of one color) however after some experimentation using 8x8 unmasked tiles for font (Notable in [[Commander Keen 1-3]].), a new way to use the font for more varied purposes was discovered.

== Format ==

0 [[UINT16LE]] Line height Height of lines (And thus all characters)
2 256*[[UINT16LE]] Char offset Array of 16-bit offsets to characters from the start of the data chunk
514 256*[[UINT8]] Char width Width of the character on-screen (but see below)
770 bytes to the end of the chunk Character image data (see below)

Each file starts with a 770 byte header. This can be used to search for the font if it is stored internally. This is because characters 0-31 are used by the game to write 8x8 window tiles inside which text is written. Therefore a font file will start with a word of varying value followed by 64 nulls and the word $302, pointing to the end of the header.

The offsets in the header refer to 1-plane (one bit per pixel, monochrome) image data. The size of the stored image is line height*rounded with, where rounded width is "char width," but rounded '''up''' to the next multiple of 8.

For example, in a font with height 10, a character where "width" == 7 is stored in a 10x8 monochrome image. A character where "width" == 11 is stored in a 10x16 monochrome image.

The additional pixels to the right of the width line are not meant to be rendered and are consequently always set to 0 in the mask; the rounding is simply to prevent the rows of the planar image from having an odd (non-byte-aligned) number of bits.

=== Version 1 and Version 2 ===

There is one difference between the two versions of fonts; version 1 has twice as much character data, as each character's data is preceded by a mask. It is not known if or how the game uses this, but it may have something to do with character overlap mentioned above. The difference between versions can be detected by comparing the size of a character's data with its height\width. The 4x10 character above would have 20 bytes of data in version 1.

Version 1 is found either internally in executables or externally as a single file in earlier Softdisk\ID Software games such as [[Shadow Knights]] or [[Rescue Rover]]. Version 2 is found inside [[EGAGraph Format|EGAGraph]] files as a font chunk.

== Implementation ==

In its earliest implementation characters are treated as another plane of EGA data overlaid on the screen. The game performs a NOT check meaning in essence that the nonzero part of the character inverts the color it is displayed on. In a text window this turns the white background black, but characters can be displayed over images outside of text windows, where this effect can be seen more clearly.

Later games allow the font to be warped in various ways, as well as having custom colors instead of simple inversion. This can be seen in the [[Commander Keen 4-6]] help screens for example.

Carmack compression

2023-01-20T17:26:27Z

VKokielov: clearer

{{Compression Infobox
| Type = Stream
| UnitSize = 1-byte
| Games =
{{Game|Catacomb 3-D}}
{{Game|Commander Keen 4-6}}
{{Game|Super 3-D Noah's Ark}}
{{Game|Wolfenstein 3-D}}
}}

[[Carmack compression]] is used in the [[GameMaps Format|GAMEMAPS file]] in a number of games to further shrink the levels down beyond what [[RLEW compression]] can achieve. Its basic idea is somewhat like LZ (Lempel-Ziv) compression in that it contains pointers back to previous data.

As in RLEW compression, the first word in the Carmack compressed data is the number of bytes (not words) in the decompressed data. This is typically the number of bytes in the compressed RLEW data, as Carmack compression is performed after RLEW compression.

The format specifies some values in '''words''' - these are 16-bits in length ([[UINT16LE]]).

Carmack compression contains two types of references to previous data: near pointers and far pointers.

=== Near Pointers ===

Near pointers occupy three bytes in the compressed data. The first is the number of words in the referenced sequence, the second is the signal byte of 0xA7, and the third is the number of words to the start of the reference (counting backwards from the current location). As a concrete example, the three bytes 0x05 0xA7 0x0A mean 'repeat the 5 words starting 10 words ago'.

Notice that near pointers only let one refer to the last 255 words. To refer to sequences further back, one must use far pointers.

=== Far Pointers ===

Far pointers occupy four bytes in the compressed data:
* The first byte is the number of ''words'' in the sequence to copy from the previously generated output;
* The second byte is the tag '0xa8'
* The fourth and fifth bytes are an UINT16LE specifying '''the number of words from the beginning of output to the start of the sequence to copy'''. This is different from the near pointers, which are offsets from the "current" output position!

As a concrete example, the four bytes 0x10 0xA8 0x01 0x02 mean 'copy to the current output position the 16 words (or 32 bytes) starting 513 words (or 1026 bytes) from the start of the output'.

=== Words with a high byte of 0xA7 or 0xA8 ===

Words whose high (second) byte is 0xA7 or 0xA8 would appear to be issue, as they would be confused with near or far pointers. These are handled by representing them as the three bytes: <tt>00 Ax yy</tt>, where <tt>yy</tt> is the lower 8 bits of the word being escaped. This sequence is recognized as an exception, as repeating zero words would make no sense.

For example:

00 A7 12 EE FF 00 A8 34 CC DD

Decodes to:

12 A7 EE FF 34 A8 CC DD

=== Example code ===

* Javascript: the [https://github.com/Malvineous/gamecompjs/blob/master/formats/cmp-carmackize.js cmp-carmackize] algorithm in gamecomp.js

Carmack compression

2023-01-20T17:22:42Z

VKokielov: this is rather misleading here. I implemented the wrong algorithm. Correcting

{{Compression Infobox
| Type = Stream
| UnitSize = 1-byte
| Games =
{{Game|Catacomb 3-D}}
{{Game|Commander Keen 4-6}}
{{Game|Super 3-D Noah's Ark}}
{{Game|Wolfenstein 3-D}}
}}

[[Carmack compression]] is used in the [[GameMaps Format|GAMEMAPS file]] in a number of games to further shrink the levels down beyond what [[RLEW compression]] can achieve. Its basic idea is somewhat like LZ (Lempel-Ziv) compression in that it contains pointers back to previous data.

As in RLEW compression, the first word in the Carmack compressed data is the number of bytes (not words) in the decompressed data. This is typically the number of bytes in the compressed RLEW data, as Carmack compression is performed after RLEW compression.

The format specifies some values in '''words''' - these are 16-bits in length ([[UINT16LE]]).

Carmack compression contains two types of references to previous data: near pointers and far pointers.

=== Near Pointers ===

Near pointers occupy three bytes in the compressed data. The first is the number of words in the referenced sequence, the second is the signal byte of 0xA7, and the third is the number of words to the start of the reference (counting backwards from the current location). As a concrete example, the three bytes 0x05 0xA7 0x0A mean 'repeat the 5 words starting 10 words ago'.

Notice that near pointers only let one refer to the last 255 words. To refer to sequences further back, one must use far pointers.

=== Far Pointers ===

Far pointers occupy four bytes in the compressed data:
* The first byte is the number of bytes to repeat;
* The second byte is the tag '0xa8'
* The fourth and fifth bytes are an UINT16LE specifying '''the number of words from the beginning of output to the start of the sequence to copy'''. This is different from the near pointers, which are offsets from the "current" output position!

As a concrete example, the four bytes 0x10 0xA8 0x01 0x02 mean 'repeat the 16 words starting 513 words from the start of the output '.

=== Words with a high byte of 0xA7 or 0xA8 ===

Words whose high (second) byte is 0xA7 or 0xA8 would appear to be issue, as they would be confused with near or far pointers. These are handled by representing them as the three bytes: <tt>00 Ax yy</tt>, where <tt>yy</tt> is the lower 8 bits of the word being escaped. This sequence is recognized as an exception, as repeating zero words would make no sense.

For example:

00 A7 12 EE FF 00 A8 34 CC DD

Decodes to:

12 A7 EE FF 34 A8 CC DD

=== Example code ===

* Javascript: the [https://github.com/Malvineous/gamecompjs/blob/master/formats/cmp-carmackize.js cmp-carmackize] algorithm in gamecomp.js

GameMaps Format

2023-01-18T19:09:52Z

VKokielov: /* Level headers */

{{Map Infobox
| Type = 2D tile-based
| Layers = 3
| Viewport = ''Varies by game''
| Games =
{{Game|Bio Menace}}
{{Game|Blake Stone}}
{{Game|Catacomb 3-D}}
{{Game|Catacomb Abyss}}
{{Game|Commander Keen Dreams}}
{{Game|Commander Keen 4-6}}
{{Game|Corridor 7 Alien Invasion}}
{{Game|Dangerous Dave 3}}
{{Game|Dangerous Dave 4}}
{{Game|Super 3-D Noah's Ark}}
{{Game|Operation Body Count}}
{{Game|Rescue Rover 2}}
{{Game|Spear of Destiny}}
{{Game|Wolfenstein 3-D}}
}}

The '''GameMaps Format''' stores levels in a number of [[:Category:id Software]] games. The filenames and compression varies somewhat across different games but all files stored in this format were produced by the [[TED5]] level editor.

There are three main varieties of the file format. The most basic version is just [[RLEW compression|RLEW compressed]], the other two are either [[Carmack compression|carmackized]] or [[Huffman Compression|Huffman compressed]] on top of the RLEW compression. Each variation has its own file naming scheme and pattern of external/internal files.

There are two main components to the format. The game maps proper, which contain the actual level data, and the map headers, which contain both the location of each level's data within the game maps file, and the tile info for the game.

== Variants ==

{|class="wikitable"
! Game !! RLEW !! Carmackization !! Huffman !! Head || Gamemaps || Notes
|-
| Bio Menace || Yes || No || No || maphead.bm[123] || maptemp.bm[123] || gamemaps.bm[123] and mapthead.bm[123] are present but not used
|-
| Blake Stone: Aliens of Gold || Yes || No || No || maphead.bs[16] || maptemp.bs[16] ||
|-
| Blake Stone: Planet Strike || Yes || No || No || maphead.vsi || maptemp.vsi ||
|-
| Catacomb 3-D || Yes || Yes || No || Inside .exe || gamemaps.c3d ||
|-
| Catacomb Abyss || Yes || Yes || No || Inside .exe || gamemaps.abs ||
|-
| Catacomb Apocalypse || Yes || Yes || No || Inside .exe || gamemaps.apc ||
|-
| Catacomb Armageddon || Yes || Yes || No || Inside .exe || gamemaps.arm ||
|-
| Commander Keen Dreams || Yes || No || Yes || Inside .exe || gamemaps.kdr (v1.00), kdreams.map (v1.01+) ||
|-
| Commander Keen 4-6 || Yes || Yes || No || Inside .exe || gamemaps.ck[456] ||
|-
| Corridor 7 Alien Invasion || Yes || No || No || ? || ? || Uses MAPTEMP.xxx (only RLEW compression)
|-
| Dangerous Dave 3 || Yes || No || Yes || Inside .exe || gamemaps.dav ||
|-
| Dangerous Dave 4 || Yes || No || Yes || Inside .exe || gamemaps.dav ||
|-
| Super 3-D Noah's Ark || Yes || Yes || No || maphead.n3d || gamemaps.n3d ||
|-
| Operation Body Count || Yes || No || No || ? || ? || Uses MAPTEMP.xxx (only RLEW compression)
|-
| Rescue Rover 2 || Yes || Yes || No || Inside .exe || gamemaps.rr2 ||
|-
| Spear of Destiny || Yes || Yes || No || maphead.sod || gamemaps.sod ||
|-
| Wolfenstein 3-D (v1.0) || Yes || No || No || maphead.wl1 || maptemp.wl1 ||
|-
| Wolfenstein 3-D (v1.1 and above)|| Yes || Yes || No || maphead.wl[16] || gamemaps.wl[16] ||
|}

The games that use Huffman compression will have a MAPDICT (embedded in the game's main executable). Those missing the map dictionary are not Huffman encoded.

To work out whether Carmackization is used, read the first UINT16LE in a map plane (the field storing the decompressed size). If the value matches the expected size of the plane (i.e. width * height * 2), then only RLEW compression is used. If it doesn't match, check the second UINT16LE in the file (which will become the first UINT16LE once Carmackization has been removed). If this matches the expected plane size then the plane must first have Carmackization removed followed by removal of RLEW. The exception to this rule are plane sizes that have either 0xA7 or 0xA8 as the high byte (i.e. any value from 0xA700 to 0xA8FF), as those values would have been encoded differently by the [[Carmack compression]] algorithm.

== Data structures==

The map data is split into two files: The map header (<tt>MAPHEAD.xxx</tt>) and the main map file (usually <tt>MAPTEMP.xxx</tt> or <tt>GAMEMAPS.xxx</tt>). The map header may be embedded in the game's main executable.

<tt>MAPTEMP.xxx</tt> is the working format saved by [[TED5]] when maps are being edited and can be directly accessed and edited by this utility, allowing changes to be made to the game. Note that if the MAPHEAD file exists as an external file, the game always reads it from a file named named <tt>MAPHEAD.xxx</tt> for both the <tt>GAMEMAPS.xxx</tt> and the <tt>MAPTEMP.xxx</tt> variation. TED5 also saves a <tt>MAPTHEAD.xx</tt> file when editing maps, but that file is only used by TED5 and usually omitted from any game release.

The maps were often compressed even further for the public release versions of the games. This more compressed version of the map file was saved as <tt>GAMEMAPS.xxx</tt> by TED5. Later releases would omit the additional compression layer and ship with the <tt>MAPTEMP.xxx</tt> file instead. One possible reason for this could be that the size of the games grew to the point where they would no longer fit onto and be playable from a single floppy disk, and therefore the additional compression was no longer worth the amount of time it took to compress the maps and re-compile the code.

=== Map headers (MAPHEAD) ===

{|class="wikitable"
! Offset !! Type !! Name !! Description
|-
| 0 || [[UINT16LE]] || magic || Magic word signalling [[RLEW compression]]
|-
| 2 || [[INT32LE]][100] || ptr || 100 pointers to start of level 0-99 data in the game maps file
|-
| 402 || {{TODO|Unknown}} || tileinfo || Optional tileinfo data
|}

The map header file (MAPHEAD) is of varying length and contains three main types of data.

* The first is the magic word or flag used for RLEW compression, which is almost always $ABCD in the original files. It could be changed to any other value if necessary.

* The second is 100 level pointers which give the location of the start of level data in the GAMEMAPS file, relative to the start of that file. A value less than 1 indicates no level (generally 0, but occasionally -1 (0xFFFFFFFF) is used). Using -1 should be preferred over 0, as the pre-Wolf3D version of the engine will treat any negative value as "a non existant map" [sic!] and quit with an appropriate error message, while 0 will cause it to try reading a level header at offset 0 (where the "TED5v1.0" string is usually stored), which will cause all kinds of errors as there is clearly no valid level header at that offset.

* The third is the tileinfo data, which contains tile properties for each tile used in level creation. (These are masked and unmasked and either 8x8, 16x16 or 32x32.)

Many programs treat the tileinfo as a separate file from the MAPHEAD and it is possible to modify a game in this manner. Indeed, some games such as Wolfenstein 3-D do not have any tileinfo data at all in the map header file (giving a total file length of 402 bytes.) However TED5 works with any tileinfo data in the MAPHEAD.

=== Map data (GAMEMAPS) ===

The GAMEMAPS file consists of the string "TED5v1.0" and a number of compressed chunks of varying length. Each level in the file will have from two to four chunks (usually four) depending on the game, with all levels in a given game having the same number of chunks. These are the level header and 1-3 planes (foreground, background and sprite/info.) The chunks are in no particular order and it is possible to read through the entire file decompressing chunks as they're found.

Chunks are ordered by the MAPHEAD file, which will point to the GAMEMAPS level header chunks which in turn contain pointers to the other GAMEMAPS chunks used by that level.

All level data is in the form of [[UINT16LE]] values (or in the case of pointers, [[UINT32LE]].)

==== Level headers ====

The header for each level inside the GAMEMAPS file (which is pointed to by MAPHEAD) is 38 bytes long and ''never'' RLEW compressed. If the GAMEMAPS file is using Huffman compression, the level header itself is Huffman-compressed. In that case, the size of the compressed level header can be found in the MAPHEAD file. Since the uncompressed level header always has a size of 38 bytes, that size is not stored at the beginning of the compressed data. The header is sometimes followed by a signature "!ID!" string, which would give the header a total size of 42 bytes, but that string is not part of the actual level header.

The expanded size of each map plane is the size of a word ([[UINT16LE]]) times the width times the height. This is the final, expected size and can be precomputed even if there are two layers of compression.

Plane 0 is background using unmasked tiles, plane 1 is foreground and uses masked tiles, and plane 2 is sprite/info. Levels must contain a background plane and usually an infoplane.

For the compressed size of each level plane, a value of 0 indicates the plane does not exist. The offset value for unused planes appears to be set to a random number with the most significant byte set to 0xFF, making it either a negative number or an offset close to the 4 gigabyte range. The games only check the compressed size and ignore the offset if the size is 0.

Note that Wolf3D is hard-coded to always load the first two planes, even if the compressed size of a plane is 0. Wolf3D also ignores the width and height stored in the level header and just assumes the level is 64x64 tiles. This also applies to Blake Stone and probably any other game based on the Wolf3D code.

All versions of the "Id Software Caching Manager" ignore the expanded size value at the beginning of the RLEW data and just assume that the size is the same as the size of the plane (width * height * 2).

{|class="wikitable"
! Offset !! Type !! Name !! Description
|-
| 0 || [[INT32LE]] || offPlane0 || Offset in GAMEMAPS to beginning of compressed plane 0 data (or <= 0 if plane is not present)
|-
| 4 || INT32LE || offPlane1 || Offset in GAMEMAPS to beginning of compressed plane 1 data (or <= 0 if plane is not present)
|-
| 8 || INT32LE || offPlane2 || Offset in GAMEMAPS to beginning of compressed plane 2 data (or <= 0 if plane is not present)
|-
| 12 || UINT16LE || lenPlane0 || Length of compressed plane 0 data (in bytes)
|-
| 14 || UINT16LE || lenPlane1 || Length of compressed plane 1 data (in bytes)
|-
| 16 || UINT16LE || lenPlane2 || Length of compressed plane 2 data (in bytes)
|-
| 18 || UINT16LE || width || Width of level (in tiles)
|-
| 20 || UINT16LE || height || Height of level (in tiles)
|-
| 22 || char[16] || name || Internal name for level (used only by editor, not displayed in-game. null-terminated)
|}

Note that for Wolfenstein 3D, a 4-byte signature string ("!ID!") will normally be present directly after the level name. The signature does not appear to be used anywhere, but is useful for distinguishing between v1.0 files (the signature string is missing), and files for v1.1 and later (includes the signature string).

== Carmack compression ==

[[Carmack compression]] is the method used to compress later ''id Software'' games, when file size was still a concern. It is the most efficient and complex compression method and was created specifically to work with the 16-bit word structure of the GameMaps file. The compression is detailed on its [[Carmack compression|own page.]]

Carmackized game maps files are external <tt>GAMEMAPS.xxx</tt> files and the map header is usually (but not always) stored internally in the executable. The map header must be extracted and the game maps decompressed before TED5 can access them. TED5 itself can produce carmackized files and external <tt>MAPHEAD.xxx</tt> files. Carmackization does not replace the RLEW compression used in uncompressed data, but compresses this data, that is, the data is doubly compressed.

Note that for Wolfenstein 3D v1.0, map files are not carmackized, only RLEW compression is applied.

== Huffman compression ==

[[Huffman Compression]] was probably used by earlier versions of TED5 (but possibly not TED5 at all) before carmackization was introduced. It uses the same method to compress its data as is used by ''id Software'' games to compress their graphics and sounds. Again this compression method works with RLEW compressed data and has its [[Huffman Compression|own page.]]

Huffman compression is easily detected since it works on the bit level and thus disrupts the word structure of the game data. This is easily seen in a hex editor. Compressed data will not contain the string $00 $00 or indeed even $00 very often. (In contrast, even carmackized data contains both strings hundreds of times.)

There will be two internal files for this format: the map header and the Huffman dictionary (which is always the first dictionary in the executable.) The map header format is also slightly different, being 502 bytes long, the extra 100 bytes being the length of the compressed level headers in the game maps data, which occur immediately after the normal level header offsets and before the tileinfo. Each entry is one octet indicating the decompressed header length in bytes or zero if the level does not exist. (These can be ignored when decompressing since Huffman data can be read until the decompressed level header's fixed size is reached, but if they are omitted when writing the MAPHEAD, the game may experience a buffer overflow when reading the maps.)

== Location of internal files ==

The GAMEMAPS file itself is always external, but in the case of compression, the MAPHEAD is stored internally in the main .exe file. Executables are themselves compressed with either with LZEXE or PKLite. Once the .exe has been decompressed it is a trivial task to find the MAPHEAD as it will start with the UINT16LE value $ABCD (i.e. the byte $CD followed by the byte $AB.) For level editing purposes only the first 402 (or 502) bytes of the file need to be extracted, though it is possible to read the MAPHEAD file to calculate its length.

The following table lists the offsets of the MAPHEAD file for various games, relative to the start of the decompressed game .exe file.

{{TODO|TODO: Add all known versions of all games}}

{|class="wikitable"
! Game !! Version !! Location !! Filename !! Offset !! Notes
|-
| [[Bio Menace]] || Freeware || External || <tt>MAPHEAD.BM[123]</tt> || - ||
|-
|rowspan=2| [[Blake Stone]]: Aliens of Gold || Shareware || External || <tt>MAPHEAD.BS1</tt> || - ||
|-
| Registered|| External || <tt>MAPHEAD.BS6</tt> || - ||
|-
| [[Blake Stone]] 2: Planet Strike || All || External || <tt>MAPHEAD.VSI</tt> || - ||
|-
| [[Catacomb 3-D]] (3) || 1.00 || Internal || <tt>CAT3D.EXE</tt> || $1C570 || After UNLZEXE
|-
| [[Catacomb Abyss]] (4) || 1.13 || Internal || <tt>CATABYSS.EXE</tt> || $1C510 || After UNLZEXE
|-
| [[Catacomb Armageddon]] (5) || 1.01a || Internal || <tt>CATARMA.EXE</tt> || $1D900 || After UNLZEXE
|-
| [[Catacomb Apocalypse]] (6) || 1.00b || Internal || <tt>CATAPOC.EXE</tt> || $1DD50 || After UNLZEXE
|-
|rowspan=3| [[Corridor 7 Alien Invasion]] || Demo || External || <tt>MAPHEAD.DMO</tt> || - ||
|-
|| CD || Internal || <tt>CORR7CD.EXE</tt> || $30D50 || File is not compressed
|-
| Floppy || Internal || <tt>C7.EXE</tt> || $24BF0 || File is not compressed
|-
|rowspan=2| [[Commander Keen 4-6|Keen 4]] || Special Demo || ? || ? || ? || File is PKLite compressed
|-
| 1.4 EGA || Internal || <tt>KEEN4E.EXE</tt> || $24830 || After UNLZEXE
|-
| [[Commander Keen 4-6|Keen 5]] || 1.4 EGA || Internal || <tt>KEEN5E.EXE</tt> || $25990 || After UNLZEXE
|-
| [[Commander Keen 4-6|Keen 6]] || 1.4 EGA || Internal || <tt>KEEN6.EXE</tt> || $25080 || After UNLZEXE
|-
| [[Commander Keen Dreams]] || 1.13 || Internal || ? || $1FA50 || After UNLZEXE
|-
| [[Noah's Ark 3D]] || All || External || ? || - ||
|-
| [[Operation Body Count]] || All || External || <tt>MAPHEAD.BC</tt> || - ||
|-
| [[Spear of Destiny]] || All || External || <tt>MAPHEAD.SOD</tt> || - ||
|-
|rowspan=2| [[Wolfenstein 3-D]] || Shareware || External || <tt>MAPHEAD.WL1</tt> || - ||
|-
| Registered || External || <tt>MAPHEAD.WL6</tt> || - ||
|}

== Utilities ==

* [[TED5]] can edit the <tt>GAMEMAPS</tt> format of any games that use it. It is the original editor used to create these files.

== Credits ==

This file format was reverse engineered by Andrew Durdin (adurdin). If you find this information helpful in a project you're working on, please give credit where credit is due. (A link back to this wiki would be nice too!)

EGAGraph Format

2023-01-17T17:59:40Z

VKokielov: sprites missing from list

{{Tileset Infobox
| ImageNativeWidth = Y
| Hardware1 = VGA
| Palette = External
| Names = N
| HasTransparency = Y
| Metadata = None
| Subtilesets = N
| Compressed = Y
| Hidden = N
| Games =
{{Game|Catacomb 3-D}}
{{Game|Catacomb Abyss}}
{{Game|Commander Keen 4-6}}
{{Game|Commander Keen Dreams}}
{{Game|Dangerous Dave 3}}
}}

'''EGAGraph''', short for 'EGA graphics library' is the format used to store graphics, demos, fonts, game texts and more in many early [[:Category:Id Software|id Software]] games.

The basic format is that of a number of [[Huffman Compression]] compressed sub-files (Chunks) stored in a similar manner to the [[AudioT Format]]. Like this format it has three main files, <tt>EGAGRAPH</tt>, <tt>EGAHEAD</tt> and <tt>EGADICT</tt>.

It is notable that while the <tt>EGAHEAD</tt> and <tt>EGADICT</tt> are stored in the game executable, they need to be extracted for [[TED5]] to edit levels.

This article may contain errors as some formats have not been worked out completely.

== EGA Head (EGAHEAD.xxx) ==

There are two versions of this format. The first version, used in [[Commander Keen Dreams]], [[Dangerous Dave 3]] and [[Dangerous Dave 4]], is an array of 4-byte little-endian values. The second version, used in all later EGA games, is an array of 3-byte unsigned little-endian values.

This header file may be present as an external file (eg. [[Bio Menace]]), or it may be included in the EXE file (eg. [[Catacomb 3-D]]). The last entry in the header is always the size of the EGAGRAPH.xxx file, and the first entry in the header is always 00 00 00. To find the end, you can search for filesize(EGAGRAPH.xxx) as a 3-byte (little-endian) value in the EXE. Then to find the start, go back 3 bytes at a time until you get to 00 000 00. Or use the fact that entries always get smaller as you go back, unless the entry is $FFFFFF.

In [[Catacomb 3-D]] v1.00 <tt>EGAHEAD.C3D</tt> is at $1BFD0 from the start of the decompressed ([[unlzexe]]) EXE file, and is 1437 bytes long, or 479 3-byte entries (for 478 chunks). It is then followed by 3 zero bytes (padding to multiple of 16?) 00 00 00, then the <tt>MAPHEAD.C3D</tt>.

In [[Catacomb Abyss]] v1.13 <tt>EGAHEAD.ABS</tt> is at $1BDB0 from the start of the decompressed ([[unlzexe]]) EXE file, and 1881 bytes long and has 626 chunks.

In [[Catacomb Apocalypse]] v1.00b <tt>EGAHEAD.APC</tt> is at $1E270 from the start of the decompressed ([[unlzexe]]) EXE file, and 2049 bytes long and has 682 chunks.

This header file stores the offsets (relative to the start of the <tt>EGAGRAPH</tt> file) for each sub file. The format is trivial, in that the header file is simply an array of 3 or 4 byte variables. (Each variable is a "slot", as the game refers to files by index.) Most games use the more compact 3-byte variables, since the <tt>EGAGRAPH</tt> file is never larger than $FFFFFF. However games based on older engines, notably [[Commander Keen Dreams]], [[Dangerous Dave 3]] and [[Dangerous Dave 4]], use 4-byte vales as these are easier to deal with.

It is important to note that not every 'slot' will be in use. Tiles especially if blank (All black) will be considered 'empty' and not worth adding to the file. (A blank 16x16 tile takes up 12 bytes of space if compressed, and there can be hundreds.) There are two ways of dealing with this; by default the games set all empty slot headers to -1, but many programs compress the graphics anyway and use a normal header value for them.

The last offset in the file will be an offset to the end of the main <tt>EGAGRAPH</tt> file. (So this should be ignored when reading the file to prevent a zero-byte file appearing last.) The total size of the <tt>EGAHEAD</tt> divided by 3 (Or 4) will also give the number of 'slots' the game uses. This varies, but is usually about 10,000.

Unlike [[AudioT Format]] files, <tt>EGAGRAPH</tt> is always compressed. However the header and dictionary may be external (E.g [[Bio Menace]])

== Dictionary (EGADICT.xxx) ==

The same [[Huffman Compression]] scheme used elsewhere in the [[Commander Keen]] series is used. When reading compressed chunks out of the <tt>EGAGRAPH</tt> file, the first four bytes located at the <tt>EGAHEAD</tt> offset are a UINT32LE specifying the file's decompressed size (which is required for the decompression algorithm.) The compressed data then follows, EXCEPT for 16x16 masked and unmasked tiles. Since these all have a similar decompressed size (128 bytes for unmasked, 256 bytes for masked) it is a waste of space to include these (Since tiles make up the bulk of graphics slots.) The decompressed size is hard coded, as are the start and finish of the unmasked and masked tile slots.

Note that the <tt>EGADICT</tt> file is not often obvious, usually being embedded in the main exe file. It is possible to locate it by looking for the string <tt>$FD $01 $00 $00 $00 $00</tt>, which appears at the end of nearly all Huffman dictionaries. They are the last 6 bytes out of 1024 (256*2*2), so add 6 and subtract 1024 to get the start (pointer to the head node).

Executables usually contain two or more dictionaries, but the <tt>EGADICT</tt> is usually '''the second one''', except in the case of early games like Keen Dreams, where it is the first of THREE. (A simple check of whether it decompresses the data sensibly works.)

In [[Catacomb 3-D]] <tt>EGADICT.C3D</tt> is at offset $24464 from the start of the decompressed CAT3D.EXE, which is the second Huffman dictionary and comes immediately after the first Huffman Dictionary.

In [[Catacomb Abyss]] v1.13 <tt>EGADICT.ABS</tt> is at offset $2734C from the start of the decompressed CATABYSS.EXE, which is the second Huffman dictionary.

In [[Catacomb Apocalypse]] v1.00b <tt>EGADICT.APC</tt> is at offset $26B24 from the start of the decompressed CATAPOC.EXE, which is the second Huffman dictionary.

== Main file (EGAGRAPH.xxx) ==

This file is simply an array of data files. Each file starts at the offset specified in the <tt>EGAHEAD</tt> file, and as there are no filenames each file is referred to by its index/slot number. Slots containing dummy values in the header are treated as if they don't exist in the <tt>EGAGRAPH</tt> file. Each file within the <tt>EGAGRAPH</tt> file is individually compressed. A file can be read by opening the <tt>EGAGRAPH</tt> file, seeking to the offset specified in the <tt>EGAHEAD</tt> file, reading a UINT32LE for the decompressed file size, and then decompressing the data from that point onwards using standard Huffman decompression techniques.

Note that in early games such as Keen Dreams, the <tt>EGAGRAPH</tt> file may have another name. (Such as <tt>KDREAMS.EGA</tt> in that case.) in which case it is always the largest non-executable file.

=== Chunks ===

Each sub file or chunk is a separate graphic, ordered in the <tt>EGAGRAPH</tt> file in a specific way, much again like the [[AudioT Format]]. Chunks are labeled starting at 0. The game executable is hard coded for the start and finish of various chunk types. For example, Keen 4 has chunks 124-520 as sprites and will treat any chunk between these two numbers as a sprite. (Note that the game refers to chunk number, not sprite number.) The usual order of chunks is:

Picture table
Masked picture table
Sprite table
Fonts
Pictures (Unmasked bitmaps)
Masked pictures
Sprites
8x8 unmasked tiles (Single chunk)
8x8 masked tiles (Single chunk)
16x16 unmasked tiles
16x16 masked tiles
32x32 unmasked tiles (Optional)
32x32 masked tiles (Optional)
Misc graphics (Optional)
Game texts
Demo files (Optional)
Misc data (Optional)

== Chunk formats ==

When compressed each chunk consists of a dword giving the decompressed size followed by the compressed data.

=== Picture table ===

Always present and always the first chunk, the picture table is 4 * numpics bytes long, consisting of two words for each picture (Width\8, Height) used when displaying picture chunks.

Divide the decompressed size by 4 to get numpics.

=== Masked picture table ===

Always present and always the second chunk, the picture table is 4 * numpics bytes long, consisting of two words for each picture (Width\8, Height) used when displaying masked picture chunks. This table is often quite small.

=== Sprite table ===

Always present and always the third chunk, the sprite table is 18 * numspr bytes long, consisting of nine words for each sprite image (width\8, height, x offset, y offset, clipping rectangle left, top, right and bottom, and shifts; all in that order.) used when displaying sprite chunks. This is what Modkeen exports as its notoriously hard to use xSPRITES.txt file.

=== Fonts ===

Always present and always starting at the fourth chunk. (Chunk 3!) Each chunk is a single monochrome font, containing all the entries from 0-255 for that font. Each 'letter' is stored separately and consecutively. A game will have at least one, and usually 3 fonts. The format is version two of [[EGA Font format]]

Fonts are used in the game for game texts. They can be stretched or colored and are always transparent, meaning they look strange when not over a single-color background.

=== Pictures (Bitmaps) ===

These follow game fonts. You need to know how many fonts there are before it to know how what chunk number the first picture is (3+NumFonts).

Bitmaps are stored as standard [[Raw EGA data]], the size of each plane being the decompressed chunk size \ 4. In order to be displayed properly these need information from chunk 0, the picture table. Note that unlike fonts, data does not wrap, so a 4x4 sprite will consist of four planes of four bytes in size, the same as an 8x4 sprite.

Pictures are used for things such as title screens or pictures in game texts. Most of the main menu will consist of pictures. They are also used for the wall textures and sprites in EGA FPS games like [[Catacomb 3-D]], in which case the wall textures usually come near the end of the picture list.

The number of picture chunks is given in chunk 0, the picture table.

=== Masked pictures (Masked bitmaps) ===

These follow Pictures. You need to know how many fonts there are, to know how what chunk number the first Masked picture is (3+NumFonts+numpics).

These are identical to the picture chunks in every respect, except being masked, they consist of five EGA planes, not four. Most games have only one or two of them. They need information from chunk 1, the masked picture table, to be displayed correctly.

The number of Masked pictures is given in Chunk 1.

=== Sprites ===

The first Sprite chunk is at 3+numfonts+numpics+numMaskedPics.

Sprites are exactly identical to masked pictures in format except the game cannot stretch or warp them. Most games use these for enemy, player or item graphics during gameplay. They need information from chunk 2, the sprite table, both to display correctly and to interact correctly, something more complex than masked pictures.

There are usually several hundred sprite chunks, although that's not always the case, as [[Catacomb 3-D]] only has 3 sprite chunks (used for the PaddleWar game), and [[Catacomb Abyss]] has only one (used for the in-game radar). The number of sprite chunks is given in chunk 2.

=== 8x8 tiles ===

8x8 tiles are used by most games in status windows or foe the borders of message windows in-game. (And occasionally by TED5 to display levels.) There are thus not many of them. ALL the masked or unmasked tiles are one single chunk stored as four and five plane [[Raw EGA data]] respectively. The number of 8x8 unmasked and masked tiles is hard-coded into the executable, but can be worked out by dividing the decompressed chunk size by 32 and 40 (The size of one tile's data) respectively.

=== 16x16 and 32x32 tiles ===

32x32 tiles are optional and rarely used. 16x16 tiles are only occasionally absent and for most games make up the bulk of graphics. There are usually several thousand entries. Both come in masked and unmasked kinds, just like 8x8 tiles.

These chunks have notable differences. Each tile is an individual chunk and stored as four or five plane [[Raw EGA data]] with a plane size of 128 (16x16) or 512 (32x32). These chunks do NOT have a dword specifying their decompressed size as this is hard-coded into the executable as a space saving measure. (As is the start and finish of unmasked and masked tile chunks.) This can cause problems for editing programs.

Tiles make up the bulk of 2D game levels but are seldom seen elsewhere.

=== Misc graphics ===

Sometimes following tile graphics are miscellaneous graphics, that cannot be handled by the other chunk types. For example, Keen 4-6 has two misc graphics files used for the 'COMMANDER KEEN terminator text' intro. These graphics usually have unique formats that fit their function and few have been investigated.

==== Keen 4-6 Intro Bitmaps ====

This is the text that displays after the 'Ready, press any key' screen at Keen startup. It is composed of a monochrome bitmap that is scrolled across the screen and distorted for special effects. When displayed it is transparent, with a special palette so it is not black-and-white. It consists of a header followed by RLE compressed monochrome data.

HEADER:
0 2 Img height Height of the image in pixels
2 2 Img width Width of the image in pixels
4 2x Line point Pointers to line 1,2,3..etc of data. There will be [Img height] of
these, each 2 bytes long. The first pointer will have the value
(2 * [Img height] + 4)
+2 ? RLE data RLE-WM compressed data

DATA:
0 2 Black run Number of black pixels to write
2 2 Not-blk run Number of not-black pixels to write
4 2 Black run....
...
..
.
? 2 End $FFFF; end of row.

=== Game texts ===

Also known as ANSII chunks, these are used by the game for things like help screens, and have their own format. In the main they are simply text documents, interspersed with various commands to make things happen. Each file is divided up into a number of 'pages' which are moved between by pressing the up/down arrows. Pages can also have action sequences (Repeated each time the page is moved to, you cannot leave a page until the sequence finishes.)

^P First command in every file. Defines a page start
^E Ends the file
^Cx Change font color to $x until next page or ^C command
^Gx,y,z Display (unmasked) picture chunk z at location x,y (in pixels)
^Tx,y,z,t Display picture chunk z at x,y for z clicks of time
^Bx,y,z,t,b Fill a width-by-height-pixel rectangle at pixel location x,y (for z clicks of time?) with color $x
^Lx,y Start text alignment at pixel location x,y.

=== Demo files ===

These files, which can be recorded in several games using the 'demo cheat' consist of a series of commands that are played back when a demo is run ingame. (The game is also 'derandomized' during recording so all demo playbacks will be predictable.)

The format is quite simple; consisting of two words and a number of byte pairs. The first two bytes store the number of the level to load for the demo, the next two store the length of data to load\play (After this limit is reached the demo will end, whether or not there is any more data to read.) The remaining byte pairs each encode a time and a keypress. The following values are known:

01 Left
04 Up
05 Nothing
06 Down
09 Right
15 Ctrl
25 Alt

=== Misc files ===

The last few chunks are demo files and occasionally miscellaneous data. Demo file formats are currently unknown but can be recorded using the demo cheat. They contain the level number and difficulty followed by a series of key commands.

== Utilities ==

* [[KeenWiki:ModKeen|ModKeen]] (DOS) and [[KeenWiki:LModKeen|LModKeen]] (Linux/Windows) can be used to modify graphics and text stored in EGAGRAPH.CKx for the Commander Keen [[KeenWiki:Goodbye Galaxy|Goodbye Galaxy]] trilogy.
* WDC (Windows) can be used to view or modify the graphics in most EGAGRAPH games, including [[Catacomb 3-D]], [[Catacomb Abyss]] and [[Commander Keen 4-6]].