لماذا تسبب خوارزمية ملء الفيضان هذه في تدفق مكدس؟
سؤال
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"). بعد ذلك ، قد يعمل algo الخاص بك ، طالما أن _mapwidth و _mapheight ليست كبيرة غير عادية (يعتمد اعتمادًا كبيرًا على محتوى صفيف _maplayers الخاص بك). إذا كانت هذه مشكلة ، فيجب عليك تجربة خوارزمية غير متكررة. إنشاء
class Point
{
public int x, y;
public Point(int newX, int newY)
{
x=newX;
y=newY;
}
}
و
List<Point> 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));
}
}
EDIT2: في الواقع ، إليك اقتراح لتحسين الروتين: تجنب الإدراج في القائمة إذا كان الإدخال لا معنى له ، لذلك:
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));