javascript - 多种形状的 3D 网格

Question

几个月前，我为一个学校项目制作了一个小型地形生成器，例如 Minecraft。我这样做的方法是使用多个 block 。每个 block 都包含一个存储 block 的 3 维数组。该数组中的每个位置都与其包含的 block 的位置相对应。

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

现在我想添加不同大小的 if block 。但是，我不能用我现在存储 block 的方式来做到这一点，因为更大的 block 必须分布在 3 维数组中的多个位置。具有不同大小块(和不同形状)的游戏示例是 LEGO Worlds。像这样的游戏如何存储所有这些小块？

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

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

提前致谢!

Answer 1

根据我的经验，有几种不同的方法可以解决此类问题，但我推荐的方法取决于您处理此问题所需的时间以及您想要处理的范围(多大)这个游戏。

您当前的方法

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

[Source] .

但是您似乎遇到了两个问题，即没有明显的方法来创建大于 1x1 的 block ，并且世界空间的 3D 网格在内存使用方面效率相当低(至于数组你必须为每个单元格分配内存，包括空白空间。JavaScript 也不异常(exception))。

另一种方法

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

简单来说，这是一个树形数据结构，通过分割空间区域直到存储所有内容。

其中一个正方形子划分为四个较小的象限的 2D 形式称为四叉树，同样的 3D 等效划分为八个象限，称为八叉树。这种方法通常在可能的情况下更可取，因为它更有效，因为树仅在绝对必要时占用更多内存，并且它们也可以打包到一维数组中(从技术上讲，3 维数组也可以)。

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

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

[SVO Source]

[Z Order Curve Source]

推荐方法

除非您有几个月的时间来完成您的游戏并且您正在上大学，否则我真的不会推荐 SVO(尽管阅读相关内容可能会给您的任何老师留下深刻印象)。相反，我建议采用与 Minecraft 明显相同的方法。例如。门是 1X2，但 block 只能是 1x1，那么就把它变成两个 block 。

在一扇门的示例中，您总共有四个独特的 block ，上半部分和下半部分各两个，每个打开或关闭的两种变化。

例如

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;
    }
}