I reply because i want to follow this thread. Not so long ago i had the same problem as you have now, i wanted to make Diablo. The only thing i could think of was to use a path finder to make sure that every part of the map is reachable for the player. The problem however, is that path finders in java are not fast.
The only solution i could think of, is to make maps like a game of Domino. So every domino stone is a predefined map, and you connect the new map to the corresponding number of the domino stone. This way you know the starting point and the end point. It's a bit hard to explain.
The problem with this method, is that it isn't really random like what you made.

Greetings, Dippo.

How 'bout this?

Code Example

1. PImage img, filtered;
2. color blue = color(70, 150, 220);
3.  
4. void setup() {
5.   img = loadImage("island.png");
6.   size(img.width, img.height);
7.   filtered = filterImage(img, 4);
8. }
9.  
10. void draw() {
11.   image(mousePressed?img:filtered, 0, 0); // press mouse to see original image
    
12. }
13.  
14. PImage filterImage(PImage img, int erodeLevel) {
15.   PImage e = img.get();
16.   PImage f = img.get();
17.   for (int i=0; i<erodeLevel; i++) { e.filter(ERODE); }
18.   for (int i=0; i<img.pixels.length; i++) {
19.     if (e.pixels[i]==blue) { f.pixels[i]=blue; }
20.   }
21.   f.updatePixels();
22.   return f;
23. }

@amnon: great suggestion! It looks like the ERODE filter is based on luminence, which works ok but has a few limitations:

1. Must be run on a PImage - I didn't mention in my post, but the image is just for the example, the real level is in a 2d array. I suppose it could be stored as an image, but I think the int array is faster.
2. The filter misses some bits and removes some of the "beach" along the coast.

This might well be the quickest solution :)

My start at a recursive fill:

1. color bgColor = color(0);
   
2. color landColor = color(255, 0, 0);
   
3. color blockColor = color(255, 150, 0);
   
4. color newColor = color(40);
   
5. 
   
6. void setup() {
   
7. 
   
8.   size(400, 400);
   
9.   background(bgColor);
   
10.   noStroke();
    
11. 
    
12.   fill(landColor);
    
13.   rect(width/2 - 100, height/2-100, 200, 200);
    
14. 
    
15.   fill(blockColor);
    
16.   for (int i=0; i<10; i++) {
    
17. 
    
18.     rect(random(0, width), random(0, height), 30, 30);
    
19.   }
    
20. 
    
21.   loadPixels();
    
22.   for (int i=0; i<pixels.length; i++) {
    
23.     if (pixels[i] == blockColor) {    // only check blocks
    
24.       int x = i % width;
    
25.       int y = i / width;
    
26.       checkForIsolatedPixels(x, y);
    
27.     }
    
28.   }
    
29.   updatePixels();
    
30. }
    
31. 
    
32. void checkForIsolatedPixels(int x, int y) {
    
33.   if (pixels[y*width + x] != blockColor || x < 0 || x > width-1 || y < 0 || y > height-1) {
    
34.     pixels[y*width + x] = newColor;
    
35.     return;
    
36.   }
    
37.   else {
    
38.     pixels[y*width + x] = newColor;
    
39.     checkForIsolatedPixels(x, y-1);  // u
    
40.     checkForIsolatedPixels(x+1, y);  // r
    
41.     checkForIsolatedPixels(x, y+1);  // d
    
42.     checkForIsolatedPixels(x-1, y);  // l
    
43.     return;
    
44.   }
    
45. }

Of course, finding a solution works best if you create an example that simulates your actual code. I'm just working with what you post here. I've taken your last example as a starting point, but that has some problems. First it's not safe, so it often runs out of bounds. Second, it fills all blockColored pixels, not just the ones connected to the main land.

How 'bout this?

Code Example

1. // press a key to generate a new scene
   
2. 
   
