c# - 使用位掩码在平面 '3D' 数组上进行索引环绕

Question

我的 3D 游戏世界存储在平面字节数组中。世界的宽度/长度为 1024 x 1024，高度为 256。所以数组的长度是 268435456 字节。为了访问数组，我使用了一个像这样计算的索引指针:

WORLD_WIDTH_SHIFT = 10;
WORLD_HEIGHT_SHIFT = 8;

indexPointer = (((Px << WORLD_WIDTH_SHIFT) + Pz) << WORLD_HEIGHT_SHIFT) + Py;

出于性能原因，我在处理过程中通过向索引值添加预定义常量来导航数组。向西移动(正 x 轴)是这样实现的:

WEST = WORLD_WIDTH * WORLD_HEIGHT;
NORTH = WORLD_HEIGHT;
SOUTH = -WORLD_HEIGHT;
WEST = WORLD_WIDTH * WORLD_HEIGHT;
EAST = -WORLD_WIDTH * WORLD_HEIGHT;
UP = 1;
DOWN = -1;

indexPointer += WEST;

为了防止索引超出范围以及我愚蠢地认为可以实现环绕，我在结果中添加了一个位掩码:

WORLD_ARRAY_SIZE = WORLD_WIDTH * WORLD_WIDTH * WORLD_HEIGHT;
WORLD_ARRAY_SIZE_MASK = WORLD_ARRAY_SIZE - 1;
WEST = WORLD_WIDTH * WORLD_HEIGHT;

indexPointer = (indexPointer + WEST) & WORLD_ARRAY_SIZE_MASK;

这在上面的 x 轴上工作正常，但在 z 轴(南北)上，我在仔细考虑后发现的环绕显然行不通。如果我错了请纠正我，但我需要一种方法来对表示 indexPointer 中 z 坐标的位执​​行位掩码。前 8 位是高度，接下来的 10 位是 z 坐标，最后 10 位是 x 坐标。有没有一种方法可以执行此操作，而无需将 10 位提取到单独的字段中，然后执行加法和掩码，然后必须重建最终指针？

Answer 1

给定常量:

HIGH = 1;
NORTH = WORLD_WIDTH;
WEST = NORTH*WORLD_HEIGHT;

您可以修改您的“增量”函数:

public static void UpdatePointer (int indexPointer, int dir) {
    int mask0 = 0xffc0000;
    int mask1 = 0x003ff00;
    int mask2 = 0x00000ff;
    res = (indexPointer&mask0+dir)&mask0;
    res |= (indexPointer&mask1+dir)&mask1;
    res |= (indexPointer&mask2+dir)&mask2;
    return res;
}

因此，这或多或少是您需要的，而不是 indexPointer += update。

---

解释:

问题是当你添加一个常量时，添加一个值会导致进位。您基本上想将三个“整数”表示为一个整数。现在给定整数有值:

#bits 10   10    8
value 12 1023   15

然后你加上第二个整数，那个整数会溢出导致:

#bits 10   10    8
value 13    0   15

尽管第二个“整数”具有正确的值，但第一个已递增。

你可以通过屏蔽来解决这个问题。我们来看看第二条掩码指令:

(indexPointer&mask1+dir)&mask1;

(其他都是等价的)

这里我们首先对 indexPointer 应用掩码。这确保我们“提取”了正确的整数。所以:

#bits 10   10    8
value 12 1023   15

现在变成:

#bits 10   10    8
value 0  1023    0

这对于防止 dir 溢出第三个整数并因此导致第二个整数递增很有用。

现在我们将 dir“添加”到值中，结果是:

#bits 10   10    8
value  1    0    0

但现在我们再次屏蔽导致:

#bits 10   10    8
value  0    0    0

所以第二条标记指令已经确定第二个“整数”的值为零，并且对其他整数没有任何影响。

第一个mask也是一样的，这里carry provention比较突出:

#bits 10   10    8 //initial state
value 12 1023   15

#bits 10   10    8 //masking with mask0
value 12    0    0

#bits 10   10    8 //adding dir
value 12    1    0

#bits 10   10    8 //masking again
value 12    0    0

如果您稍后对这三个操作执行或操作，最终状态将是:

#bits 10   10    8 //final result
value 12    0   15

---

替代方案:

另一种方法是使用“溢出”位。在这种情况下，indexPointer 使用 8+1+10+1+10 = 30 位，其中一位用于溢出。在这种情况下，更新是:

indexPointer += dir;
indexPointer &= 0x3ff7feff;

其中 0x3ff7feff 是再次清除溢出位的掩码:

0x3ff7feff = 11 1111 1111   0   11 1111 1111   0   1111 1111

为了“使用”指针，您需要一个紧凑的操作:

int realPointer = ((indexPointer&0x3ff00000)>>0x02)|((indexPointer&0x7fe00)>>0x01)|(indexPointer&0xff);

或者更新函数如下:

public static void UpdatePointer (int indexPointer, int dir) {
    int temp = ((indexPointer&0xffc0000)<<0x02)|((indexPointer&0x3ff00)<<0x01)|(indexPointer&0xff);
    temp += dir;
    return ((temp&0x3ff00000)>>0x02)|((temp&0x7fe00)>>0x01)|(temp&0xff);
}

显然你需要在某个地方付出代价。