Iterative flood fill

Newbie & Debugging Questions
#1

Hi,

I’ve got a recursive flood fill to create caves, but if cave large, stack overflow. So, I’ve been looking at iterative using a queue:


public class IterativeFloodFill {

	static char[][] m = { 
			{'x','x','x','c','x' },
			{'x','x','x','c','x' },
			{'x','x','x','c','x' },
			{'x','x','x','c','x' },
			{'x','x','x','c','x'},		
	};
	
	
	private static void fill(int x, int y, char target, char replace)
	{
		if(m[x][y] == replace) return;

		Queue<Character> q = new LinkedList(); 			
		q.add(m[x][y]);  
		while(!q.isEmpty()) {  
			q.remove(); 
			if( m[x][y]!= replace && m[x][y]==target) 
			{
				m[x][y] = replace;  
				q.add(m[x][y+1]);
				q.add(m[x][y-1]);
				q.add(m[x+1][y]);				
				q.add(m[x-1][y]);
			}
		}
	}
		
public static void main(String[] args) {
		// TODO Auto-generated method stub
		for(int x=1; x<4;x++)
			for(int y=1;y<4;y++)
				fill(x,y,'c','w');

	
		for(int x=1; x<=4;x++,System.out.println())
			for(int y=1;y<=4;y++)
				System.out.print(m[x][y]);

	}

Now the obvious problem above would give arrayIndexOutOfBounds exception as y would become -1, and so would x as I start x,y off as 0.

I’m taking it you need to start off someplace else and call the above in a forloop?

Thanks

#2

Instead of always adding four neighbours, check whether each neighbour exists before adding it to the queue…

#3

Hi Riven,

Modified it, this look ok (see previous post)? But as stated, cannnot start from 0 and cannot go to max width, height of array, has to be minus 1…

#4

Now works, see modifications below :slight_smile:


package com.mygdx.game;

import java.util.LinkedList;
import java.util.Queue;

public class IterativeFloodFill {

	static char[][] m = { 
			{'c','x','x','c','c' },
			{'c','x','x','c','x' },
			{'x','c','x','c','x' },
			{'x','c','x','c','c' },
			{'x','c','c','c','c'},		
	};
	
	
	private static void fill(int x, int y, char target, char replace)
	{
		if(m[x][y] == replace) return;  // current is same as node - 1
		
		Queue<Character> q = new LinkedList(); 
			
		q.add(m[x][y]);  
	
		while(!q.isEmpty()) {  
			
			q.remove(); 
			
			if( m[x][y]!= replace && m[x][y]==target) // 7
			{
				m[x][y] = replace;  // 
				if(y<m[x].length-1)
				q.add(m[x][y+1]);
				if(y>0)
					q.add(m[x][y-1]);
				if(x<m.length-1)
					q.add(m[x+1][y]);				
				if(x>0)
					q.add(m[x-1][y]);
			}
		}
		
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for(int x=0; x<m.length;x++)
			for(int y=0;y<m[x].length;y++)
				fill(x,y,'c','w');

	
		for(int x=0; x<m.length;x++,System.out.println())
			for(int y=0;y<m[x].length;y++)
				System.out.print(m[x][y]);

	}

}
#5

Hi,

I thought my iterative flood fill was working ok - obviously just a red herrin!


private void fill(int x, int y, char target, char replace) {
		if (m[x][y] == replace)
			return; // current is same as node - 1

		Queue<Character> q = new LinkedList();

		q.add(m[x][y]);

		while (!q.isEmpty()) {

			q.remove();

			if (m[x][y] != replace && m[x][y] == target) 
			{
				m[x][y] = replace; //

				if (x < m.length - 1)
					if (m[x + 1][y] != replace)   // east
						q.add(m[x + 1][y]);
				if (x > 0)
					if (m[x - 1][y] != replace)   // west
						q.add(m[x - 1][y]);

				if (y < m[x].length - 1)
					if (m[x][y + 1] != replace)   // north
						q.add(m[x][y + 1]);
				if (y > 0)
					if (m[x][y - 1] != replace)   // south
						q.add(m[x][y - 1]);
			}
		}
	}

The above code can just be:


private void fill(int x, int y, char target, char replace) {
		if (m[x][y] == replace)
			return; // current is same as node - 1

		Queue<Character> q = new LinkedList();

		q.add(m[x][y]);

		while (!q.isEmpty()) {

			q.remove();

			if (m[x][y] != replace && m[x][y] == target) 
				m[x][y] = replace; 
      }
}



