如何将3D数组“压平”或“索引”为1D数组？

Question

我正在尝试将3D数组压缩为1D数组，以便在我的游戏的“区块”系统中使用。这是一个3D方块游戏，基本上我希望该区块系统几乎与Minecraft的系统相同（但无论如何都不是Minecraft的克隆）。在我之前的2D游戏中，我使用以下算法访问了已压平的数组：

Tiles[x + y * WIDTH]

然而，这显然无法在三维空间中使用，因为缺少Z轴。我不知道如何在三维空间中实现这种算法。宽度、高度和深度都是常数（而且宽度与高度相同）。

是不是只需要x + y * WIDTH + Z * DEPTH？我对数学很差，而且我刚开始学习3D编程，所以我很迷惑 :|

PS. 这是因为我经常通过索引循环和获取数组中的内容。我知道一维数组比多维数组更快（出于某些原因我记不清了 :P）。即使这可能不是必要的，我仍希望尽可能获得良好的性能 :)

- user925777

---

我说的正确吗？你想把一个3D数组放入一个1D数组中吗？ - Dominic K

为什么不使用三维数组呢？ - svick

@DMan 是的，没错。 - user925777

Answer 1

以下是一个Java解决方案，可以同时实现以下两个功能:

• 从3D转换为1D
• 从1D转换为3D

下面是我选择遍历3D矩阵的图形说明，单元格按其遍历顺序编号：

转换函数:

public int to1D( int x, int y, int z ) {
    return (z * xMax * yMax) + (y * xMax) + x;
}

public int[] to3D( int idx ) {
    final int z = idx / (xMax * yMax);
    idx -= (z * xMax * yMax);
    final int y = idx / xMax;
    final int x = idx % xMax;
    return new int[]{ x, y, z };
}

- Samuel Kerrien

---

在这个回答中不清楚 xMax 是否指 WIDTH 还是 WIDTH-1。 - hellowill89

Answer 2

算法基本相同。如果您有一个三维数组Original [HEIGHT，WIDTH，DEPTH]，则可以通过以下方式将其转换为Flat [HEIGHT * WIDTH * DEPTH]：

Flat[x + WIDTH * (y + DEPTH * z)] = Original[x, y, z]

顺便提一下，在 .NET 中，你应该更喜欢使用数组的数组而不是多维数组。性能差异是显著的。

- Gideon Engelberth

---

请问一些能够讨论性能差异的来源在哪里可以找到？另外，您不应该仅基于性能来做出决策。 - svick

请翻译以下与编程有关的内容，从英语到中文。仅返回已翻译的文本：https://dev59.com/dnRB5IYBdhLWcg3wiHll和https://dev59.com/cHRB5IYBdhLWcg3w6bYE - hatchet - done with SOverflow

@svick：一些资源可以在hatchet提供的链接中看到。我的性能注释只是旁敲侧击，而不是主要建议。锯齿数组具有几乎相同的语法（original[x][y][z]），但初始化需要更多的工作。然而，根据使用情况，性能优势可以变得非常明显（2-5倍加速）。 - Gideon Engelberth

如果 HEIGHT 对应 Y 维度，那么它应该是：Flat[x + WIDTH * (y + HEIGHT * z)] = Original[x, y, z] - Jonathan Lidbeck

Answer 3

我认为上面的内容需要稍作修正。假设您的高度是10，宽度是90，那么单维数组将会是900。按照上述逻辑，如果您在数组的最后一个元素上，9+89*89显然大于900。正确的算法应该是：

Flat[x + HEIGHT* (y + WIDTH* z)] = Original[x, y, z], assuming Original[HEIGHT,WIDTH,DEPTH] 

具有讽刺意味的是，如果您的 HEIGHT>WIDTH，则不会出现溢出，而只会得到完全荒谬的结果；）

- Martin

---

我无法为真正正确的答案点赞或评论，但马丁是正确的，当前选择的答案是错误的。本质上：data[x][y][z] = data[x + ymaxX + zmaxX*maxY]。 - jking

