多个形状的三维网格

Question

几个月前，我为一个学校项目做了一个小型的地形生成器，比如“我的世界”。我这样做的方式是使用多个块。每个块都包含一个存储这些块的三维数组。该数组中的每个位置都与它所包含的块的位置相对应。

blocks[x, y, z] = new Block();

现在我想添加不同大小的if块。然而，我不能用我现在存储块的方式做到这一点，因为更大的块必须分布在三维数组中的多个位置上。具有不同大小(和不同形状)的块的游戏的一个例子是乐高世界。像这样的游戏是如何存储所有这些小块的？

我希望有人能帮我解决这个问题。

我使用的语言是Javascript和WebGL的结合。

提前感谢！

Answer 1

根据我的经验，有几种不同的方法来解决这样的问题，但我推荐的方法取决于你必须在这个问题上工作的时间和你想要制作这个游戏的范围(有多大)。

您当前的方法

目前，我认为您使用的是大多数人认为最直接的方法，即将体素存储在3D网格中

[Source]。

但是你似乎有两个问题，那就是没有一种明显的方法来创建大于1x1的块，并且一个世界空间的3D网格在内存使用方面效率相当低(对于一个数组，你必须为每个单元分配内存，包括空白空间。JavaScript也不例外)。

另一种方法

使用3D阵列的替代方案是使用不同的数据结构，全称为稀疏体素八叉树。

简单地说，这是一个树数据结构，它的工作原理是细分一个空间区域，直到存储完所有内容。

​

其中一个正方形被分成四个较小的象限的2D形式称为四叉树，同样，3D等价物划分为八个象限，称为八叉树。这种方法通常在可能的情况下是可取的，因为它的效率要高得多，因为树只在绝对必要的时候才占用更多的内存，并且它们也可以被打包到一维阵列中(从技术上讲，三维阵列也可以)。

在一些基于块的游戏中，四叉树/八叉树使用的一种常见策略是将适合于树的一个较大象限的同类体素取一个区域，简单地在那里停止细分，因为如果所有数据都相同，则没有理由进行更深层次的划分。

他们可以进行的另一个优化被称为稀疏，其中空白区域(空气)被简单地删除，因为空白空间不会做任何特殊的事情，并且它的位置可以被推断。

[SVO Source]

[Z Order Curve Source]

推荐的方法

除非你有几个月的时间来完成你的游戏，并且你正在上大学，否则我不会推荐SVO (尽管阅读关于SVO的文章可能会给你的任何老师留下深刻的印象)。取而代之的是，我建议采用与“我的世界”相同的方法。例如，一扇门是1X2，但是积木只能是1x1，那么就把它做成两个积木。

在一个门的示例中，总共有四个唯一的块，上半部分和下半部分有两个，每个块都有两个打开或关闭的变体。

例如。

var cubeProgram; // shader program
var cubeVBO; // vertex buffer (I recommend combining vertex & UV coords)
var gl; // rendering context

// Preset list of block ID's
var BLOCK_TYPES = {
    DOOR_LOWER_OPEN: 0,
    DOOR_UPPER_OPEN: 1,
    DOOR_LOWER_CLOSED: 2,
    DOOR_UPPER_CLOSED: 3,
}

var BLOCK_MESHES = {
    GENERIC_VBO: null,
    DOOR_UPPER_VBO: null
    DOOR_LOWER_VBO: null
}

// Declare a Door class using ES6 syntax
class Door {
    // Assume X & Y are the lower half of the door
    constructor(x,y,map) {
        if (y - 1 > -1) {
            console.error("Error: Top half of the door goes outside the map");
            return;
        }

        this.x = x;
        this.y = y;

        map[x][y  ] = BLOCK_TYPES.DOOR_LOWER_OPEN;
        map[x][y-1] = BLOCK_TYPES.DOOR_UPPER_OPEN;
    }
}