Does anyone have a fast floodfill?

[Mads]

I was going to check my map for the nearest x-object, using a floodfill. However, I can’t seem to write one that makes sence.
First I was going to go in spirals, but now I’m not so sure. I end up using a lot of lines, and way too many checks for silly things to
even be considered a valid solution. I want to floodfill in four directions, until I find the first of my x-objects (which would therefore be the nearest, right?).

The only things google came up with was redundant to my case, or gave me just as silly spaghetti-code.

Does anyone have a nice implementation of this, lying around?

[CyanPrime]

I kept reading this as fast foodfill, thinking wtf is that?

[theagentd]

It’s not really hard at all to write one. Here is an example of Dijkstra’s pathfinding algorithm which is a flood-fill algorithm with varying costs for moving over different tiles.

	private ScriptPath pathfind(Job job){

		if(!level.checkBounds(job.startX, job.startY) || !level.checkBounds(job.destX, job.destY)){
			return new ScriptPath(job.callback, job.startX, job.startY, job.destX, job.destY, null);
		}

		jobID++;
		openList.clear();

		int startX = (int)job.startX, startY = (int)job.startY;
		int destX = (int)job.destX, destY = (int)job.destY;

		//Start and end flipped since we get the path backwards by traversing the parents of the goal node
		DijkstraData start = getData(level.getNode(destX, destY));
		DijkstraData end = getData(level.getNode(startX, startY));

		if(start.isWall() || end.isWall()){
			return new ScriptPath(job.callback, job.startX, job.startY, job.destX, job.destY, null);
		}

		start.cost = 0;
		start.parent = null;
		start.lastOpened = jobID;
		openList.add(start);

		boolean foundPath = false;
		DijkstraData current;
		while((current = openList.poll()) != null){

			if (current == end) {
				foundPath = true;
				break;
			}

			current.lastClosed = jobID;
			//System.out.println("Closed " + current.node.getX() + ", " + current.node.getY() + " Cost: " + current.cost);

			addNeighbors(current);

		}

		if(!foundPath){
			return new ScriptPath(job.callback, job.startX, job.startY, job.destX, job.destY, null);
		}
		ArrayList<Point2D.Double> waypoints = buildPath(current);

		return new ScriptPath(job.callback, job.startX, job.startY, job.destX, job.destY, waypoints);
	}

You can ignore the cost variable and simply use a normal list for the open list. A note about the lastOpened and lastClosed variables: These could’ve been booleans marking if the node has been visited/closed, but that will force you to reset all tiles to false/false after each job, which is obviously really slow if you have a large map (1024x1024 maps = >1 million nodes for example). By using an int instead, you can just increase the jobID before each job, and all nodes not having the same ID haven’t been visited/closed yet. You still have to reset the whole map every 2^32 = 4294967296th job though xD. A similar optimization could be used for the open list. Instead of calling clear() on it which nulls out all elements in the backing object[] you can just set the size to 0 similar to how ByteBuffer.clear() works to.

[EgonOlsen]

I wrote this one some time ago:

import java.awt.*;
import java.awt.image.*;
import java.util.*;

public class FloodFiller
{

  public Image fill(Image img, int xSeed, int ySeed, Color col)
  {
    BufferedImage bi = new BufferedImage(img.getWidth(null), img.getHeight(null), BufferedImage.TYPE_INT_ARGB);
    bi.getGraphics().drawImage(img, 0, 0, null);
    int x = xSeed;
    int y = ySeed;
    int width = bi.getWidth();
    int height = bi.getHeight();

    DataBufferInt data = (DataBufferInt) (bi.getRaster().getDataBuffer());
    int[] pixels = data.getData();

    if (x >= 0 && x < width && y >= 0 && y < height)
    {

      int oldColor = pixels[y * width + x];
      int fillColor = col.getRGB();

      if (oldColor != fillColor)
      {
        floodIt(pixels, x, y, width, height, oldColor, fillColor);
      }
    }
    return bi;
  }


