Detecting islands on a 2d map?

Game Mechanics
#1

I’ve managed to use a perlin noise generator to generate a random 512x512 map.

If the value the noise spits out is lower than 125, for example, the tile will be water. Otherwise its a land tile.

What I’m trying to do is scan over the map, detect and remove any island that touches the edges, also if the surface area of an island is below say 45 then remove it. Any ideas?

Could I for loop over the map, detect a land tile (that hasn’t already been filled) and start filling adjacent tiles. If I can’t fill any more I must assume that area is an island. If any of the land tiles are y:0, x:0, y:height or x:width, remove the island as it touches the edges.

#2

Either you try to mark areas by filling them (going around the border of the map, fill everything that touches the
edges with some kind of flood-fill, then remove all “marked” aread-> turning them into water-tiles)

or you manipulate your generator, that it will never generate high tiles near the edges, eg letting the land fall off
the more you get to the edges.
Or having the high hills in the lowest resolution only in the middle.
-> then smoothing it.

here is some example I wrote a while back:

#3

Yeah I think I’ll try sloping the terrain height down closer to the edges. But I also want to detect islands and store each one as an object, so I can give them their own attributes.

#4

experiment with a flood fill method (just like filling colors in a paint program)

this way you can detect each area.

fill at any point, and mark the filled area (on land) with an ID,
take the next tile that has not been marked with an ID, fill it with a new ID.

etc

this way you can detect all island, and assign their are a unique ID.

#5

Pretty much what Damocles said, I would iterate over the pixels and do something like this:


List<Island> islands;

for (int y = 0; y < height; y++)
    for (int x = 0; x < width; x++)
    	if (tiles[y][x] != WATER && !tileInIsland(x, y))
    		islands.add(new Island(x, y));

private boolean tileInIsland(int x, int y) {
	for (Island i : islands)
		if(i.contains(x, y))
			return true;

	return false;
}

class Island {
	Set<Point> tiles;
	// other fields as necessary

	public Island(int x, int y) {
		tiles = floodFill(x, y);
	}

	public boolean contains(int x, int y) {
		return tiles.contains(new Point(x, y));
	}
}

Basically if the tile isn’t water, and it isn’t already part of an island, then it must be a new island, so create a new island using that as the seed point.

#6

I gave flood fill a go but it only seems to result in a stack overflow.

This gets called every time a new island is made. The int[] tiles array contains the tile ids of the map, 0 is land and 1 is water. Each island class has a List coords = new ArrayList();

	public void floodFill(int[] tiles, int width, int height, Coord current, Coord target){
		//Check if target x,y is out of bounds.
		if(target.getX() < 0 || target.getY() < 0 || target.getX() >= width || target.getY() >= height) return;
		//Check if target x,y is a land tile.
		if(tiles[target.getX() + target.getY() * width] != 0) return;
		//Checks if target x,y has already been filled.
		if(contains(target.getX(), target.getY())) return;

		//Add target to filled tiles list.
		coords.add(target);

		//Fill adjacent tiles.
		floodFill(tiles, width, height, target, new Coord(current.getX() + 1, current.getY()));
		floodFill(tiles, width, height, target, new Coord(current.getX() - 1, current.getY()));
		floodFill(tiles, width, height, target, new Coord(current.getX(), current.getY() + 1));
		floodFill(tiles, width, height, target, new Coord(current.getX(), current.getY() - 1));
		return;
	}
	
	//Checks filled tiles list for specific coords.
	public boolean contains(int x, int y){
		return coords.contains(new Coord(x, y));
	}

I’m not sure if I’m doing something completely wrong here.

#7

You’re using recursive flood fill, not the best solution. It tends to cause those stackoverflows.

Use an iterative approach as documented on the wikipedia page under “Alternative implementations”: http://en.wikipedia.org/wiki/Flood_fill

#8

Or could maybe forget flood fill?

for (each tile on map) {
  if (sea)
    continue
  
  if (no adjacent tiles are on islands)
    start new island with just this tile
  else
    merge this tile with any adjacent island(s)
}
#9

You would have to add code to detect and merge “islands” that connect together.

#10

Indeed. I was suggesting adding that code, rather than adding the code to do a flood fill!

Just a matter of taste I guess - seemed like it might be a simpler algorithm. Or at least an alternative if flood filling was proving to be a problem.

#11

Right, I had a go at trying to fill in island tiles non-recursively and came up with this. This is a method called when a tile is detected which doesn’t belong to an island.

http://pastebin.com/t1h1ESLg

This results in a Concurrent Modification Exception, pointing to line 12.

#12

Try replacing scanCoords.add() with coord.add()


//Add new coord to scan list.
 scanCoords.add(new Coord(xa, ya)); // <-- will cause CME on coord.next()

You might have to call coord.previous() once or twice after adding too if you want the added tile to be the next to show up.
Review the docs: http://docs.oracle.com/javase/7/docs/api/java/util/ListIterator.html#add(E)

EDIT: also note that that is an 8-way flood fill, so tiles can connect diagonally:

[spoiler]…[/spoiler]
[spoiler]…[/spoiler]

You may or may not want that behavior.

