CODEWITHSUNDEEP
c#algorithmxnaflood-fill
Jamie
Jamie

Reputation: 1657

Flood fill algorithm looping ad infinitum

I'm trying to implement a simple flood fill algorithm to my game in order to find the size of a cavern in a procedurally generated cave; however, I appear to be missing some fundamental point and as such the algorithm I'm using continuously queues even checked points. My code is as follows:

List<Point> sector = new List<Point>();
List<Point> checkd = new List<Point>();
List<Point> queue = new List<Point>();

queue.Add(new Point(startX, startY));

while (queue.Count > 0) {
    Point origin = queue[0];
    queue.RemoveAt(0);
    sector.Add(origin);
    checkd.Add(origin);

    for (int offsetX = -1; offsetX < 2; offsetX++) {
        for (int offsetY = -1; offsetY < 2; offsetY++) {
            if (offsetX == 0 && offsetY == 0 || offsetX == offsetY ||
                offsetX == -offsetY || -offsetX == offsetY)
                continue;

            Point target = new Point(offsetX, offsetY);

            if (target.X < 0 || target.Y < 0 ||
                target.X >= cells.Width || target.Y >= cells.Height ||
                !checkd.Contains (target))
                queue.Add(target);
        }
    }
}

Upvotes: 1

Views: 259

Answers (1)

helb
helb

Reputation: 7793

There are many things wrong here. I tried to preserve your original code as much as possible.

  1. Target point calculation: Point target = new Point (offsetX, offsetY); does not compute the position. You probably want to use Point target = new Point(origin.X + offsetX, origin.Y + offsetY);
  2. Checking out of bounds coordinates and if the point is already in checkd cannot be done in one if-statement as in if (target.X < 0 || target.Y < 0 || target.X >= cells.Width || target.Y >= cells.Height || !checkd.Contains (target)) since that would also add points to the queue which are outside the cells grid.
  3. Checking if the point is in the list by reference. Using List<Point>.Contains(Point p) only returns true if the reference to the point is already in the list. This is never the case since target is created as with Point target = new Point(...).
  4. Before adding the target point you may also want to check if that point is not already in the queue.

So here is my version. It travels through all points and eventually adds them to checkd.

List<Point> checkd = new List<Point>();
List<Point> queue = new List<Point>();

queue.Add(new Point(startX, startY));

while (queue.Count > 0)
{
    Point origin = queue[0];
    queue.RemoveAt(0);
    sector.Add(origin);
    checkd.Add(origin);

    for (int offsetX = -1; offsetX < 2; offsetX++)
    {
        for (int offsetY = -1; offsetY < 2; offsetY++)
        {
            // do not check origin or diagonal neighbours
            if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY) continue;

            Point target = new Point(origin.X + offsetX, origin.Y + offsetY);

            // skip out of bounds point
            if (target.X < 0 || target.Y < 0 || target.X >= cells.Width || target.Y >= cells.Height) continue;

            if (!Contains(checkd, target) && !Contains(queue, target))
            {
                queue.Add(target);
            }
        }
    }
}

To check for containment I used the method:

private bool Contains(List<Point> list, Point point)
{
    return list.Any(p => p.X == point.X && p.Y == point.Y);
}

Trying to implement a flood-fill algorithm from scratch may be a good exercise. For a serious project you should consider using a graphics library which has this functionality (and probably more you will need) already implemented.

Upvotes: 3

Related Questions