# Algorithm for dividing a 2D grid into organic looking plates

the title pretty much says it all: How could one go about segmenting a 2D grid into smaller parts? My goal here is to create tectonic plates for further procedural world generation

Details to consider:

• The amount of parts should be controllable the resulting parts should
• look "organic", meaning somewhat irregular, but still clumpy
• the parts should wrap on the x and y axes

For now, I am using a random flood fill with as many starting points as I want plates.

Pseudocode would look a bit like this:

For 0 to plateAmount
create a random seeding point and store point in each plates list of points.

While empty points exist in the grid,
loop over each plate and add an adjacent, empty point to it.


This gives acceptable results, but takes very long! With 6 plates, a map of 100x100 tiles/points/cells takes 3 seconds, 200x200 takes 50 seconds, 500x500 takes forever. The more plates, the quicker it is.

Is there a quicker way to get a good result? Maybe something with Voronoi?

My result with 60x60 cells, 10 plates, each cell is 10x10 pixels. Ignore the "height" text, it displays not-yet-visualized data from the cell the mousecursor hovers over

You're on the right track. However...

Try

O(n*m) runtime is typical with something like this. Your implementation is a bit excessive, however. The real question is, What is making your O(n*m) algorithm take so long?

Why bother to run through every map cell for each influence? It would be faster to have each starting influence also specify some random maximum radius within which it could affect map cells. At the start, store the position of the influence AND it's radius. Then, for each "plate" (influence), attempt to write cell color only within that radius.

Cell-based Voronoi will similarly be O(n*m) if using a similarly naive approach, since you must run through all Voronoi centres for all map cells.

Catch

For the approach described above:

1. Radius-based distance checks use a square root which can be relatively costly; use either a radius look-up table to avoid square root calculations, or use rectangular [x,y] bounds range-check for early termination, only checking radius / sqrt once you fall within those [x,y] bounds.
2. Optimal average radius is going to be based on your average influence point spacing... this is something I leave for you to figure out, as it depends on how you have distributed your initial points.
3. Some empty cells will remain since radii will not cover all map cells. You can fill these out relatively cheaply in a final step, by taking the colour of a random, populated neighbour.

Finally...

(1) profile your code and (2) optimise:

• remove conditionals, the more deeply-nested they are the more impact this will have;
• pack your data tightly and in a cache-friendly fashion (anything from using simple sub-grids to a Hilbert curve or Z-curve).

Unfortunately, to get to closer to O(n), you would need a continuous function that creates distinct regions of adjacent, uniquely-coloured cells. If anyone knows of such an approach, I would love to hear about it, but I know of no such algorithm. There may be a way to adapt Perlin noise (continuous function) to do this, but not without a significant amount more effort and complexity. Usually, simplicity is best, so I suggest sticking with and optimising your current nested approach.

Vectorised (SIMD) and parallelised (multi-core) processing are also options if your language is sufficiently low-level or does these transparently. The only other thing I could suggest if you are using a higher-level langauge (e.g. HTML5 JS or Unity) is to write generation functions in a lower level language and tie them in as e.g. shared libraries to maximise performance in those critical sections.

• Really nice answer, thanks a bunch! The radius is a cool idea. ATM my plate seed coordinates are completely random without any relaxation, but that's just a placeholder anyways. Code optimization is what I thought of first, but then decided to ask here if my approach is worth optimizing in the first place. :) BTW. I use C#. I could go even "closer to the metal" but that'd feel like putting a stronger motor in my car because the axes are so rusty they won't move otherwise. I'd rather repair / switch axes. ;) May 19 '15 at 14:03
• @ChristianGeese You're welcome. I wasn't even sure what language you used so was not sure what could be suggested in terms of optimsation, though really the algorithmic approach is always best and applies anywhere. Glad it helped! May 19 '15 at 21:23

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

• Because repeating what I said an hour ago is useful. ;) May 19 '15 at 12:08
• Well, you beat me to it ;-) But apart from that, I think it's useful in that there's some sample code to look at. May 19 '15 at 12:11
• Hey, thanks! In retrospect, I should've been more verbose with my pseudocode, since I already do it the way you suggested. :D One little difference: Instead of 5), I check ALL cells belonging to a plate for empty neighbors right before I add a new one, because your way would lead (I think) to plates sometimes overwriting each others cells where two plates meet. I have gotten a new idea on how to tackle that, though!! May 19 '15 at 14:00
• @ChristianGeese - Filled cells should never be overwritten: the cells array contains a list of all unwritten cells and a cell is removed from that list as soon as it is assigned a plate. This way it can never be overwritten. But now I'm curious: you say you already implemented it this way, yet a 500x500 grid with 6 plates take "forever" -- the above code, however, can fill 500x500 with 10 plates in under a second on my machine?! May 19 '15 at 14:12
• I store plate-adjacent cells in a list belonging to the plate, that's probably the source of the "overwrite"-problem. My implementation is very close to your pseudocode, I guess I have made one or more hefty mistakes somewhere. Didn't get around to checking your real code YET! :) May 19 '15 at 14:23

Since you mention voronoi, i'll give my c# voronoi implementation

private void Voronoi(int[,] points, int minDelta)
{
for (int i = 0; i < wid; i++)
{
for (int j = 0; j < hei; j++)
{
float minDist = 999999999f;
float minDist2 = 999999999f;
float minV = 0f;
for (int p = 0; p < points.GetLength(0); p++)
{
int pX = points[p, 0];
int pY = points[p, 1];
float pV = (float)(points[p, 2])/255f; //0..1
Double Dist1X = Math.Abs((i - pX));
Double Dist1Y = Math.Abs((j - pY));
Double Dist2X = wid - Dist1X;
Double Dist2Y = hei - Dist1Y;
/*to grant seamless I take the min between distX and wid-distX
|                       |
|                       |     ----------- = Dist1X
|...i-----------X.......|     ..........  = Dist2X
|                       |
*/
Dist1X = Math.Min(Dist1X, Dist2X);
/*to grant seamless I take the min between distY and hei-distY*/
Dist1Y = Math.Min(Dist1Y, Dist2Y);
//euclidian metric
float dist = (float)Math.Sqrt(Dist1X * Dist1X + Dist1Y * Dist1Y);

// add pseudorandom perturbation to plates/cells
float a = (float)PerlinNoise2d(pX, pY, wid, hei, wid/4, hei/4, 0.5f, 1, 0.5f);
dist = dist * (a - 0.5f)*2;
if (dist <= minDist)
{
minDist2 = minDist;
minDist = dist;
minV = pV;
}
else
{
if (dist <= minDist2)
minDist2 = dist;
}
}

//store the i,j pixel value
setV(i, j, minV);
}
}
}


Where wid and hei are the map dimensions , setV() is the sets the pixel i,j at value minV, PerlinNoise2d is autoexplicative, but you can use any pseudo random generator (same coord same value)

Here a 256X256 example in 1.7 seconds

• That's very neat, thank you! Gotta wrap my head around your code for a bit now (I am not too clever :>) but the results + speed look great! May 19 '15 at 14:07