	public static void main(String[] args) {
		FloodFill f = new FloodFill();
		for (int x = 0; x < m.length; x++) 
			for (int y = 0; y < m[x].length; y++) 
				f.fill(x, y, 'c', 'w');

Where m is a 2d array of chars:


	static char[][] m = { 
		    { 'c', 'x', 'x', 'c', 'c' },
			{ 'c', 'x', 'x', 'c', 'x' }, 
			{ 'x', 'c', 'c', 'c', 'x' },
			{ 'x', 'c', 'x', 'x', 'c' }, 
			{ 'x', 'c', 'c', 'c', 'c' }, 
	};

The queue is doing nothing…anything obvious wrong? All the code I’ve written is just replacing the character c with W.

Thanks.

#6

This kind of stuff can be a little hard to debug just by looking at it (for me at least), but it looks like you’re just pushing the contents of the cell (i.e. the character that’s stored there) onto the stack, and not the cell itself. This means, among other things, that the values of x and y never change in your fill function, so the fill is never ‘getting anywhere’, so to speak.

If you haven’t already, I’d recommend adding some printed debug output (e.g. the cell contents and coordinates at each step) and/or stepping through the code in the debugger. I think that will likely illuminate the problem, or at least point you in the right direction.

#7

Hey Jesse,

Yes you are correct, the x & y don’t change. I’m taking it you would call this method once and it would do the whole array?

Thus fill(0,0,‘c’,‘w’);

is all that would be needed?

Thanks

#8

Did try something like this using Point object:


public void BoundaryFill(int initialX, int initialY, char target, char replacement){
	    Stack<Point> points = new Stack<Point>();
	    points.add(new Point(initialX, initialY));

	    while(!points.isEmpty()) {
	        Point currentPoint = points.pop();
	        int x = currentPoint.x;
	        int y = currentPoint.y;

	        char current = m[x][y];
	        if((current == target)){
	            m[x][y] = replacement;
	        
	            points.push(new Point(x+1, y));
	            if(x>0)
	            	points.push(new Point(x-1, y));
	            points.push(new Point(x, y+1));
	            if(y>0)
	            	points.push(new Point(x, y-1));
	        }
	    }
	}

Still only does up to x being 2 then exits

#9

The new version looks closer to being correct (although it seem like you’d want to check for out-of-bounds coordinates in the positive direction, not just the negative direction). If it’s still not working though, I think some debug output and/or stepping through in the debugger is probably in order, as that will probably be the most effective way to find the source of the problem.

#10

Thanks Jesse,

Yes, using the Point object so can get x,y incremented. I’ve got this now:


	public void iterativeFill(int initialX, int initialY, char target, char replacement){
	    Queue<Point> points = new LinkedList<Point>();
	    points.add(new Point(initialX, initialY));

	    while(!points.isEmpty()) {
	        Point currentPoint = points.remove();
	        int x = currentPoint.x;
	        int y = currentPoint.y;

	        char current = m[x][y];
	        if((current == target)){
	            m[x][y] = replacement;
	            if(x< m.length - 1)
	               points.add(new Point(x+1, y));
	            if(x>0)
	            	points.add(new Point(x-1, y));
                    if(y<m[x].length)
	                points.add(new Point(x, y+1));
	            if(y>0)
	            	points.add(new Point(x, y-1));
	        }
	    }
	}

Will need to put in the usual visited boolean like had before and then a loop:


		for (int x = 0; x < m.length; x++) 
			for (int y = 0; y < m[x].length; y++) 
           fill.IterativeFill(x,y,'c','w');

Think this could work, doing it this way before changing it to the 2d array in my game which you know is of BlankEntity objects.

#11

Well, this is what I have for an iterative flood fill, does this look correct?..


public void iterativeFill(int initialX, int initialY) {
		Queue<Point> points = new LinkedList<Point>();
		points.add(new Point(initialX, initialY));
		caveCells = new ArrayList<CaveCell>();
		
		while (!points.isEmpty()) {
			Point currentPoint = points.remove();
			int x = currentPoint.x;
			int y = currentPoint.y;

			BlankEntity currentTile = mm[x][y]; // get current tile
	
			if(currentTile instanceof CaveEntity && !currentTile.visited)
			{
				cell = new CaveCell(x, y);
				caveCells.add(cell);
				currentTile.visited = true;
				
				if (x < mm.length - 1 )
					points.add(new Point(x + 1, y));
				if (x > 0)
					points.add(new Point(x - 1, y));
				if (y < mm[x].length -1)
					points.add(new Point(x, y + 1));
				if (y > 0)
					points.add(new Point(x, y - 1));
			}
		}

	}

Where caveCells is an ArrayList of cells for particular cave. The above is called as:


FloodFill f = new FloodFill();

		for (int x = 0; x < mm.length; x++) {
			for (int y = 0; y < mm[x].length; y++) {
				f.iterativeFill(x, y);
				ArrayList<CaveCell> cavec = FloodFill.caveCells;
				if (caveCells.size() > 0) {
					Cave c = new Cave();
					for (CaveCell cell : caveCells) {
						c.cells.add(cell);
					}

					caves.add(c);
					System.out.println("Added to caves arraylist.\n");
				}
			}
		}

Thanks

#12

It does look like it should work, but I could easily have missed something. (I find it tricky to confirm the correctness of this kind of code just by looking it over, since there’s a lot of ways to get it wrong and many of those are easy to miss.)

Is it working correctly? Or are you having problems with it?

#13

You’ll have thousands of identical caves in your ‘caves list’, as adjacent cells are very likely to be in the same cave.

#14

Hi,

Yeah, seems to work, gives me a list of caves - this is used to allow water to be added to the caves later.

Been on hols for 2 weeks so only just getting back to this!

No caves are the same due to the visited property :slight_smile:

Thanks

#15

Ah, you don’t reset the ‘visited’ property when restarting a fill. Okay, that seems counter intuitive, but will work in your case.

To clean up your code a bit, you should remove the static fields, and just return the [icode]ArrayList[/icode] you are building in [icode]iterativeFill(…)[/icode]. There is no need to store it in a field, especially not in a static one.

#16

Thanks Riven,

Makes sense :slight_smile:

#17

Iterative flood fill working a treat and so much faster to render the world with!

Please see here for latest screen shot:

https://sites.google.com/site/sterrialand/development/news/iterativefloodfillimplemented

The code:


package com.mygdx.game;

import java.awt.Point;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class FloodFill {

	BlankEntity[][] map;

	private CaveCell cell;

	public ArrayList<CaveCell> caveCells = new ArrayList<CaveCell>();

	public FloodFill() {
	}

	public FloodFill(BlankEntity[][] map) {
		this.map = map;
	}

	/*
	 * Recursive flood fill - CANNOT handle large caves
	 */
	public void fill(int x, int y) {

		try {
			if (x < 0)
				return;
			if (y < 0)
				return;
			if (x >= map.length)
				return;
			if (y >= map[x].length)
				return;

			BlankEntity currentTile = map[x][y]; // get current tile
			if (currentTile == null)
				return;

			if (currentTile.visited)
				return;

			if (!(currentTile instanceof CaveEntity))
				return;

			currentTile.visited = true;

			cell = new CaveCell(x, y);
			caveCells.add(cell);

			fill(x - 1, y);
			fill(x + 1, y);
			fill(x, y - 1);
			fill(x, y + 1);
		} catch (Exception ex) {
			System.out.println(":-( Cave too large");
		}
	}

	
    /*
     * Iterative Flood fill - stops stack overflow :-)
     */
	public void iterativeFill(int initialX, int initialY) {
		Queue<Point> points = new LinkedList<Point>();
		points.add(new Point(initialX, initialY));
		caveCells = new ArrayList<CaveCell>();
		
		while (!points.isEmpty()) {
			Point currentPoint = points.remove();
			int x = currentPoint.x;
			int y = currentPoint.y;

			BlankEntity currentTile = map[x][y]; // get current tile
	
			if(currentTile instanceof CaveEntity && !currentTile.visited)
			{
				cell = new CaveCell(x, y);
				caveCells.add(cell);
				currentTile.visited = true;
				
				if (x < map.length - 1 )
					points.add(new Point(x + 1, y));
				if (x > 0)
					points.add(new Point(x - 1, y));
				if (y < map[x].length -1)
					points.add(new Point(x, y + 1));
				if (y > 0)
					points.add(new Point(x, y - 1));
			}
		}
	}
}


class CaveCell {
	public int x, y;

	public CaveCell(int x, int y) {
		this.x = x;
		this.y = y;
	}

	@Override
	public String toString() {
		return "X:" + x + " Y:" + y;
	}
}

class Cave {
	public Cave() {
		cells = new ArrayList<CaveCell>();
	}

	public ArrayList<CaveCell> cells;
}
#18

Looks good!

#19

Cheers Jesse,

Couldn’t have done it without your help!

Looking to do some lighting next…not sure of which way to go with this though, looked at using a shader.

Thanks