3. color bgColor = color(0);
4. color landColor = color(255, 0, 0);
5. color blockColor = color(255, 150, 0);
6. color newColor = color(255);
7.  
8. HashSet <PVector> Q = new HashSet <PVector> ();
9. HashSet <PVector> Qadd = new HashSet <PVector> ();
10.  
11. PGraphics pg;
12. PImage floodfill, result;
13.  
14. void setup() {
15.   size(1202, 400);
16.   pg = createGraphics(400, 400, JAVA2D);
17.   reset();
18. }
19.  
20. void draw() {
21.   background(255);
22.   image(pg, 0, 0); // original scene
    
23.   image(floodfill, pg.width+1, 0); // floodfilled main land plus connected areas
    
24.   image(result, 2*(pg.width+1), 0); // removed offshore islands
    
25. }
26.  
27. void keyPressed() {
28.   reset();
29. }
30.  
31. void reset() {
32.   drawScene();
33.   floodfill = floodFill(pg);
34.   result = filterImage(pg, floodfill);
35. }
36.  
37. void drawScene() {
38.   pg.beginDraw();
39.   pg.noStroke();
40.   pg.background(bgColor);
41.   pg.fill(landColor);
42.   pg.rect(pg.width/2 - 100, pg.height/2-100, 200, 200);
43.   pg.fill(blockColor);
44.   for (int i=0; i<10; i++) {
45.     pg.rect(random(pg.width), random(pg.height), 30, 30);
46.   }
47.   pg.endDraw();
48. }
49.  
50. PImage floodFill(PGraphics pg) {
51.   PImage result = pg.get();
52.   Q.add( new PVector(result.width/2, result.height/2) );
53.   while (!Q.isEmpty()) {
54.     Qadd.clear();
55.     result.loadPixels();
56.     for (PVector p : Q) {
57.       int curX = (int) p.x;
58.       int curY = (int) p.y;
59.       result.pixels[curX+curY*result.width] = newColor;
60.       addValidXY(result, curX+1, curY);
61.       addValidXY(result, curX-1, curY);
62.       addValidXY(result, curX, curY+1);
63.       addValidXY(result, curX, curY-1);
64.     }
65.     result.updatePixels();
66.     Q.clear();
67.     Q.addAll(Qadd);
68.   }
69.   return result;
70. }
71.  
72. void addValidXY(PImage img, int x, int y) {
73.   if ((x < 0 || x >= img.width) || (y < 0 || y >= img.height)) return;
74.   else if (!isValidColor(img.pixels[x+y*img.width])) return;
75.   else { Qadd.add(new PVector(x, y)); }
76. }
77.  
78. boolean isValidColor(color c) {
79.   return (c == landColor || c == blockColor);
80. }
81.  
82. PImage filterImage(PGraphics pg, PImage msk) {
83.   PImage result = pg.get();
84.   for (int i=0; i<result.pixels.length; i++) {
85.     if (msk.pixels[i]!=newColor) {
86.       result.pixels[i] = bgColor;
87.     }
88.   }
89.   return result;
90. }

For sure - the code has gotten so complex it's hard to extract the relevant parts. Essentially, I have a 2d array of ints representing various "tiles", in a range from 0-5 or so. 0=ocean, 1=beach, 2=grass, etc.

Your example (seems) to do the same as my admittedly messy code? Running it, yours fills in all the squares as well?

I think your HashSet is suggesting I store all traversed pixels (as PVectors since we need x and y) in a list - couldn't I then say that if we bump into "land" (meaning that space is traversable), a flag is set and when the recursion is done we fill in one color, but if it only hits "ocean" it gets filled in blue?

PS: thanks for clearly putting a lot of time into your suggested code - appreciated!

In  this topic there is a Processing  A* search implementation  and a link to some variations in javaScript. The jump point search seams to be really fast...

Hey Jeff,

Our codes operate on the same principle but with a crucial difference. My code only fills the squares attached to the main land in the center (so only a specific selection of squares, not all of them), while your code fills every square on the screen. The difference is important, because my flood fill can be used to distinguish the main land from the offshore areas. Let me post the images that I see when I run these codes...

Your code (except with a white newColor)


My code (left = original, middle = floodfilled main land, right = offshore areas removed)


Hope this clears up my code attempt. Indeed it's based on those kind of 'recursive' principles. And as v.k. points out, there may be much faster implementations of relevant algorithms (of course PVector is notoriously slow already). However, when you hold the key pressed on my code, it still runs realtime, so it's not that slow. As you conclude, my implementation is indeed about floodfilling / traversing all pixels of the main land for until you meet an 'ocean'. Once you know that traversable land, the rest should be ocean. I think this solution is better than the other way around (aka trying to find all isolated areas).

@vk: great suggestion - A* was sitting somewhere in my brain! :)

