Warum wird diese Flut-fill-Algorithmus Ursache einem Stapelüberlauf?

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

Das ist mein Code so weit, aber wenn es das Ende der Karte erreicht es einen Stapelüberlauf verursacht, weiß jemand, wie das Problem zu lösen (wahrscheinlich eine schwierige Bedingung)?

Answer 1

Beachten Sie, dass dieser Aufruf Pfad vorhanden ist:

(x, y) -> (x+1, y) -> (x+1-1, y) -> (x+1-1+1, y) -> ...

Dies ist eine unendliche Rekursion, so dass Sie Stapelüberlauf haben. Ihre Schecks können nicht damit umgehen. Sie müssen eine zusätzliche Prüfung durchführen:

if (_mapLayers[layer, x, y] == replacement) return;

---

Auch wenn Sie die zusätzliche Überprüfung der obigen Tabelle enthalten sind, beachten Sie, dass die maximale Rekursionstiefe ist (_mapWidth * _mapHeight), die sogar für eine kleine Bitmap sehr tief sein kann (zum Beispiel 100 x 100).

Answer 2

Zunächst einmal sollten Sie sicherstellen, dass target!=replacement (kann einmal von ‚FloodFill‘ vor dem inital Anruf erfolgen). Dann Ihre algo arbeiten können, solange _mapWidth und _mapHeight ist nicht außergewöhnlich groß (es hängt stark von dem Inhalt Ihres _mapLayers Array). Wenn dies ein Problem ist, sollten Sie einen nicht-rekursive Algorithmus versuchen. Erstellen Sie ein

class Point
{ 
    public int x, y;
    public Point(int newX, int newY)
    {
         x=newX;
         y=newY;
    }
}

und

 List<Point> pointList;

Setzen Sie den Anfangspunkt in diese Liste und eine Art Schleife laufen, bis Punktliste leer ist: Nehmen Sie einen Punkt aus der Liste aus, verarbeitet es wie oben und statt den ursprünglichen rekursiven Aufruf oben setzten die vier Nachbarn wieder in die Liste.

EDIT: Hier ist das komplette Beispiel, hat es nicht testen, aber:

    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 der Tat, hier ist ein Vorschlag, die Routine zu optimieren: Vermeiden Sie in die Liste eingefügt, wenn Einfügen sinnlos wird, so:

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