Divide grid (2D array) into random shaped parts?

Question

The Problem
I want to divide a grid (2D array) into random shaped parts (think earth's tectonic plates).

Criteria are:

• User inputs grid size (program should scale because this could be very large).
• User inputs grid division factor (how many parts).
• Grid is a rectangular shaped hex grid, and is capped top and bottom, wrap around left and right.
• No fragmentation of the parts.
• No parts inside other parts.
• No tiny or super-large parts.
• Random shaped parts, that are not perfect circles, or strung-out snaking shapes.

My solution:

• Create a method that can access/manipulate adjacent cells.
• Randomly determine the size of each part (the sum of all the parts equal the size of the whole 2D array).
• Fill the entire 2D array with the last part's id number.
• For each part except the last:
• Seed the current part id number in a random cell of the 2D array.
• Iterate over the entire array and store the address of each cell adjacent to any cells already seeded with the current part id number.
• Extract one of the stored addresses and fill that cell with the current plate id number (and so the part starts to form).
• Repeat until the part size is reached.

Note that to avoid parts with long strung out "arms" or big holes inside them, I created two storage arrays: one for cells adjacent to just one cell with the current part id number, and the other for cells adjacent to more than one, then I exhaust the latter before the former.

Running my solution gives the following:
Grid size: 200
width: 20
height: 10
Parts: 7

66633333111114444466
00033331111114444466
00003331111114444466
00003331111144444660
00000333111164444660
00000336111664422600
00000336615522222200
00006655555522222200
00006655555552222220
00066655555552222220

Part number: 0
Part size: 47

Part number: 1
Part size: 30

Part number: 2
Part size: 26

Part number: 3
Part size: 22

Part number: 4
Part size: 26

Part number: 5
Part size: 22

Part number: 6
Part size: 27

Problems with my solution:

• The last part is always fragmented - in the case above there are three separate groups of sixes.
• The algorithm will stall when parts form in cul-de-sacs and don't have room to grow to their full size (the algorithm does not allow forming parts over other parts, unless it's the last part, which is layed down over the entire 2D array at the start).
• If I don't specify the part sizes before forming the 2d array, and just make do with specifying the number of parts and randomly generating the part sizes on the fly, this leaves open the possibility of tiny parts being formed, that might aswell not be there at all, especially when the 2D array is very large. My current part size method limits the parts sizes to between 10% and 40% of the total size of the 2D array. I may be okay with not specifying the parts sizes if there is some super-elegant way to do this - the only control the user will have is 2d array size and number of parts.

Other ideas:

• Form the parts in perfectly aligned squares, then run over the 2D array and randomly allow each part to encroach on other parts, warping them into random shapes.
• Draw snaking lines across the grid and fill in the spaces created, maybe using some math like this: http://mathworld.wolfram.com/PlaneDivisionbyLines.html

Conclusion:
So here's the rub: I am a beginner programmer who is unsure if I'm tackling this problem in the right way. I can create some more "patch up" methods, that shift the fragmented parts together, and allow forming parts to "jump out" of the cul-de-sacs if they get stuck in them, but it feels messy.

How would you approach this problem? Is there some sexy math I could use to simplify things perhaps?

Thx

Answer 1

Here's what I'd do: use Voronoi algorithm. At first place some random points, then let the Voronoi algorithm generate the parts. To get the idea how it looks like consult: this applet.

Answer 2

I did something similar for a game a few months back, though it was a rectangular grid rather than a hex grid. Still, the theory is the same, and it came up with nice contiguous areas of roughly equal size -- some were larger, some were smaller, but none were too small or too large. YMMV.

1. Make an array of pointers to all the spaces in your grid. Shuffle the array.
2. Assign the first N of them IDs -- 1, 2, 3, etc.
3. Until the array points to no spaces that do not have IDs,
4. Iterate through the array looking for spaces that do not have IDs
5. If the space has neighbors in the grid that DO have IDs, assign the space the ID from a weighted random selection of the IDs of its neighbors.
6. If it doesn't have neighbors with IDs, skip to the next.
7. Once there are no non-empty spaces, you have your map with sufficiently blobby areas.

Answer 3

As Rekin suggested, a Voronoi diagram plus some random perturbation will generally do a good job, and on a discretized space like you've got, is relatively easy to implement.

I just wanted to give some ideas about how to do the random perturbation. If you do it at the final resolution, then it's either going to take a very long time, or be pretty minimal. You might try doing a multi-resolution perturbation. So, start with a rather small grid, randomly seed, compute the Voronoi diagram. Then randomly perturb the borders - something like, for each pair of adjacent cells with different regions, push the region one way or the other. You might need to run a post-process to make sure you have no tiny islands.. a simple floodfill will work.

Then create a grid that's twice the size (in each direction), and copy your regions over. You can probably use nearest neighbor. Then perturb the borders again, and repeat until you reach your desired resolution.