Looking back at my recursive code (with some great insights from Amnon), this now works!



And of course the code:

1. color bgColor = color(100);              // background
   
2. color landColor = color(255, 0, 0);      // large center square ("land")
   
3. color blockColor = color(255, 150, 0);   // color for random blocks
   
4. color newColor = color(40);              // replace blocks' color if they hit "land"
   
5. 
   
6. ArrayList<PVector> testPx = new ArrayList<PVector>();    // store pixels as we check to see if they hit land
   
7. boolean hitLand;                                         // flag to check if we've hit land (keep) or not (delete)
   
8. 
   
9. void setup() {
   
10. 
    
11.   size(400, 400);
    
12.   background(bgColor);
    
13.   noStroke();
    
14.   noSmooth();      // !!! seems to be needed for the sharp edges on rect
    
15. 
    
16.   // square in center (this is "land") - if blocks touch this they are kept
    
17.   fill(landColor);
    
18.   rect(width/2 - 100, height/2-100, 200, 200);
    
19. 
    
20.   // random blocks to test
    
21.   fill(blockColor);
    
22.   for (int i=0; i<10; i++) {
    
23.     rect(random(0, width), random(0, height), 30, 30);
    
24.   }
    
25. 
    
26.   // check blocks to see if they hit the center square
    
27.   loadPixels();
    
28.   for (int i=0; i<pixels.length; i++) {
    
29.     if (pixels[i] == blockColor) {    // only check blocks
    
30.       int x = i % width;
    
31.       int y = i / width;
    
32.       testPx.clear();                  // clear the list of px to be tested
    
33.       hitLand = false;                 // lower flag
    
34.       checkForIsolatedPixels(x, y);    // check recursively
    
35. 
    
36.       // if we didn't hit land, set to background color (delete)
    
37.       if (!hitLand) {
    
38.         for (PVector p : testPx) {
    
39.           pixels[int(p.y) * width + int(p.x)] = bgColor;
    
40.         }
    
41.       }
    
42.     }
    
43.   }
    
44.  
    
45.   // all done!
    
46.   updatePixels();
    
47. }
    
48. 
    
49. void checkForIsolatedPixels(int x, int y) {
    
50.   testPx.add(new PVector(x, y));        // add to ArrayList
    
51. 
    
52.   // if we've hit something other than the block, we're done
    
53.   if (pixels[y*width + x] != blockColor) {
    
54.     if (pixels[y*width + x] == landColor) {
    
55.       hitLand = true;                          // hit some land in the process, set true
    
56.     }
    
57.     return;
    
58.   }
    
59. 
    
60.   // check all neigbors so long as we're not going offscreen
    
61.   else {
    
62.     pixels[y*width + x] = newColor;
    
63.     if (y-1 >= 0) {
    
64.       checkForIsolatedPixels(x, y-1);  // u
    
65.     }
    
66.     if (x+1 < width) {
    
67.       checkForIsolatedPixels(x+1, y);  // r
    
68.     }
    
69.     if (y+1 < height) {
    
70.       checkForIsolatedPixels(x, y+1);  // d
    
71.     }
    
72.     if (x-1 >= 0) {
    
73.       checkForIsolatedPixels(x-1, y);  // l
    
74.     }
    
75.     return;
    
76.   }
    
77. }

@Amnon: your reply appeared just as I submitted mine!

Your screenshots look different than mine. The middle image on my machine has filled in everything except some odd vertical lines and the righthand image has no squares left (they are either black or red). Maybe I copied something wrong - I also found that turning off smooth() seems to help.

Speed (in my case) is definitely not an issue, since I'll generate the level at startup and never again while running.

Essentially, I have a 2d array of ints representing various "tiles", in a range from 0-5 or so. 0=ocean, 1=beach, 2=grass, etc.

When I read this, I'm also contemplating a solution based on grid selection totals/averages. Because a 10x10 ocean grid would be 0. But a land grid would total around 150 or average around 1.8 or something. So somehow it could be used to distinguish the type of the grid, which can then be used to look at the deviation. For example grass (2) in the middle of the ocean (average of for example 0.25) wouldn't be allowed. Just an idea. The recursive floodfilling is probably the fastest.

