# Axis Aligned Spatial Division : Divide space into random rectangles?

I need a method to divide 3d space into random axis aligned box shapes. For now I am currently dividing the 2d space for testing purposes. The most immediate approach I came up with was to define a rectangle of size (1, 1) and then recursively split all existing rectangles to two uneven rectangles alternating between axis X and Y.

The problem here is obvious. This approach results in long stretching lines (marked in red)

What I would like is something more organic looking (I included an example)

See, no long straight lines from top to bottom or left to right.

The only constraint is that I may wish to limit the minimal size of the rectangle without affecting the granularity of the sizes. i.e. if the smallest rect is 1 square centimeters than the seconds smallest room should not be 2 square units.

So ideally the algorithm should meet all three following constraints:

1. Rectangles are not infinitesimally small.
2. Rect sizes aren't discrete multiplication of the smallest rect size. i.e. if the smallest rect is 3 square unit than larger rects are not constrained to be 6, 9, 12 and so forth square units and instead could be 3.2 or 4.7 for that matter).
3. The algorithm runs in polynomial time (needs to compute fast).

The approach you outline is simple and useful, but suffers from terrible artifacts as shown. Avoid it. You need a parallel growth algorithm; for a single-threaded model, a round-robin approach follows:

1. Randomly place various points in your map space. Normalise their distribution (avoids ugly clustering) using Gaussian distribution or by applying an iterative relaxation algorithm to move randomly placed points away from one another, as per Lloyd relaxation for Voronoi Diagrams. These points represent the centroids of your rooms-to-be.
2. (Parallel / Repeat round-robin for all rooms) From each point, grow 4 vertices outward (a rectangular room), moving from the centre point per global iteration (you can grow different rooms at different rates in each axis rather than the same for all, and see how this turns out -- possibly for a more organic / varied result). At some point, some of your rectangles will begin to press against each other. At that point, limit growth in that axis, ensure the two rooms' adjacent edges are exactly touching, and move on.
3. Repeat step 2, growing every room incrementally, till all growth is restricted by adjacent rooms or the bounds of the map.
4. This will still leave some empty spaces. The problem now becomes one of locating and making rooms out of non-occupied spaces. In fact, if your underlying space is a (integer-indexed) grid (and every growth iteration snaps to that grid), then this is much easier to deal with, since you can maintain lists of occupied and unoccupied grid cells: Once you've placed and grown all your rooms, search through the unoccupied list for discrete spaces consisting of groups of adjacent cells. As many unused spaces will have non-rectangular shapes, you'll need to pick a cell at random from within that non-rectangular space, and grow it to its maximal size just as you did with rooms in step 2. Repeat within said non-rectangular space, till it is completely filled.
5. Repeat step 4 till your map is 100% occupied.
• This is good advice. The disadvantage is that it possibly doesn't do anything to protect me from infinitesimally small rects. I need some manner to limit how small and how big rects are. Currently I am in the process of working on another method. I will compare the results and update. Commented May 12, 2014 at 8:57
• @ArthurWulfWhite Then your question was under-specified and should be updated. Your minimum room size is determined by your map-cell resolution; so if you make that coarse-grained enough to accommodate the minimum room size, you can thereafter adjust axes on a floating-point basis, returning a more organic look. Commented May 12, 2014 at 9:13
• You are correct! I thought I wrote that part. But I haven't. I apologize for this mistake. Yes I'm aware of the grid size. A room can only be as small as the grid allows. Commented May 12, 2014 at 9:25
• OK -- hope you find a suitable solution. BTW I meant "adjust grid-lines", not "adjust axes". Commented May 12, 2014 at 9:36
• Actually I am doing something exactly like that loosely based on the concepts you thought me. I will post the results here as well. Commented May 12, 2014 at 9:43

As you can see, I managed to rid the world of these artifacts. The idea is very similar.

1. Divide the 2d space into a non-uniform grid. If two lines are too close, remove one.
2. Pick a rectangle in random, check if it's been modified across axis-y (in height) and if it's direct neighbor was modified across axis-y. I both were not modified, have them renegotiate the segment between them (one will donate some space to the other).
3. Do the same as in step 2 only this time on the other axis.
4. Repeat the process until you modified as many as possible.

Non-uniform grid (1):

Negotiating on axis x (2):

Negotiating on axis y (3):

Result (4) :

• This was loosely inspired by the insight from @Nick Wiggill Commented May 12, 2014 at 13:04
• One could further improve on this by first randomly merging groups of n*m adjacent cells into a single rectangle. This masks the underlying grid still visible in the output above. Negotiation with these larger rectangles now has to work on all cells along one of its edges. Commented May 12, 2014 at 15:09
• OK. Still a great many colinear boundaries, I'd work on those further, but good that you've found your solution! Glad to assist. Commented May 12, 2014 at 15:21
• @DMGregory I considered this but I wanted the ratio between the small rects and the large rects to be consistent somewhat. If this was a texture or a level I would definitely do it (Actually have a previous example that does that). Commented May 12, 2014 at 17:16
• @NickWiggill I can completely eliminate the colinear lines. It is just a matter of tweaking the algorithm. There must be a way to improve it further (update with most recent variation) Commented May 12, 2014 at 18:07