c - 将表示地图的文本文件解析为四叉树结构

Question

我必须创建一个伪 wolfenstein 3D 作为学校的作业，并且我需要一个结构来表示地图。由于所有计算都将基于二维网格，我认为四叉树将是我所需要的。

您将如何解析包含此内容的文件，例如：

1 1 1 1 1 1 1 1

1 0 0 0 0 0 0 1

1 0 0 1 0 0 0 1

1 0 0 1 0 0 0 1

1 0 0 1 0 0 0 1

1 1 1 1 1 1 1 1

其中 1 是墙块，0 是空块，形成四叉树结构？

Answer 1

您在这里有几个选择。一种方法是将整个文件读入内存到某种数组中，然后从那里自上而下构建四叉树。只要地图不是特别大，这可能是最直接的方法。

另一种选择是从底部的每个单独节点自下而上构建树，然后一旦您解析了足够的节点以根据您所阅读的内容形成父节点，就这样做。在此示例中，您将为读取的每个值形成叶节点。然后在偶数行的偶数列上，在您形成叶节点后，从那里形成您的二级节点。

你会得到这样的结构：

1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2
1 1 1 1 1 1 1 1
1 2 1 3 1 2 1 3
1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2
1 1 1 1 1 1 1 1
1 2 1 3 1 2 1 4

每个数字代表读取该位置的数字后形成的最高级别的节点。还形成每个下面的所有级别（即在级别 3 上，还形成一个级别 2 节点和一个叶（级别 1）节点）。

Answer 2

您可以以自上而下的方式构建树：假设整个数组（假设它的维度是 8x8）混合了 0 和 1，将其划分为 4x4 块。现在检查每个图块是否只包含一个或零或两者都包含。当一个 tile 包含两者时，再次对其进行分区 (2x2) 并重新检查。重复直到你处于“像素”级别（1x1）。您可以将其存储在包含指向四个相邻图块的指针的结构中。

维基百科上的这张图片显示它非常好。