Запуск в исключение переполнения стека при многократном запуске алгоритма заполнения

Question

У меня есть список объектов, расположенных на сетке. Я хочу удалить все, которые не имеют пути к вершине сетки, ни напрямую, ни через своих соседей.

Я подумал, что хороший способ сделать это - сначала сделать все в сетке удаляемым, а затем сделать что-либо в верхней строке не удаляемым. Затем я хотел сделать заливку из любых объектов в верхнем ряду, чтобы сделать объекты, связанные с ними, не удаляемыми.

Я не могу придумать способ (который работает) оптимизировать его. Есть ли более простой способ понять, что я пытаюсь сделать?

Возможно, я выстрелил себе в ногу, используя список, а не двумерный массив. Это вводит много дополнительных циклов foreach.

    internal void DetectHangingObjects(int X)
    {
        //Set all objects to deletable
        for (int i = 0; i < planets.Count; i++)
            planets[i].deletable = true;

        //Set first row to not deletable
        for (int i = 0; i < planets.Count; i++)
        {
            Debug.WriteLine(planets[i].X + " " + X);

            if (planets[i].X == X) //X=0
            {
                planets[i].deletable = false;
                try
                {
                    DetectHangingNeighbours(planets[i]);
                }

                catch (Exception ee)
                { Debug.WriteLine(ee.Message); }
            }
        }          
    }

    internal void DetectHangingNeighbours(Planet planet)
    {
        if (planet == null || planet.deletable==true)
            return;

        planet.deletable = false;

        DetectHangingNeighbours(GetTopLeftNode2(planet));
        DetectHangingNeighbours(GetTopRightNode2(planet));
        DetectHangingNeighbours(GetLeftNode2(planet));
        DetectHangingNeighbours(GetRightNode2(planet));
        DetectHangingNeighbours(GetBottomLeftNode2(planet));
        DetectHangingNeighbours(GetBottomRightNode2(planet));
    }

    //The following methods check the six adjacent objects and returns them to the caller if they match
    internal Planet GetTopLeftNode2(Planet planet)
    {
        foreach (Planet gridPlanet in planets)
            if (gridPlanet.X == planet.X - planetSize && gridPlanet.Y == planet.Y - yOffset)
                return gridPlanet;

        return null;
    }

    internal Planet GetTopRightNode2(Planet planet)
    {
        foreach (Planet gridPlanet in planets)
            if (gridPlanet.X == planet.X - planetSize && gridPlanet.Y == planet.Y + yOffset)
                return gridPlanet;

        return null;
    }

    internal Planet GetLeftNode2(Planet planet)
    {
        foreach (Planet gridPlanet in planets)
            if (gridPlanet.X == planet.X && gridPlanet.Y == planet.Y - planetSize)
                return gridPlanet;

        return null;
    }

    internal Planet GetRightNode2(Planet planet)
    {
        foreach (Planet gridPlanet in planets)
            if (gridPlanet.X == planet.X && gridPlanet.Y == planet.Y + planetSize)
                return gridPlanet;

        return null;
    }

    internal Planet GetBottomLeftNode2(Planet planet)
    {
        foreach (Planet gridPlanet in planets)
            if (gridPlanet.X == planet.X + planetSize && gridPlanet.Y == planet.Y - yOffset)
                return gridPlanet;

        return null;
    }

    internal Planet GetBottomRightNode2(Planet planet)
    {
        foreach (Planet gridPlanet in planets)
            if (gridPlanet.X == planet.X + planetSize && gridPlanet.Y == planet.Y + yOffset)
                return gridPlanet;

        return null;
    }

Answer 1

Распутать рекурсию

Один из ответов - разгадать вашу рекурсию. Вы получаете переполнение стека, потому что существует слишком много уровней рекурсии, которые требуют выделения памяти, прежде чем она сможет завершиться и вернуться, таким образом, «переполнение стека».

Предел рекурсии

В прошлом я создавал редактор для игры XNA, где мне требовался алгоритм заполнения флудом, и я установил верхний предел числа повторений, которые он будет выполнять перед выходом. Фактически это означает, что мне, возможно, придется повторно применить большую заливку к оставшимся частям, которые не были заполнены, однако это не приведет к переполнению стека.

Алгоритмы заполнения потока

• http://www.codeproject.com/KB/GDI-plus/floodfillincsharp.aspx
• http://www.codeproject.com/KB/GDI-plus/queuelinearfloodfill.aspx

Используется регулярный цикл, чтобы избежать ошибок переполнения стека.

Answer 2

Избегайте рекурсии (DetectHangingNeighbours вызывает себя) Вместо этого используйте подход стека:

push your starting node into the stack

while there are elements in stack...
  pop element from stack

  if the element is not visited
    visit the element
    push its neighbours into the stack
  end if
end while

Удачи.