Почему этот алгоритм заливки вызывает переполнение стека?
Вопрос
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;
}
Пока что это мой код, но когда он достигает конца карты, он вызывает переполнение стека. Кто-нибудь знает, как решить проблему (вероятно, сложное условие)?
Решение
Обратите внимание, что этот путь вызова существует:
(x, y) -> (x+1, y) -> (x+1-1, y) -> (x+1-1+1, y) -> ...
Это бесконечная рекурсия, поэтому у вас есть переполнение стека.Ваши чеки не могут справиться с этим.Вам необходимо выполнить еще одну проверку:
if (_mapLayers[layer, x, y] == replacement) return;
Даже если вы включили дополнительную проверку выше, обратите внимание, что максимальная глубина рекурсии равна (_mapWidth * _mapHeight)
, который может быть очень глубоким даже для небольшого растрового изображения (например.100 х 100).
Другие советы
Прежде всего, вы должны убедиться, что target!=replacement
(можно сделать один раз перед первым вызовом FloodFill).Тогда ваш алгоритм может работать, если _mapWidth и _mapHeight не слишком велики (это сильно зависит от содержимого вашего массива _mapLayers).Если это проблема, вам следует попробовать нерекурсивный алгоритм.Создать
class Point
{
public int x, y;
public Point(int newX, int newY)
{
x=newX;
y=newY;
}
}
и
List<Point> pointList;
Поместите начальную точку в этот список и выполните какой-нибудь цикл, пока pointList не станет пустым:возьмите одну точку из списка, обработайте ее, как указано выше, и вместо исходного рекурсивного вызова, приведенного выше, снова поместите четырех соседей в список.
РЕДАКТИРОВАТЬ:вот полный пример, правда не проверял:
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));
}
}
РЕДАКТИРОВАТЬ2:Фактически, вот предложение по оптимизации рутины:избегайте вставки в список, если вставка становится бессмысленной, поэтому:
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));