是的，当前的答案是错误的，应该是高度而不是深度。这让我花了太长时间才弄清楚，因为这是我第一次使用错误的SO答案来编写代码 >.< - chilleo

Answer 4

x + y*WIDTH + Z*WIDTH*DEPTH。将它想象成一个长方体：首先沿着 x 遍历，然后每个 y 是一条长度为 width 的 "线"，每个 z 是一个面积为 WIDTH*DEPTH 的 "平面"。

- Tom Zych

Answer 5

你已经接近成功了。你需要将 Z 乘以 WIDTH 和 DEPTH：

Tiles[x + y*WIDTH + Z*WIDTH*DEPTH] = elements[x][y][z]; // or elements[x,y,z]

- dlev

---

你能帮我确认一下4D或5D等的模式是什么吗？ - Jamie Nicholl-Shelley

Answer 6

TL;DR

正确答案可以用各种方式表达，但我认为最好的方式是能够以非常易于理解和形象化的方式来表述。以下是确切的答案：

(width * height * z) + (width * y) + x

TS;DR

Visualize it:

someNumberToRepresentZ + someNumberToRepresentY + someNumberToRepresentX

someNumberToRepresentZ 表示我们当前所在的矩阵 (depth)。要知道当前所在的矩阵，我们需要知道每个矩阵的大小。一个矩阵是2维的，大小为 width * height。现在的问题是：“在我所在的矩阵之前有多少个矩阵？”答案是 z：

someNumberToRepresentZ = width * height * z

someNumberToRepresentY表示我们所在的行数（即height）。要知道我们所在的行数，我们必须知道每一行有多大：每一行都是1维，大小为width。需要问的问题是“在我所在的行之前有多少行？”答案是y：

someNumberToRepresentY = width * y

someNumberToRepresentX 表示我们当前所在的列（width）。为了知道我们正在哪一列上，我们只需要使用 x：

someNumberToRepresentX = x

我们的可视化是这样的：

someNumberToRepresentZ + someNumberToRepresentY + someNumberToRepresentX

变成

(width * height * z) + (width * y) + x

- Robert Plummer

Answer 7

Samuel Kerrien的前向和反向转换几乎是正确的。下面包括了一个更加简洁的（基于R语言的）变换映射，附带一个示例（其中“a %% b”是模运算符，表示a除以b的余数）：

dx=5; dy=6; dz=7  # dimensions
x1=1; y1=2; z1=3  # 3D point example
I = dx*dy*z1+dx*y1+x1; I  # corresponding 2D index
# [1] 101
x= I %% dx; x  # inverse transform recovering the x index
# [1] 1
y = ((I - x)/dx) %% dy; y  # inverse transform recovering the y index
# [1] 2
z= (I-x -dx*y)/(dx*dy); z  # inverse transform recovering the z index
# [1] 3

请注意除法（/）和模运算符（%%）。

- Joe Doe

Answer 8

正确的算法是：

Flat[ x * height * depth + y * depth + z ] = elements[x][y][z] 
where [WIDTH][HEIGHT][DEPTH]

- Beta-Logics

---

测试了几乎所有其他答案，只有这个可以将嵌套的for循环（x < width，y < height，z < depth）转换为从0到width * height * depth（有序）的数组索引。 - Kuba Chrabański

Answer 9

为了更好地理解一维数组中的三维数组描述（我猜最佳答案中的深度指的是 Y 轴大小）。

IndexArray = x + y * InSizeX + z * InSizeX * InSizeY;

IndexArray = x + InSizeX * (y + z * InSizeY);

- Evalds Urtans

Answer 10

一个Python版本：

from operator import mul
from functools import reduce

def idx_1D(target, shape):
        idx = 0
        for i, digit in enumerate(target):
            coeff = reduce(mul, shape[i + 1 :]) if i < len(shape) - 1 else 1
            idx += digit * coeff
        return idx

- byp_bypa