编写Doom引擎克隆：读取地图信息

引言

该项目的目标是使用Ultimate DOOM（ Steam版本 ）发布的资源创建DOOM引擎的克隆。

它将以教程的形式呈现-我不想在代码中获得最大的性能，而只是创建一个工作版本，稍后我将开始对其进行改进和优化。

我没有创建游戏或游戏引擎的经验，也没有撰写文章的经验，因此您可以提出自己的修改建议，甚至完全重写代码。

这是资源和链接的列表。

图书游戏引擎黑皮书：DOOM Fabien Sanglar 。 关于DOOM内部的最佳书籍之一。

毁灭战士Wiki

DOOM源代码

源代码Chocolate Doom

要求条件

• Visual Studio：任何IDE都可以； 我将在Visual Studio 2017中工作。
• SDL2：库。
• 毁灭战士：终极毁灭战士的Steam版本的副本，我们只需要其中的WAD文件。

选配

• Slade3：一个测试我们工作的好工具。

思想

我不知道，我可以完成这个项目，但是我会尽力而为。

Windows将成为我的目标平台，但是由于我使用SDL，因此它将使引擎在任何其他平台上都能正常工作。

同时，安装Visual Studio！

该项目从Handmade DOOM重命名为SLD（DIY Doom），“ Doom Yourself Doom”，因此不会与其他称为“ Handmade”的项目混淆。 教程中有一些屏幕截图，其仍称为“手工制作DOOM”。

WAD文件

在开始编码之前，让我们设定目标并思考我们想要实现的目标。

首先，让我们检查是否可以读取DOOM资源文件。 所有DOOM资源都在WAD文件中。

什么是WAD文件？

“我的所有数据都在哪里”？ （“我的所有数据在哪里？”）它们在WAD中！ WAD是位于单个文件中的所有DOOM资源（和基于DOOM的游戏）的存档。

厄运开发者想出了这种格式来简化游戏修改的创建。

WAD文件解剖

WAD文件包含三个主要部分：标头（header），“件”（lump）和目录（目录）。

1. 标头-包含有关WAD文件和目录偏移的基本信息。
2. 一次性-此处存储的游戏资源，地图数据，精灵，音乐等。
3. 目录-在整块区域中查找数据的组织结构。

  <---- 32 bits ----> /------------------\ ---> 0x00 | ASCII WAD Type | 0X03 | |------------------| Header -| 0x04 | # of directories | 0x07 | |------------------| ---> 0x08 | directory offset | 0x0B -- ---> |------------------| <-- | | 0x0C | Lump Data | | | | |------------------| | | Lumps - | | . | | | | | . | | | | | . | | | ---> | . | | | ---> |------------------| <--|--- | | Lump offset | | | |------------------| | Directory -| | directory offset | --- List | |------------------| | | Lump Name | | |------------------| | | . | | | . | | | . | ---> \------------------/ 

标题格式

目录格式

目标

1. 创建一个项目。
2. 打开WAD文件。
3. 阅读标题。
4. 读取所有目录并显示它们。

建筑学

让我们不复杂化。 创建一个仅打开并加载WAD的类，并将其命名为WADLoader。 然后，我们编写一个负责根据其格式读取数据的类，并将其称为WADReader。 我们还需要一个简单的main函数来调用这些类。

注意：此架构可能不是最佳架构，如有必要，我们将对其进行更改。

获取代码

让我们从创建一个空的C ++项目开始。 在Visual Studio中，单击“文件”->“新建”->“项目”。 我们称之为DIYDoom。


