Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Island Counting: Flood Fill vs Hash Deduping
package scratch;
import java.util.*;
public class islands {
public static void main(String args[]){
boolean map[][] = generateIslands(180, 50, new Random(287), 25, 15, .3);
System.out.println(drawMap(map));
System.out.println("Flood count:" + floodCount(map));
System.out.println("Hash Count:" + hashCount(map));
int amount = 5000;
boolean maps[][][] = new boolean[amount][][];
System.out.println("Generating " + amount +" maps for speed test...");
for(int seed = 0; seed < amount; seed++){
maps[seed] = generateIslands(180, 50, new Random(seed), 25, 15, .3);
}
System.out.println("testing flood...");
long flood_start = System.nanoTime();
int flood_result[] = new int[amount];
for(int seed = 0; seed < amount; seed++){
flood_result[seed] = floodCount(maps[seed]);
flood_result[seed] = floodCount(maps[seed]);
flood_result[seed] = floodCount(maps[seed]);
}
long flood_end = System.nanoTime();
System.out.println("testing hash dedupe...");
long hash_start = System.nanoTime();
int hash_result[] = new int[amount];
for(int seed = 0; seed < amount; seed++){
hash_result[seed] = hashCount(maps[seed]);
hash_result[seed] = hashCount(maps[seed]);
hash_result[seed] = hashCount(maps[seed]);
}
long hash_end = System.nanoTime();
int same_result = 0 ;
for(int k=0;k<amount;k++){
if(hash_result[k] == flood_result[k]){
same_result++;
}else{
System.out.println("mismatch seed:" + k + " flood:" + flood_result[k] +" hash:" + hash_result[k]);
}
}
System.out.println("Matching results:" + same_result +"/" + amount);
System.out.println("Flood time:" + (flood_end-flood_start));
System.out.println("Hash time:" + (hash_end-hash_start));
System.out.println("Hashing speed up:" + (flood_end-flood_start)/(double)(hash_end-hash_start));
}
// Flood fills when hits new land. Counts number of floods.
public static int floodCount(boolean map[][]){
boolean checked[][] = new boolean[map.length][map[0].length];
int count = 0 ;
for(int x = 0; x < map.length; x++){
for(int y = 0; y < map[x].length; y++){
if(map[x][y] && !checked[x][y]){
count++;
Queue<Point> queue = new LinkedList<Point>();
queue.add(new Point(x,y));
checked[x][y] = true;
while(!queue.isEmpty()){
Point p = queue.poll();
if(p.x > 0 && !checked[p.x-1][p.y] && map[p.x-1][p.y]){
checked[p.x-1][p.y] = true;
queue.add(new Point(p.x-1,p.y));
}
if(p.y > 0 && !checked[p.x][p.y-1] && map[p.x][p.y-1]){
checked[p.x][p.y-1] = true;
queue.add(new Point(p.x,p.y-1));
}
if(p.x+1 < map.length && !checked[p.x+1][p.y] && map[p.x+1][p.y]){
checked[p.x+1][p.y] = true;
queue.add(new Point(p.x+1,p.y));
}
if(p.y+1 < map[p.x].length && !checked[p.x][p.y+1] && map[p.x][p.y+1]){
checked[p.x][p.y+1] = true;
queue.add(new Point(p.x,p.y+1));
}
}
}
}
}
return count;
}
// Marks simply connected regions with numbers and maintains a table of numbers that mpa to the same island.
public static int hashCount(boolean map[][]){
int label[][] = new int[map.length][map[0].length];
int count = 0 ;
Hashtable<Integer,Integer> dupes = new Hashtable<Integer,Integer>();
for(int x = 0; x < map.length; x++){
for(int y = 0; y < map[x].length; y++){
if(map[x][y]){
boolean has_left = x > 0 && map[x-1][y] ;
boolean has_up = y > 0 && map[x][y-1] ;
if(has_left && has_up && label[x][y-1] != label[x-1][y]){
int left = label[x-1][y];
int up = label[x][y-1];
while(dupes.containsKey(left)){
left = dupes.get(left);
}
while(dupes.containsKey(up)){
up = dupes.get(up);
}
if(up!=left){
int min = Math.min(up, left);
int max = Math.max(up, left);
dupes.put(max,min);
label[x][y] = min;
}else{
label[x][y] = up;
}
}else if(has_up){
label[x][y] = label[x][y-1];
}else if(has_left){
label[x][y] = label[x-1][y];
}else{
count++;
label[x][y] = count;
}
}
}
}
return count - dupes.size();
}
// Generates a random continent-like island arrangement.
public static boolean[][] generateIslands(int width, int height, Random rand, int seeds, int expand, double chance){
boolean map[][] = new boolean[width][height];
for(int k = 0;k < seeds; k++){
int x = rand.nextInt(width);
int y = rand.nextInt(height);
map[x][y] = true;
}
for(int k=0;k<expand;k++){
map = expand(map, rand, chance);
}
return map;
}
// Expand land for generating simply continuous regions.
public static boolean[][] expand(boolean map[][]){
boolean new_map[][] = new boolean[map.length][map[0].length];
for(int x = 0; x < map.length; x++){
for(int y = 0; y < map[x].length; y++){
new_map[x][y] = map[x][y]
|| (x+1 < map.length && map[x+1][y])
|| (x-1 >= 0 && map[x-1][y])
|| (y+1 < map[x].length && map[x][y+1])
|| (y-1 >= 0 && map[x][y-1]);
}
}
return new_map;
}
// Probabilistically add land near existing land.
// Used for generating interesting continuous island regions.
public static boolean[][] expand(boolean map[][], Random rand, double chance){
boolean new_map[][] = new boolean[map.length][map[0].length];
for(int x = 0; x < map.length; x++){
for(int y = 0; y < map[x].length; y++){
new_map[x][y] = map[x][y]
|| (x+1 < map.length && map[x+1][y] && rand.nextDouble() < chance)
|| (x-1 >= 0 && map[x-1][y] && rand.nextDouble() < chance)
|| (y+1 < map[x].length && map[x][y+1] && rand.nextDouble() < chance)
|| (y-1 >= 0 && map[x][y-1] && rand.nextDouble() < chance);
}
}
return new_map;
}
// Draw an island map.
public static String drawMap(boolean map[][]){
String map_string = "";
for(int y = 0; y < map[0].length; y++){
String row_string = y == 0 ? "" : "\n";
for(int x = 0; x < map.length; x++){
if(map[x][y]){
row_string+="O";
}else{
row_string+="-";
}
}
map_string += row_string;
}
return map_string;
}
// Draws a map of integers by mapping to individual characters.
public static String drawMap(int map[][]){
String map_string = "";
char[] alphabet = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()~".toCharArray();
for(int y = 0; y < map[0].length; y++){
String row_string = y == 0 ? "" : "\n";
for(int x = 0; x < map.length; x++){
row_string+=alphabet[map[x][y]%alphabet.length];
}
map_string += row_string;
}
return map_string;
}
// Used for debugging hash fill.
public static String drawMap(int map[][], Hashtable<Integer,Integer> dupes){
String map_string = "";
char[] alphabet = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()~".toCharArray();
//Collapse dupe table.
Enumeration<Integer> a = dupes.keys();
while(a.hasMoreElements()){
int key = a.nextElement();
int value = dupes.get(key);
while(dupes.containsKey(value)){
value = dupes.get(value);
}
dupes.put(key,value);
}
for(int y = 0; y < map[0].length; y++){
String row_string = y == 0 ? "" : "\n";
for(int x = 0; x < map.length; x++){
if(dupes.containsKey(map[x][y])){
map[x][y] = dupes.get(map[x][y]);
}
row_string+=alphabet[map[x][y]%alphabet.length];
}
map_string += row_string;
}
return map_string;
}
// Used for queue locations in flodd fill.
static class Point{
public int x, y;
public Point(int x, int y){
this.x = x;
this.y = y ;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.