Minecraft洪水填充

Question

我想計算我的世界的光照值，但我使用的算法非常緩慢。

什麼是計算照明陣列的更好方法？

的代碼看起來是這樣的：

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