  private void floodIt(int[] pixels, int x, int y, int width, int height, int oldColor, int fillColor)
  {

    int[] point = new int[] { x, y };
    LinkedList<int[]> points = new LinkedList<int[]>();
    points.addFirst(point);

    while (!points.isEmpty())
    {
      point = points.remove();

      x = point[0];
      y = point[1];
      int xr = x;

      int yp = y * width;
      int ypp = yp + width;
      int ypm = yp - width;

      do
      {
        pixels[xr + yp] = fillColor;
        xr++;
      }
      while (xr < width && pixels[xr + y * width] == oldColor);

      int xl = x;
      do
      {
        pixels[xl + yp] = fillColor;
        xl--;
      }
      while (xl >= 0 && pixels[xl + y * width] == oldColor);

      xr--;
      xl++;

      boolean upLine = false;
      boolean downLine = false;

      for (int xi = xl; xi <= xr; xi++)
      {
        if (y > 0 && pixels[xi + ypm] == oldColor && !upLine)
        {
          points.addFirst(new int[] { xi, y - 1 });
          upLine = true;
        }
        else
        {
          upLine = false;
        }
        if (y < height - 1 && pixels[xi + ypp] == oldColor && !downLine)
        {
          points.addFirst(new int[] { xi, y + 1 });
          downLine = true;
        }
        else
        {
          downLine = false;
        }
      }
    }
  }
}

However, i’m not sure if this really relates to your actual problem… ???

[Mads]

The thing is that I know what I’m looking for, but not where it is. I have no such thing as a destination when the algorithm starts, so it just has to spread outwards until something that’ll do is encountered.

[Regenuluz]

Which is exactly what Dijkstra’s pathfinding algorithm does. ^^

Dijkstra's algorithm

[Mads]

@Regenuluz

Which is exactly what Dijkstra’s pathfinding algorithm does. ^^

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

I must be missing something completely here though. I definitely see a destX/destY variable in the Job.
I’m not really interrested in the pathfinding part of this, just finding the coords of the nearest X (only knowing what should be on the tile I’m looking for, but not where it is).

[Mads]

Oh, I just realized I can just take the neighbors of neighbors until I find my tile!

However, how do I avoid searching in just one direction? If I always add all the neighbors to the open list, and then look for neighbors to the open list from the top, then I will only go in one direction. How do I avoid that?

[sproingie]

You’ll go in one direction til you can’t any more, then you’ll “bounce” over to another edge of your filled region and start from there. What your filled area looks like depends on how you store your open list. Check out the wikipedia page on floodfill for some visual comparisons of how the fill progresses depending on the data structure you use. If you use a queue for your open list, you’ll get a nice diamond-shaped fill, while the stack gives you more of a scan behavior. You can also choose randomly, though that will cost you some overhead.

Dijkstra is like flood fill except you record whole paths, not just nodes, and you stop when you get to your destination. If you’re looking to visit every node, you don’t keep paths, so you get floodfill.

[Mads]

@sproingie

You’ll go in one direction til you can’t any more, then you’ll “bounce” over to another edge of your filled region and start from there. What your filled area looks like depends on how you store your open list. Check out the wikipedia page on floodfill for some visual comparisons of how the fill progresses depending on the data structure you use. If you use a queue for your open list, you’ll get a nice diamond-shaped fill, while the stack gives you more of a scan behavior. You can also choose randomly, though that will cost you some overhead.

Dijkstra is like flood fill except you record whole paths, not just nodes, and you stop when you get to your destination. If you’re looking to visit every node, you don’t keep paths, so you get floodfill.

My area is infinite though :emo: How would I code-wise go about making the diamond?

[sproingie]

Push each neighbor onto a queue, then dequeue when you select an open node. That’ll give you an infinitely expanding diamond (or square if you go diagonally)

If you’re looking for the “nearest X” and your area is infinite, however, you’re using the wrong algorithm. If you already know the locations of your various X, then you should be pathfinding to them.

[DrZoidberg]

Why don’t you just go through the list of all your objects and check their distance.
Unless you have millions of objects it might be faster than floodfill.

