c - 我的世界洪水填充

Question

我正在尝试计算 minecraft 的光照值，但我使用的算法非常慢。

计算照明阵列的更好方法是什么？

代码如下所示：

struct chunk_data {
    char light[16*16*256];
};

int j;

void fill(chunk_data* c, int i, int l) {
        ++j;
        if(c->light[i] > l)
                return;
        c->light[i] = l;
        if(!--l)
                return;
        if((i&0x0F) != 0x0F)
                fill(c, i + 0x01, l);
        if((i&0x0F) != 0x00)
                fill(c, i - 0x01, l);
        if((i&0xF0) != 0xF0)
                fill(c, i + 0x10, l);
        if((i&0xF0) != 0x00)
                fill(c, i - 0x10, l);
        if((i&0xFF00) != 0x0000)
                fill(c, i - 0x0100, l);
        if((i&0xFF00) != 0xFF00)
                fill(c, i + 0x0100, l);
}

Answer 1

当我在调用递归之前移动检查时，堆栈推送的数量会减少。这将运行时间从 250ms 减少到 23us。

改进的代码：

void fill(chunk_data* c, int i, int l) {
        c->light[i] = l;
        if(!--l)
                return;
        if((i&0x0F) != 0x0F && c->light[i + 0x01] < l)
                fill(c, i + 0x01, l);
        if((i&0x0F) != 0x00 && c->light[i - 0x01] < l)
                fill(c, i - 0x01, l);
        if((i&0xF0) != 0xF0 && c->light[i + 0x10] < l)
                fill(c, i + 0x10, l);
        if((i&0xF0) != 0x00 && c->light[i - 0x10] < l)
                fill(c, i - 0x10, l);
        if((i&0xFF00) != 0x0000 && c->light[i - 0x0100] < l)
                fill(c, i - 0x0100, l);
        if((i&0xFF00) != 0xFF00 && c->light[i + 0x0100] < l)
                fill(c, i + 0x0100, l);
}