Perché questo algoritmo flood-fill causare un overflow dello stack?
Domanda
void FloodFill(int layer, int x, int y, int target, int replacement)
{
if (x < 0) return;
if (y < 0) return;
if (x >= _mapWidth) return;
if (y >= _mapHeight) return;
if (_mapLayers[layer, x, y] != target) return;
_mapLayers[layer, x, y] = replacement;
FloodFill(layer, x - 1, y, target, replacement);
FloodFill(layer, x + 1, y, target, replacement);
FloodFill(layer, x, y - 1, target, replacement);
FloodFill(layer, x, y + 1, target, replacement);
return;
}
Questo è il mio codice finora, ma quando raggiunge la fine della mappa che provoca un overflow dello stack, qualcuno sa come risolvere il problema (probabilmente una condizione difficile)?
Soluzione
Si noti che esiste questo percorso chiamata:
(x, y) -> (x+1, y) -> (x+1-1, y) -> (x+1-1+1, y) -> ...
Questa è una ricorsione infinita, in modo da avere impilare troppo pieno. I vostri assegni non possono affrontare questo. È necessario eseguire un controllo supplementare:
if (_mapLayers[layer, x, y] == replacement) return;
Anche se avete inserito il controllo in più sopra, si noti che la profondità massima di ricorsione è (_mapWidth * _mapHeight)
, che può essere molto profonda anche per una piccola bitmap (ad esempio 100 x 100).
Altri suggerimenti
Prima di tutto, è necessario assicurarsi che target!=replacement
(può essere fatto una volta prima della chiamata di inital 'FloodFill'). Poi, l'algo può funzionare, a patto che _mapWidth e _mapHeight non sono straordinari di grandi dimensioni (dipende pesantemente sul contenuto del vostro array _mapLayers). Se questo è un problema, si dovrebbe cercare un algoritmo non ricorsivo. Creare un
class Point
{
public int x, y;
public Point(int newX, int newY)
{
x=newX;
y=newY;
}
}
e
List<Point> pointList;
Inserire il punto iniziale in questa lista ed eseguire una sorta di ciclo fino a quando pointList è vuoto: prendere un punto fuori dalla lista, elaborarla come sopra e al posto della chiamata ricorsiva originale sopra messo di nuovo i quattro vicini nella lista.
EDIT: qui è l'esempio completo, non prova, però:
void FloodFill2(int layer, int xStart, int yStart, int target, int replacement)
{
if(target==replacement)
return;
List<Point> pointList = new List<Point>();
pointList.Add(new Point(xStart,yStart));
while(pointList.Count>0)
{
Point p = pointList[pointList.Count-1];
pointList.RemoveAt(pointList.Count-1);
if (p.x < 0) continue;
if (p.y < 0) continue;
if (p.x >= _mapWidth) continue;
if (p.y >= _mapHeight) continue;
if (_mapLayers[layer, p.x, p.y] != target) continue;
_mapLayers[layer, p.x, p.y] = replacement;
pointList.Add(new Point(p.x - 1, p.y));
pointList.Add(new Point(p.x + 1, p.y));
pointList.Add(new Point(p.x, p.y - 1));
pointList.Add(new Point(p.x, p.y + 1));
}
}
EDIT2: In realtà, ecco un suggerimento per ottimizzare la routine: evitare di inserire nella lista se inserimento diventa inutile, così:
if(p.x>=0)
pointList.Add(new Point(p.x - 1, p.y));
if(p.x<_mapWidth-1)
pointList.Add(new Point(p.x + 1, p.y));
if(p.y>=0)
pointList.Add(new Point(p.x, p.y - 1));
if(p.y<_mapHeight-1)
pointList.Add(new Point(p.x, p.y + 1));