@Mads

Oh, I just realized I can just take the neighbors of neighbors until I find my tile!

However, how do I avoid searching in just one direction? If I always add all the neighbors to the open list, and then look for neighbors to the open list from the top, then I will only go in one direction. How do I avoid that?

I don’t see what you mean. Taking the neighbors of neighbors should go in all directions.

while(openList.isEmpty() == false) {
    ArrayList<Tile> newOpenList = new ArrayList<Tile>();
    for(Tile tile: openList) {
        if(tile.isEmpty() == false) {
            //found the closest object
        }
        for(Tile neighbor: tile.getAllNeighbors()) {
            if(neighbor.hasBeenVisited() == false) {
                neighbor.visit();
                newOpenList.add(neighbor);
            }
        }
    }
    openList = newOpenList
}

[Mads]

I really appriciate the replies guys, even though I’m derping hardcore right now

@sproingie

Push each neighbor onto a queue, then dequeue when you select an open node. That’ll give you an infinitely expanding diamond (or square if you go diagonally)

If you’re looking for the “nearest X” and your area is infinite, however, you’re using the wrong algorithm. If you already know the locations of your various X, then you should be pathfinding to them.

It’s not infinite, but it’s really big. I just want to search for so long (or such a large area), before giving up. I don’t know where my X’s are.

@DrZoidberg

Why don’t you just go through the list of all your objects and check their distance.
Unless you have millions of objects it might be faster than floodfill.

@Mads

Oh, I just realized I can just take the neighbors of neighbors until I find my tile!

However, how do I avoid searching in just one direction? If I always add all the neighbors to the open list, and then look for neighbors to the open list from the top, then I will only go in one direction. How do I avoid that?

I don’t see what you mean. Taking the neighbors of neighbors should go in all directions.

while(openList.isEmpty() == false) {
    ArrayList<Tile> newOpenList = new ArrayList<Tile>();
    for(Tile tile: openList) {
        if(tile.isEmpty() == false) {
            //found the closest object
        }
        for(Tile neighbor: tile.getAllNeighbors()) {
            if(neighbor.hasBeenVisited() == false) {
                neighbor.visit();
                newOpenList.add(neighbor);
            }
        }
    }
    openList = newOpenList
}

The map is definitely too big to check every single tile. I only want to search within… let’s say a 100 tile radius of the starting point.

I’m having some trouble here, implementing it. In my A*, I have nodes in a map (2D array) equal to the size of the map I’m searching. It’s a double/replicate of it, holding just the values I need.

With this dimaond-shaped-floodfill, I’m looking for a Tile that has a specific type of object on it/in the class. Therefore, I can’t just use nodes because they need to know both what is on their representative Tile, and where they belong in the map (coordinates).
I wanted to just use my actual TileMap, and ignore the overhead, but the tiles themselves (in my actual map) don’t know their position.

This is what I have written so far

public class Floodfinder {
	
	/** TileMap which we're searching (this is the actual map) */
	private TileMap map;
	/** List containing the points that have yet to be searched */
	private ArrayList<Tile> open = new ArrayList<Tile>();
	/** Contains the already searched coordinates */
	private ArrayList<Tile> closed = new ArrayList<Tile>();
	
	public Floodfinder(TileMap map) {
		this.map = map;
	}
	
	/**
	 * Finds the location of the tile that hosts nearest WorldObject of a given type.
	 * 
	 * @param obj The object type we're looking for (not the actual object - they just need to be of the same type)
	 * @param sx The source x
	 * @param sy The source y
	 */
	public Point findTile(WorldObject obj, int sx, int sy) {
		closed.clear(); // Initial clear of both lists for safety
		open.clear();
		open.add(map.getTile(sx, sy)); // Add the starting point
		
		//XXX: Add a check for how far into the search we are (loop).. How big of an area are we currently covering? Should we stop?
		
		Tile current = map.getTile(?int?, ?int?); //open.get(open.size()); // Getting the last element in the queue
		open.remove(current);
		closed.add(current);
		
		for (int x = -1; x < 2; x++) { // Looking for neighbours
			for (int y = -1; y < 2; y++) {

				if ((x == 0) && (y == 0)) { // not a neighbour, its the current tile
					continue;
				}

				if ((x != 0) && (y != 0)) { // no diagonals
					continue;
				}

				// determine the location of the neighbour and add it to the open list
				int xp = x + current.x; // Problems arise here, again.
				int yp = y + current.y;
				open.add(map.getTile(xp, yp));
			}
		}
		return null;
	}

}

