Pourquoi cet algorithme de remplissage d'inondation provoque un débordement de pile?
Question
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;
}
Ceci est mon code jusqu'à présent, mais quand il arrive à la fin de la carte, il provoque un débordement de pile, quelqu'un sait comment résoudre le problème (probablement une condition délicate)?
La solution
Notez que cette voie d'appel existe:
(x, y) -> (x+1, y) -> (x+1-1, y) -> (x+1-1+1, y) -> ...
Ceci est une récursion infinie, de sorte que vous avez débordement de pile. Vos chèques ne peuvent pas faire face. Vous devez effectuer une vérification supplémentaire:
if (_mapLayers[layer, x, y] == replacement) return;
Même si vous avez inclus le chèque supplémentaire ci-dessus, notez que la profondeur de récursivité maximale est (_mapWidth * _mapHeight)
, qui peut être très profonde, même pour une petite image (par exemple 100 x 100).
Autres conseils
Tout d'abord, vous devez vous assurer que target!=replacement
(peut être fait une fois avant l'appel inital de « FloodFill »). Ensuite, votre algo peut travailler, aussi longtemps que _mapWidth et _mapHeight ne sont pas extraordinaires grand (cela dépend en grande partie sur le contenu de votre tableau _mapLayers). Si cela est un problème, vous devriez essayer un algorithme non récurrent. Créer un
class Point
{
public int x, y;
public Point(int newX, int newY)
{
x=newX;
y=newY;
}
}
et
List<Point> pointList;
Mettre le point initial dans cette liste et exécuter une sorte de boucle jusqu'à ce que PointList est vide: prendre un point sur la liste, le processus comme ci-dessus et au lieu de l'appel récursif d'origine mis au-dessus de nouveau les quatre voisins dans la liste.
EDIT: voici l'exemple complet, ne pas le tester, si:
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: En fait, voici une suggestion d'optimiser la routine: éviter d'insérer à la liste si l'insertion devient inutile, donc:
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));