Instead of iterating over all plates, consider only those empty cells that could possibly be filled: namely those that are adjacent to at least one already filled cell.
Your algorithm could then become something like this:
1) Keep track of all unfilled cells that have at least one adjacent filled cell.
2) Select one of these unfilled cells.
3) Select one plate from all plates adjacent to the cell.
4) Make the cell part of the plate.
5) Check the cells surrounding the newly filled cell: add those that don't belong
to a plate yet to your data structure (if they haven't been added before).
This way, your runtime is O(w*h)
but the operations inside the loop are quite cheap. In practice, the following Java implementation has no trouble generating a 500 by 500 grid:
import java.util.Random;
// for displaying
import java.awt.Color;
import java.awt.image.BufferedImage;
import javax.swing.ImageIcon;
import javax.swing.JLabel;
import javax.swing.JOptionPane;
public class OrganicFill {
private int width;
private int height;
private int[][] grid;
private int numPlates;
private Random random = new Random();
public OrganicFill(int width, int height, int numPlates) {
this.width = width;
this.height = height;
this.grid = new int[width][height];
this.numPlates = numPlates;
}
public void fill() {
// auxiliary data structures for potential occupants of a cell
boolean[][] claimed = new boolean[width][height];
int[] cells = new int[width * height - numPlates]; // fixme: too much
int numEmptyCells = 0;
// select random starting points for all plates
for (int plate = 1; plate <= numPlates; plate++) {
int x = random.nextInt(width);
int y = random.nextInt(height);
// make sure this cell is unoccupied
while (grid[x][y] != 0) {
x = random.nextInt(width);
y = random.nextInt(height);
}
numEmptyCells = setCell(x, y, plate, cells, numEmptyCells, claimed);
claimed[x][y] = true;
}
// fill the rest of the grid
while (numEmptyCells > 0) {
int index = random.nextInt(numEmptyCells);
// remove the selected cell from the list
int cell = cells[index];
cells[index] = cells[--numEmptyCells];
int x = cell % width;
int y = cell / width;
int plate = selectPlate(cells, x, y);
numEmptyCells = setCell(x, y, plate, cells, numEmptyCells, claimed);
}
}
private int setCell(int x, int y, int plate, int[] cells, int cellsIndex, boolean[][] claimed) {
assert plate > 0 && plate <= numPlates;
grid[x][y] = plate;
int left = (x == 0 ? width - 1 : x - 1);
int right = (x == width - 1 ? 0 : x + 1);
int up = (y == 0 ? height - 1 : y - 1);
int down = (y == height - 1 ? 0 : y + 1);
if (!claimed[left][y]) {
cells[cellsIndex++] = left + y * width;
claimed[left][y] = true;
}
if (!claimed[right][y]) {
cells[cellsIndex++] = right + y * width;
claimed[right][y] = true;
}
if (!claimed[x][up]) {
cells[cellsIndex++] = x + up * width;
claimed[x][up] = true;
}
if (!claimed[x][down]) {
cells[cellsIndex++] = x + down * width;
claimed[x][down] = true;
}
return cellsIndex;
}
private int selectPlate(int[] cells, int x, int y) {
// find all adjacent plates
int left = (x == 0 ? width - 1: x - 1);
int right = (x == width - 1 ? 0 : x + 1);
int up = (y == 0 ? height - 1 : y - 1);
int down = (y == height - 1 ? 0 : y + 1);
final int plates[] = new int[4];
int count = 0;
if (grid[left][y] != 0) plates[count++] = grid[left][y];
if (grid[right][y] != 0) plates[count++] = grid[right][y];
if (grid[x][up] != 0) plates[count++] = grid[x][up];
if (grid[x][down] != 0) plates[count++] = grid[x][down];
// select on of the adjacent plates at random
return plates[random.nextInt(count)];
}
public static void main(String[] args) throws Exception {
if (args.length != 3) {
System.err.println("USAGE: java ..OrganicFill <width> <height> <number-of-plates>");
System.exit(1);
}
int width = Integer.parseInt(args[0]);
int height = Integer.parseInt(args[1]);
int numPlates = Integer.parseInt(args[2]);
OrganicFill main = new OrganicFill(width, height, numPlates);
main.fill();
Random random = new Random(0);
int[] colors = new int[numPlates];
for (int i = 0; i < numPlates; i++) {
colors[i] = random.nextInt(0xFFFFFF);
}
BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
int color = main.grid[x][y] > 0 ? colors[main.grid[x][y] - 1] : 0;
image.setRGB(x, y, color);
}
}
JLabel map = new JLabel(new ImageIcon(image.getScaledInstance(500, 500, image.SCALE_FAST)));
JOptionPane.showMessageDialog(null, map);
}
}
Here, I'm using a second grid (claimed
) and an array (cells
) in which I keep track of all cells that have at least one adjacent plate. The cells
array basically functions as a list for all such cells from which the next cell to assign is selected at random. The claimed
array allows for fast checking of whether a cell has already been added to cells
or not.
The main loop is in fill
: first, some random starting points are determined for each plate. Then a loop fills all remaining cells of the grid.
The real smarts is in setCell
: this method does not only update the grid itself, but also the "claims" array for the cells immediately above, below, left of and right of the given cell.
A third method selectCell
randomly selects for a given cell one of the plates that made a claim for that cell.
EDIT:
500x500 with 10 plates in 33ms
EDIT2:
500x500 with 10 plates in 19ms with updated code