One last suggestion, because I managed to find an old sketch from 2010 (!) that I thought was perhaps useful. So the suggestion is that perhaps even cellular automata could be of use in this case. Since you already have a CA-style 2D grid. With the right ruleset you could let the offshore areas 'die' after a few generations of CA. The code below was used to create 2D caves, but visually and conceptually there are similarities with islands. Press 'c' to create a new grid, then hold 'a' to see the CA in action.

Inspirational Code Example

1. /**
2.  * Using cellular automata  to generate caves
3.  * Coded by Eddie Lee, October 16, 2010
4.  * URL: http://illogictree.com/blog/2010/10/cellular-automata-all-the-way/#more-2801
5.  * Ported to Processing by Amnon Owed, October 22, 2010
6.  *
7.  * c = create grid
8.  * a = run CA
9.  * space = generate random grid and run 30 CA's
10.  *
11.  */
12.  
13. int numTilesRows;
14. int numTilesCols;
15. int[][] myMatrix;
16. int numSmoothingIterations = 30;
17.  
18. void setup() {
19.   size(500,500);
20.   smooth();
21.   noStroke();
22.   generateMatrix(100,100,0.45);
23.   for (int i=0; i<numSmoothingIterations; i++) { runCellularAutomata(); }
24. }
25.  
26. void draw() {
27.   background(255);
28.  
29.   for (int y=0; y<numTilesRows; y++) {
30.     for (int x=0; x<numTilesCols; x++) {
31.       fill(0,myMatrix[y][x]*255);
32.       rect(ceil(x*float(width)/numTilesCols),ceil(y*float(height)/numTilesRows),ceil(float(width)/numTilesCols),ceil(float(width)/numTilesRows));
33.     }
34.   }
35. }
36.  
37. void keyPressed() {
38.   if (key == 'c') { int dimensions = int(random(1,250)); generateMatrix(dimensions,dimensions,random(0.3,0.7)); }
39.   if (key == 'a') { runCellularAutomata(); }
40.   if (key == ' ') {
41.     int dimensions = int(random(1,250));
42.     generateMatrix(dimensions,dimensions,random(0.3,0.7));
43.     for (int i=0; i<numSmoothingIterations; i++) { runCellularAutomata(); }
44.   }
45. }
46.  
47. void generateMatrix(int rows, int cols, float ratio) {
48.   numTilesRows = rows;
49.   numTilesCols = cols;
50.   myMatrix = new int[numTilesRows][numTilesCols];
51.  
52.   for (int y=0; y<numTilesRows; y++) {
53.     for (int x=0; x<numTilesCols; x++) {
54.       float coinflip = random(1);
55.       if (coinflip <= ratio) { myMatrix[y][x] = 1; }
56.       else { myMatrix[y][x] = 0; }
57.     }
58.   }
59. }
60.  
61. int countNumWallsNeighbors(int xPos, int yPos, int distance) {
62.   int count = 0;
63.  
64.   for (int y = -distance; y <= distance; y++) {
65.     for (int x = -distance; x <= distance; x++) {
66.       if (xPos + x < 0 || xPos + x > numTilesCols - 1 || yPos + y < 0 || yPos + y > numTilesRows - 1 ) { } // do nothing @ window boundaries
67.       else if (myMatrix[yPos + y][xPos + x] != 0 ) { count++; }
68.     }
69.   }
70.  
71.   return count;
72. }
73.  
74. void runCellularAutomata() {
75.   int[][] outMatrix = new int[numTilesRows][numTilesCols]; // temporary matrix
76.  
77.   for (int y=0; y<numTilesRows; y++) {
78.     for (int x=0; x<numTilesCols; x++) {
79.       int numWalls = countNumWallsNeighbors(x,y,1);
80.       if (numWalls >= 5) { outMatrix[y][x] = 1; }
81.       else { outMatrix[y][x] = 0; }
82.     }
83.   }
84.  
85.   for (int y=0; y<numTilesRows; y++) {
86.     for (int x=0; x<numTilesCols; x++) {
87.       myMatrix[y][x] = outMatrix[y][x];
88.     }
89.   }
90. }

@Amnon: all interesting suggestions. I think the noSmooth() issue has to do with 1.5 where (I think) smooth is not on by default but is in 2.0 (which I'm running).  Good to know that the smoothing can cause problems with color-specific matching like this.

Going to dig into some possibilities - thanks!