Minecraft Flood fill

Question

J'essaie de calculer les valeurs de lumière de minecraft, mais l'algorithme que j'utilise est très lent. Quelle est la meilleure façon de calculer la matrice d'éclairage?

Le code ressemble à ceci:

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

Lorsque je déplace le chèque avant de remettre en récursivité, puis nombre de pile est réduite pousse. Cela réduit le temps de fonctionnement de 250ms à 23us.

Code amélioré:

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