让我们添加两个新类：WADLoader和WADReader。 让我们从WADLoader的实现开始。

 class WADLoader { public: WADLoader(std::string sWADFilePath); // We always want to make sure a WAD file is passed bool LoadWAD(); // Will call other helper functions to open and load the WAD file ~WADLoader(); // Clean up! protected: bool OpenAndLoad(); // Open the file and load it to memory bool ReadDirectories(); // A function what will iterate though the directory section std::string m_sWADFilePath; // Sore the file name passed to the constructor std::ifstream m_WADFile; // The file stream that will pint to the WAD file. uint8_t *m_WADData; // let's load the file and keep it in memory! It is just a few MBs! std::vector<Directory> m_WADDirectories; //let's store all the directories in this vector. }; 

实现构造函数将很简单：初始化数据指针并将已传输路径的副本存储到WAD文件。

 WADLoader::WADLoader(string sWADFilePath) : m_WADData(NULL), m_sWADFilePath(sWADFilePath) { } 

现在让我们开始执行加载OpenAndLoad辅助功能的OpenAndLoad ：我们只是尝试以二进制形式打开文件，并在失败的情况下显示错误。

 m_WADFile.open(m_sWADFilePath, ifstream::binary); if (!m_WADFile.is_open()) { cout << "Error: Failed to open WAD file" << m_sWADFilePath << endl; return false; } 

如果一切顺利，我们可以找到并打开文件，那么我们需要知道文件的大小才能分配用于将文件复制到其中的内存。

 m_WADFile.seekg(0, m_WADFile.end); size_t length = m_WADFile.tellg(); 

现在我们知道一个完整的WAD需要占用多少空间，并且我们将分配必要的内存量。

 m_WADData = new uint8_t[length]; 

将文件的内容复制到此存储器中。

 // remember to know the file size we had to move the file pointer all the way to the end! We need to move it back to the beginning. m_WADFile.seekg(ifstream::beg); m_WADFile.read((char *)m_WADData, length); // read the file and place it in m_WADData m_WADFile.close(); 

您可能已经注意到，我使用m_WADData类型作为m_WADData的数据类型。 这意味着我需要一个1字节（1字节*长度）的精确数组。 使用unint8_t可确保大小等于一个字节（8位，可以从类型名称中理解）。 如果要分配2个字节（16位），我们将使用unint16_t，我们将在后面讨论。 通过使用这些类型的代码，该代码将变得独立于平台。 我将解释：如果我们使用“ int”，那么内存中int的确切大小将取决于系统。 如果在32位配置中编译“ int”，则将获得4字节（32位）的内存大小，而在64位配置中编译相同的代码时，将获得8字节（64位）的内存大小！ 更糟糕的是，在16位平台（可能是DOS风扇）上编译代码将给我们2个字节（16位）！

让我们简短地检查代码，并确保一切正常。 但是首先我们需要实现LoadWAD。 而LoadWAD将调用“ OpenAndLoad”

 bool WADLoader::LoadWAD() { if (!OpenAndLoad()) { return false; } return true; } 

让我们添加到创建类实例并尝试加载WAD的主函数代码中

 int main() { WADLoader wadloader("D:\\SDKs\\Assets\\Doom\\DOOM.WAD"); wadloader.LoadWAD(); return 0; } 

您将需要输入WAD文件的正确路径。 让我们运行它！

！ 我们有一个仅会打开几秒钟的控制台窗口！ 没什么特别有用的...程序可以工作吗？ 这个主意！ 让我们看一下内存，看看其中有什么！ 也许在那里我们会发现一些特别的东西！ 首先，双击行号左侧放置一个断点。 您应该会看到以下内容：


从文件中读取所有数据后，我立即放置了一个断点，以查看内存阵列并查看加载到其中的内容。 现在再次运行代码！ 在自动窗口中，我看到前几个字节。 前4个字节说“ IWAD”！ 太好了！ 我从未想到这一天会到来！ 所以，好吧，您需要冷静下来，还有很多工作要做！

读取标题

标头的总大小为12个字节（从0x00到0x0b），这12个字节分为3组。 前4个字节是一种WAD，通常是“ IWAD”或“ PWAD”。 IWAD应该是ID软件发布的正式WAD，“ PWAD”应用于mod。 换句话说，这只是确定WAD文件是正式发行版还是由修改程序发行的一种方法。 请注意，该字符串不是以NULL结尾的，所以要小心！ 接下来的4个字节是unsigned int，它包含文件末尾的目录总数。 接下来的4个字节指示第一个目录的偏移量。

让我们添加一个存储信息的结构。 我将添加一个新的头文件并将其命名为“ DataTypes.h”。 在其中，我们将描述我们需要的所有结构。

 struct Header { char WADType[5]; // I added an extra character to add the NULL uint32_t DirectoryCount; //uint32_t is 4 bytes (32 bits) uint32_t DirectoryOffset; // The offset where the first directory is located. }; 

现在我们需要实现WADReader类，该类将从加载的WAD字节数组中读取数据。 ！ 这里有个窍门-WAD文件采用大尾数格式，也就是说，我们需要将字节移位以使其为小尾数（今天，大多数系统使用小尾数）。 为此，我们将添加两个函数，一个函数用于处理2个字节（16位），另一个函数用于处理4个字节（32位）。 如果我们只需要读取1个字节，则无需执行任何操作。

 uint16_t WADReader::bytesToShort(const uint8_t *pWADData, int offset) { return (pWADData[offset + 1] << 8) | pWADData[offset]; } uint32_t WADReader::bytesToInteger(const uint8_t *pWADData, int offset) { return (pWADData[offset + 3] << 24) | (pWADData[offset + 2] << 16) | (pWADData[offset + 1] << 8) | pWADData[offset]; } 

现在我们准备读取标头：将前四个字节计为char，然后向其添加NULL以简化工作。 对于目录数及其偏移量，您可以简单地使用辅助函数将它们转换为正确的格式。

 void WADReader::ReadHeaderData(const uint8_t *pWADData, int offset, Header &header) { //0x00 to 0x03 header.WADType[0] = pWADData[offset]; header.WADType[1] = pWADData[offset + 1]; header.WADType[2] = pWADData[offset + 2]; header.WADType[3] = pWADData[offset + 3]; header.WADType[4] = '\0'; //0x04 to 0x07 header.DirectoryCount = bytesToInteger(pWADData, offset + 4); //0x08 to 0x0b header.DirectoryOffset = bytesToInteger(pWADData, offset + 8); } 

让我们放在一起，调用这些函数并打印结果

 bool WADLoader::ReadDirectories() { WADReader reader; Header header; reader.ReadHeaderData(m_WADData, 0, header); std::cout << header.WADType << std::endl; std::cout << header.DirectoryCount << std::endl; std::cout << header.DirectoryOffset << std::endl; std::cout << std::endl << std::endl; return true; } 

运行程序，看看一切正常！


太好了！ IWAD线清晰可见，但其他两个数字正确吗？ 让我们尝试使用这些偏移量读取目录，看看它是否有效！

我们需要添加一个新的结构来处理与上述选项相对应的目录。

 struct Directory { uint32_t LumpOffset; uint32_t LumpSize; char LumpName[9]; }; 

现在让我们添加ReadDirectories函数：计算偏移量并输出！

在每次迭代中，我们将i * 16乘以转到下一个目录的偏移量增量。

 Directory directory; for (unsigned int i = 0; i < header.DirectoryCount; ++i) { reader.ReadDirectoryData(m_WADData, header.DirectoryOffset + i * 16, directory); m_WADDirectories.push_back(directory); std::cout << directory.LumpOffset << std::endl; std::cout << directory.LumpSize << std::endl; std::cout << directory.LumpName << std::endl; std::cout << std::endl; } 

运行代码，看看会发生什么。 哇！ 大量目录。


从名称块来看，我们可以假设我们设法正确读取了数据，但是也许有更好的方法来检查数据。 我们将使用Slade3来查看WAD目录条目。


块的名称和大小似乎与使用我们的代码获得的数据相对应。 今天我们做得很好！

其他注意事项

• 在某些时候，我认为使用向量存储目录会更好。 为什么不使用地图？ 这将比通过线性向量搜索获取数据更快。 这是一个坏主意。 使用map时，将不会跟踪目录条目的顺序，但是我们需要此信息来获取正确的数据。
  
  还有另一个误解：C ++中的Map被实现为具有O（log N）搜索时间的红黑树，并且map上的迭代总是给出递增的键顺序。 如果您需要一个给出平均时间O（1）和最差时间O（N）的数据结构，则必须使用无序映射。
• 将所有WAD文件加载到内存中并不是最佳的实现方法。 简单地将目录读入内存标头，然后返回到WAD文件并从磁盘加载资源，将更具逻辑性。 希望有一天我们会更多地了解缓存。
  
  DOOMReboot ： 完全不同意。 这些天15 MB的RAM简直是小菜一碟，从内存中读取将比庞大的fseek快得多，在下载完该级别所需的一切之后，您将不得不使用fseek。 这将使下载时间增加不少于一到两秒（我花所有时间不到20毫秒来下载）。 fseek使用操作系统。 哪个文件最有可能在RAM缓存中，但可能不是。 但是，即使他在那里，也浪费了大量资源，并且这些操作会使CPU缓存方面的许多WAD读数混乱。 最好的事情是，您可以创建混合启动方法并以适合现代处理器的L3缓存的级别存储WAD数据，在此节省的费用将是惊人的。

源代码

源代码

基本卡数据

了解了读取WAD文件之后，让我们尝试使用读取的数据。 学习如何读取任务数据（世界/级别）并应用它们将非常有用。 这些任务（任务集）的“块”应该是复杂而棘手的。 因此，我们将需要逐步移动和发展知识。 首先，让我们创建类似自动地图功能的东西：带有顶视图的地图的二维平面。 首先，让我们看看任务团内部的内容。

卡解剖

让我们重新开始：DOOM级别的描述与2D工程图非常相似，在该工程图的墙壁上标有线条。 但是，要获得3D坐标，每面墙都应取地板和天花板的高度（XY是我们沿水平方向移动的平面，Z是允许我们上下移动的高度，例如通过在电梯上升降或从平台上跳下这三个高度）。坐标组件用于将任务渲染为3D世界，但是，为了确保良好的性能，引擎有一定的局限性：没有一个房间在另一个水平上位于另一个之上，并且玩家无法上下看。 岩石（例如，火箭）会垂直上升，以击中较高平台上的目标。

这些奇怪的功能引起了关于DOOM是2D还是3D引擎的无休止的抱怨。 逐渐达成外交妥协，挽救了许多生命：双方商定了双方都能接受的“ 2.5D”这一称呼。

为了简化任务并返回主题，让我们尝试读取2D数据，看看是否可以以某种方式使用它。 稍后，我们将尝试以3D渲染它们，但是现在，我们需要了解引擎的各个部分如何协同工作。

经过研究，我发现每个任务都是由一组“零件”组成的。 这些“块”总是以相同的顺序显示在DOOM游戏的WAD文件中。

1. 顶点： 2D墙的端点。 两个连接的VERTEX构成一个LINEDEF。 三个相连的VERTEX形成两个墙/ LINEDEF，依此类推。 可以简单地将它们视为两个或多个墙的连接点。 （是的，大多数人都喜欢复数的“顶点”，但约翰·卡马克并不喜欢它。根据merriam-webster所说 ，这两种选择都适用。
2. LINEDEFS：在顶点和墙之间形成接缝的线。 并非所有的线（墙）的行为都相同，有一些标志指定这些线的行为。
3. SIDEDDEFS：在现实生活中，墙壁有两面-我们看一看，第二面在另一面。 两侧可以具有不同的纹理，SIDEDEFS是包含墙的纹理信息（LINEDEF）的块。
4. 部门：部门是LINEDEF联接获得的“房间”。 每个扇区都包含诸如地板和天花板高度，纹理，照明值，特殊动作（例如移动地板/平台/电梯）之类的信息。 其中一些参数也会影响渲染墙的方式，例如，照明级别和纹理贴图坐标的计算。
5. SSECTORS ：（子扇区）在扇区中形成凸面区域，这些凸面区域与BSP旁路一起用于渲染，并且还有助于确定玩家处于特定级别的位置。 它们非常有用，通常用于确定玩家的垂直位置。 每个SSECTOR都由一个扇区的连接部分组成，例如，形成一个角度的墙。 墙的这些部分或“段”存储在自己的块中，称为“块”。
6. SEGS：墙体零件/ LINEDEF； 换句话说，这些是墙/ LINEDEF的“段”。 绕过BSP树渲染世界，以确定首先绘制哪些墙（最先绘制的是最接近的墙）。 尽管系统运行良好，但它会导致linedef经常分成两个或多个SEG。 然后使用此类SEG代替LINEDEF渲染墙。 每个SSECTOR的几何形状由其中包含的段确定。
7. 节点： BSP节点是存储子扇区数据的二叉树结构的节点。 它用于快速确定播放器前面有哪个SSECTOR（和SEG）。 消除位于播放器后面的SEG（因此是不可见的），可使引擎将精力集中在可能可见的SEG上，从而大大减少了渲染时间。
8. 事物：称为事物的块是风景和任务参与者（敌人，武器等）的列表。 该块的每个元素都包含有关角色/集合的一个实例的信息，例如，对象的类型，创建的点，方向等。
9. 拒绝：该块包含有关其他扇区可见的扇区的数据。 它用于确定怪物何时得知玩家的存在。 它也可用于确定播放器创建的声音的分布范围，例如击球。 当这样的声音能够传送到怪物区时，他就可以找到玩家。 REJECT表还可以用于加快对武器弹壳碰撞的识别。
10. BLOCKMAP：玩家碰撞识别信息和THING运动。 由覆盖整个任务的几何形状的网格组成。 每个网格单元都包含一个在其内部或相交的LINEDEF列表。 它用于显着加快碰撞的识别速度：每个玩家/事物仅需几个LINEDEF即可进行碰撞检查，从而大大节省了计算能力。

生成2D地图时，我们将重点关注VERTEXES和LINEDEFS。 如果我们可以绘制顶点并将其与linedef给定的线连接，则需要生成地图的2D模型。


上面显示的演示卡具有以下特征：

• 4个山峰
  • 顶点1英寸（10.10）
  • （2,100）排名前2
  • （100，10）排名前三
  • 最高4吋（100,100）
• 4线
  • 从顶部1到2的线
  • 从顶部1到3的线
  • 从前2到4行
  • 从前三到四行

顶点格式

如您所料，顶点数据非常简单-只是某些坐标的x和y（点）。

Linedef格式

Linedef包含更多信息；它描述了连接两个顶点的线以及该线的属性（以后将成为墙）。

Linedef标志值

并非所有线（墙）都被绘制。 其中一些具有特殊行为。

目标

1. 创建一个Map类。
2. 读取顶点数据。
3. 读取linedef数据。

建筑学

首先，让我们创建一个类并将其称为map。 我们将在其中存储与卡相关的所有数据。

现在，我计划仅将顶点和linedef存储为向量，以便以后可以应用它们。

另外，让我们补充WADLoader和WADReader，以便我们可以阅读这两条新信息。

编码方式

该代码将类似于WAD读取代码，我们将只添加一些其他结构，然后使用WAD中的数据填充它们。 让我们从添加一个新类并传递地图名称开始。

 class Map { public: Map(std::string sName); ~Map(); std::string GetName(); // Incase someone need to know the map name void AddVertex(Vertex &v); // Wrapper class to append to the vertexes vector void AddLinedef(Linedef &l); // Wrapper class to append to the linedef vector protected: std::string m_sName; std::vector<Vertex> m_Vertexes; std::vector<Linedef> m_Linedef; }; 

现在添加结构以读取这些新字段。 既然我们已经做过几次了，那么就一次添加它们。

 struct Vertex { int16_t XPosition; int16_t YPosition; }; struct Linedef { uint16_t StartVertex; uint16_t EndVertex; uint16_t Flags; uint16_t LineType; uint16_t SectorTag; uint16_t FrontSidedef; uint16_t BackSidedef; }; 

WADReader, , .

 void WADReader::ReadVertexData(const uint8_t *pWADData, int offset, Vertex &vertex) { vertex.XPosition = Read2Bytes(pWADData, offset); vertex.YPosition = Read2Bytes(pWADData, offset + 2); } void WADReader::ReadLinedefData(const uint8_t *pWADData, int offset, Linedef &linedef) { linedef.StartVertex = Read2Bytes(pWADData, offset); linedef.EndVertex = Read2Bytes(pWADData, offset + 2); linedef.Flags = Read2Bytes(pWADData, offset + 4); linedef.LineType = Read2Bytes(pWADData, offset + 6); linedef.SectorTag = Read2Bytes(pWADData, offset + 8); linedef.FrontSidedef = Read2Bytes(pWADData, offset + 10); linedef.BackSidedef = Read2Bytes(pWADData, offset + 12); } 

, . WADLoader. : lumps, lump , lumps, . lumps , , .

 enum EMAPLUMPSINDEX { eTHINGS = 1, eLINEDEFS, eSIDEDDEFS, eVERTEXES, eSEAGS, eSSECTORS, eNODES, eSECTORS, eREJECT, eBLOCKMAP, eCOUNT }; 

. , , , , , , , ..

 int WADLoader::FindMapIndex(Map &map) { for (int i = 0; i < m_WADDirectories.size(); ++i) { if (m_WADDirectories[i].LumpName == map.GetName()) { return i; } } return -1; } 

, ! VERTEXES! , , .

 bool WADLoader::ReadMapVertex(Map &map) { int iMapIndex = FindMapIndex(map); if (iMapIndex == -1) { return false; } iMapIndex += EMAPLUMPSINDEX::eVERTEXES; if (strcmp(m_WADDirectories[iMapIndex].LumpName, "VERTEXES") != 0) { return false; } int iVertexSizeInBytes = sizeof(Vertex); int iVertexesCount = m_WADDirectories[iMapIndex].LumpSize / iVertexSizeInBytes; Vertex vertex; for (int i = 0; i < iVertexesCount; ++i) { m_Reader.ReadVertexData(m_WADData, m_WADDirectories[iMapIndex].LumpOffset + i * iVertexSizeInBytes, vertex); map.AddVertex(vertex); cout << vertex.XPosition << endl; cout << vertex.YPosition << endl; std::cout << std::endl; } return true; } 

, , ; , , ReadMapLinedef ( ).

— .

 bool WADLoader::LoadMapData(Map &map) { if (!ReadMapVertex(map)) { cout << "Error: Failed to load map vertex data MAP: " << map.GetName() << endl; return false; } if (!ReadMapLinedef(map)) { cout << "Error: Failed to load map linedef data MAP: " << map.GetName() << endl; return false; } return true; } 

现在，让我们更改main函数，看看一切是否正常。我想加载“ E1M1”地图，并将其转移到地图对象。

  Map map("E1M1"); wadloader.LoadMapData(map); 

现在，让我们全部运行。哇，有很多有趣的数字，但是它们是真的吗？让我们看看吧！

让我们看看斯莱德是否可以帮助我们解决这个问题。

我们可以在slade菜单中找到该图，并查看块的详细信息。让我们比较一下数字。


太好了！

那Linedef呢？


我还添加了此枚举，我们将在渲染地图时尝试使用该枚举。

 enum ELINEDEFFLAGS { eBLOCKING = 0, eBLOCKMONSTERS = 1, eTWOSIDED = 2, eDONTPEGTOP = 4, eDONTPEGBOTTOM = 8, eSECRET = 16, eSOUNDBLOCK = 32, eDONTDRAW = 64, eDRAW = 128 }; 

其他注意事项

, , . WAD , , . Visual Studio, ( ).

, Debug > Memory > Memory.


. hex- slade, lump hex.


WAD.


: , ? , , .

- . «draw points on a graph» - Plot Points — Desmos . , . "(x, y)". , .

 cout << "(" << vertex.XPosition << "," << vertex.YPosition << ")" << endl; 

! E1M1! - !


, : Plot Vertex .

: , linedefs.


: E1M1 Plot Vertex

Source code

Doom Wiki

ZDoom Wiki