#13

So, my thought is to use a combination of a flood-fill and a grid style 2d iterator~

Takes care of the currently listed cases, I believe, and does it without the whole recursive thing. The only issue is that it does ‘create’ a bunch of Coordinate objects (Local only), but if you’re creating a map then the bit of overhead there shouldn’t be too bad.

http://pastebin.java-gaming.org/d82f86e7f0a17

#14

I have a slightly different way of identifying islands.

Basically i perform two passes of the provided map:

1st pass:

  • build up a map of smaller connected regions with each cell given a region id of these smaller connected regions
  • maintain a look up table from the ids of these smaller connected regions to the id of the connected region that was last processed for that connected region.

2nd pass:

  • using the lookup table, set each cell’s region id with the last processed connected region’s id

See the example code here:

http://pastebin.java-gaming.org/82f8e7f7a0710

Note that this was copied from a Java4k entry i was making so it is not OO or particularily friendly but should give you the idea.

#15

Was bored:
http://pastebin.java-gaming.org/8efa7008a0c17

It’s not super efficient, but on your image and my machine it’s consistently less than a fifth of a second to process all the islands.

Change “map.png” to whatever your picture is.
(also currently assumes (0, 0) is a land tile, otherwise you have to hardcode it)

Eliminating islands smaller than 45 (or whatever number) is simple:


for (int i = islands.size() - 1; i >= 0; i--) {
    if (islands.get(i).size() < 45)
        islands.remove(i);
}
#16

I’m going to be away for a few days so I’ll keep coding in a couple days time. Coding is more of a hobby if mine so I really appreciate the help you guys are giving me, thanks a lot.

#17

I’ve had a go after looking at the code snippets you guys provided and this is what I’ve come up with.

Once the tiles are defined I loop over the entire map, checking if the tile is solid and doesn’t already belong to an island.

for(int y = 0; y < height; y++){
			for(int x = 0; x < width; x++){
				if(tileId[x][y] == 0 && !tileIsIsland(x, y)){
					new Island(getCoords(x, y));
				}
			}
		}

If it finds such a tile it makes a new island object that only takes a List in its constructor. This list contains will contain all the tiles belonging to that island.

Here is the getCoords() method:

The tileId[][] array contains the tile id’s of the map. 1 = water, 0 = land.

	public List<Coord> getCoords(int xa, int ya){
		//List of tiles that belong to island.
		List<Coord> coords = new ArrayList<Coord>();
		//Queue of tiles that need to be checked.
		Queue<Coord> queue = new LinkedList<Coord>();
		
		//Starting tile is added to the queue.
		queue.add(new Coord(xa, ya));
		
		//While there is something in the queue, do some checks.
		while(!queue.isEmpty()){
			Coord c = queue.remove();
			//Check bounds of coords.
			if(c.x >= 0 && c.x < width && c.y >= 0 && c.y < height){
				//If coord that is being checked is a land tile and isn't already owned. Add it to the owned list.
				if(tileId[c.x][c.y] == 0 && !coords.contains(c)) coords.add(new Coord(c.x, c.y));
				//Add surrounding tiles to the checking queue.
				if(tileId[c.x - 1][c.y] == 0) queue.add(new Coord(c.x - 1, c.y));
				if(tileId[c.x + 1][c.y] == 0) queue.add(new Coord(c.x + 1, c.y));
				if(tileId[c.x][c.y - 1] == 0) queue.add(new Coord(c.x, c.y - 1));
				if(tileId[c.x][c.y + 1] == 0) queue.add(new Coord(c.x, c.y + 1));
			}
		}
		
		//Return the final list of owned tiles.
		return coords;
	}

I would then check the List for the size of their List to decide if they are too small or not.

My problem with this is that the while loop does not stop, it just keeps going. Both the coords and the queue array size increases massively.

#18

Try this:


if(c.x >= 0 && c.x < width && c.y >= 0 && c.y < height){
    //If coord that is being checked is a land tile and isn't already owned. Add it to the owned list.
    if(tileId[c.x][c.y] == 0 && !coords.contains(c)) 
@@    {
        coords.add(new Coord(c.x, c.y));
        //Add surrounding tiles to the checking queue.
        if(tileId[c.x - 1][c.y] == 0) queue.add(new Coord(c.x - 1, c.y));
        if(tileId[c.x + 1][c.y] == 0) queue.add(new Coord(c.x + 1, c.y));
        if(tileId[c.x][c.y - 1] == 0) queue.add(new Coord(c.x, c.y - 1));
        if(tileId[c.x][c.y + 1] == 0) queue.add(new Coord(c.x, c.y + 1));
@@    }
}
#19

Just gave that a go but I still get the same results. I just checked the size of the Lists near the end of the loop and after a few seconds running find that the coords list is 296,489 and queue is 808,075.

#20

Derp, make sure you implement public boolean equals(Coord c) in class Coord. Look at awt.Point if you don’t know how.
Without it, list.contains returns false every time. (Since you are only filling it with new objects, no two objects will compare as equal, even if they have the same coords!)

(This is why I advise using provided classes where possible, to minimize the change of doing something wrong)