Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (536)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Does anyone have a fast floodfill?  (Read 7814 times)
0 Members and 1 Guest are viewing this topic.
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Posted 2012-04-03 05:42:41 »

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? Smiley 

Offline CyanPrime
« Reply #1 - Posted 2012-04-03 06:33:31 »

I kept reading this as fast foodfill, thinking wtf is that?  Tongue
Offline theagentd
« Reply #2 - Posted 2012-04-03 08:17:36 »

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.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
   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.

Myomyomyo.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline EgonOlsen
« Reply #3 - Posted 2012-04-03 08:39:37 »

I wrote this one some time ago:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
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... Huh

Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #4 - Posted 2012-04-03 16:53:14 »

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.

Offline Regenuluz
« Reply #5 - Posted 2012-04-03 17:00:43 »

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

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #6 - Posted 2012-04-03 17:14:54 »

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

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

 Cheesy

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). Tongue

Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #7 - Posted 2012-04-03 17:42:54 »

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?

Offline sproingie

JGO Kernel


Medals: 202



« Reply #8 - Posted 2012-04-03 18:10:54 »

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.  
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #9 - Posted 2012-04-03 18:17:55 »

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?

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline sproingie

JGO Kernel


Medals: 202



« Reply #10 - Posted 2012-04-03 18:57:14 »

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.
Offline DrZoidberg

Senior Member


Medals: 15



« Reply #11 - Posted 2012-04-03 18:58:25 »

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.

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.
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
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
}
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #12 - Posted 2012-04-03 19:10:15 »

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

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.

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.

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.
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
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   Sad
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
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...

Offline sproingie

JGO Kernel


Medals: 202



« Reply #13 - Posted 2012-04-03 19:15:40 »

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.


Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #14 - Posted 2012-04-03 19:19:33 »

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 Smiley 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.

Offline sproingie

JGO Kernel


Medals: 202



« Reply #15 - Posted 2012-04-03 20:41:43 »

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.

Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #16 - Posted 2012-04-03 20:50:59 »

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.

Offline sproingie

JGO Kernel


Medals: 202



« Reply #17 - Posted 2012-04-03 21:03:04 »

"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.
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #18 - Posted 2012-04-04 17:35:13 »

"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

Offline sproingie

JGO Kernel


Medals: 202



« Reply #19 - Posted 2012-04-04 17:43:39 »

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.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Riven (20 views)
2014-07-29 18:09:19

Riven (13 views)
2014-07-29 18:08:52

Dwinin (12 views)
2014-07-29 10:59:34

E.R. Fleming (31 views)
2014-07-29 03:07:13

E.R. Fleming (12 views)
2014-07-29 03:06:25

pw (42 views)
2014-07-24 01:59:36

Riven (42 views)
2014-07-23 21:16:32

Riven (28 views)
2014-07-23 21:07:15

Riven (29 views)
2014-07-23 20:56:16

ctomni231 (60 views)
2014-07-18 06:55:21
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!