Also, how do I check the radius of the area the diamond is covering? I only want to search for so long…

[sproingie]

Have a max count of nodes to search, decrement it every time you search a node, quit when it hits zero. If you have any obstacles in the way, then the size of your search area is indeterminate. If you don’t have obstacles, then let me reiterate how wrong this algorithm is.

[Mads]

@sproingie

Have a max count of nodes to search, decrement it every time you search a node, quit when it hits zero. If you have any obstacles in the way, then the size of your search area is indeterminate. If you don’t have obstacles, then let me reiterate how wrong this algorithm is.

I do have obstacles How do you think I should solve this problem instead, though?
This is for finding the nearest tree for goblins, in here http://www.java-gaming.org/topics/iconified/26136/view.html- to be quite specific.

[sproingie]

Take the manhattan distance (“straight line” without diagonals) to all the visible trees. Pathfind to the nearest one, and remove from the list of nearby trees anything with a manhattan distance greater than that path’s length. Repeat the process for remaining trees in the list, then out of the ones you have paths for, take the one with the shortest path.

Large obstacles present some corner cases for this algorithm, but you can fudge the calculated distance if you find that obstacles impinge on your straight line between your start position and the destination.

[Mads]

@sproingie

Take the manhattan distance (“straight line” without diagonals) to all the visible trees. Pathfind to the nearest one, and remove from the list of nearby trees anything with a manhattan distance greater than that path’s length. Repeat the process for remaining trees in the list, then out of the ones you have paths for, take the one with the shortest path.

Large obstacles present some corner cases for this algorithm, but you can fudge the calculated distance if you find that obstacles impinge on your straight line between your start position and the destination.

I can’t just do that. I have lots of lakes that would screw this up. Also, my entities work even when not rendered, so I would have to take all trees in the level, which could be thousands.

[sproingie]

“Visible” here refers to some arbitrarily determined set based on your current position, not real actual visibility as rendering is concerned. You don’t need to render for this, nor do you need to select every tree. Just all the trees in some reasonably sized rectangle.

Also, with lots of obstacles, flood fill is virtually guaranteed to end up with pathological cases, such as taking a very loooong trip through a narrow “corridor”. Using a queue might mitigate this, but I bet I could still cook up a way to break it even with plausible map topology.

[Mads]

@sproingie

“Visible” here refers to some arbitrarily determined set based on your current position, not real actual visibility as rendering is concerned. You don’t need to render for this, nor do you need to select every tree. Just all the trees in some reasonably sized rectangle.

Also, with lots of obstacles, flood fill is virtually guaranteed to end up with pathological cases, such as taking a very loooong trip through a narrow “corridor”. Using a queue might mitigate this, but I bet I could still cook up a way to break it even with plausible map topology.

Tried it now, and making one guys visible range 10 in all directions causes me to loop through 400 tiles. If those are all trees, or even half, I’dhave to make 200 patfinding calls to see which is closer.
With many trees and many guys, that causes trouble - sadly.

I have a feeling making a spiral around the guy until a tree is hit, can improve both visible distance, and speed with many trees around. :persecutioncomplex:

[sproingie]

You do not make 200 pathfinding calls, you sort the trees by distance, start with the closest one, then discard anything with a straight-line distance longer than the shortest path you have. If your tree density is 50%, then you start with a smaller rectangle, like, oh, looking for trees right next to your position, then widen it as needed. Using a spiral is certainly a good way to go there, since it’ll find trees in sorted order automatically – not quite perfectly, but close enough.