Procedurally generating a building of specific area

Question

Myself and a team are working on a factory builder game that gives the player a random factory at the start of the game. To try to make sure there is a sense of "fairness," ideally the randomly generated factory would have an area within a few units of (placeholder value) 30.

Its relatively simple to write a basic random rectangle generator to meet these specifications, but our goal is for the factory to be more complex, perhaps made up of 2, 3, or even 4 intersecting rectangles, producing more complex shapes (think of L, U, and O shaped buildings).

I've tried generating a random rectangle and then using basic algebra to fill in a 2nd rectangle, but so far I've had no luck implementing more than 2 rectangles, and even then I am unhappy with the results for just a 2 rectangle design.

Some more relevant info: 2D top down Some of the mechanics are factorio style so rooms should have reasonable length and width to allow room for machinery Currently in Java and Lua (can use built in libraries from either if needed)

Thanks in advance!

EDIT: When I say "good" or "bad" outputs, a bad output would be any output which has space unusable by the player. The factory shape limits where the player can place factory machines such as conveyor belts. Ideally, the factory shouldn't have areas that are only 1-2 blocks wide, the shape shouldn't be one or two big rectangles with a line of 1-2 blocks "hanging" out to one side. A good output would be where all floor space is "workable", so all areas are at least 3-4 blocks wide. A good output doesn't always have to be complex (1 or 2 rectangles is okay), but it should have a fair chance if being made up of more than 1-2 rectangles.

Answer 1

You could use pre-generated polyominoes as meta shapes to build an assortment of buildings.

Let's say your minimum acceptable distance is 3 blocks. Then the smallest acceptable building unit we'll consider is 3x3. For convenience, I'm going to call that a cell & it gives an area of 9 blocks. Next, take your target starting area & divide it by the cell area. Using the starting value you gave, we get 3.333; so 3 cells would give you a bit less than you want & 4 cells would give you more.

From here you have a couple of options. If you're flexible on your starting area, use whatever method works best for you to pick the number of cells that gives you an acceptable amount (i.e. round to the nearest value, round up, etc). I'm going to call this the cell count.

Next, randomly select the polyomino with the desired cell count. Replace each square on the polyomino with a building cell & you have your final shape.

To illustrate, say we choose to round down. Here are all the size 3 polyominoes (not including rotations / flips):

Let's assume we randomly pick the L shape & apply a random rotation, your building would have the following layout:

A couple of issues. First, there's a limit on the number of cells you can use. Wikipedia will give you all polyominoes up to size 8 (octomino). It includes summary data for up to size 12, but I don't know if there's an online listing for all them. Second, the solution above only works exactly for building sizes that are multiples of 9. There are a couple of ways to work around some of these issues:

1) Use a different cell size. For instance 3x4, 4x4, etc.

2) Add additional cells to a starting polyomino. This can be tricky if you must ensure all shapes are equally likely, but chances are for most game dev purposes you don't need a truly uniform distribution of building shapes.

3) Pad out out a building to make it bigger. Going back to the example, if you used 3 cells, your building would have an area of 27 squares leaving you short by 3. You could then scan the perimeter for a location to glue a size 1x3 group of squares. As long as your makeup group is at least AxB where A is at least your minimum acceptable distance, your result will not violate your minimum acceptable distance constraint. Building off the example above, here's an illustration of a possible result:

4) Instead of padding out a building that's too small, you could trim down a building that's too large. Ensuring that your minimum acceptable distance constraint is followed is more complex than the padding option, but would give you more alternatives to consider.

Some other comments:

Just because you could use all possible polyominoes of a given size doesn't mean you should. If some of them aren't fun, break your theme, are offensive to your audience (swastika patterns), or cause some other problem, take them out. Also, you could weight your selection routine if some patterns are interesting, but too weird to routinely pop up. Finally, you could use this solution in combination with your current strategy. Maybe 70% of the time you generate rectangular buildings & 30% of the time you use the polyomino approach. Or maybe you start with a rectangular building & glue a small polyomino to the outside.

Answer 2

A simple way to build a procedural generator is:

1. Randomly build things
2. Run a function that checks whether the output is good
3. If the output is not good, go to step 1

Even if it takes thousands of runs to complete, most simple generators get by just fine with this approach. The advantage is that there's not a lot of smarts required in the generator, and since checking whether something's good is much easier than building something that is good 100% of the time, this approach is very easy.

You've listed some objective measures on whether an output is good; that should be enough for you to create a quick and dirty generator. Place rectangles at random inside an area, and reject the output if, for example, there are areas that are only 1-2 blocks wide.

Start with that, improve and optimise afterward.

Answer 3

Given a restriction of "all areas are at are at least 3-4 blocks wide" the first idea that leaps to my mind is something like the following:

1. pick one of 3x3, 3x4, 4x3 or 4x4
2. place a block of that size in the center of the grid
3. pick a direction (up, left, right, down)
4. try to place a 3x3 block alongside previously placed blocks in that direction
5. if successful, with some probability, try to expand the block to a 4x3 block in one of the directions you didn't just pick
6. with some probability, move a to random edge of the filled in blocks
7. repeat steps 3 to 6 until the area is large enough

The basic idea is, given you want all areas to have at least a given size, only work in areas that are that size. More generally, if you want something to be true of all generated outputs, see if it can be made true of all partially generated outputs.

Answer 4

Consider using booleans NOT and UNION and choosing between them randomly.

1. Place a random rectangle.
2. Place a second random rectangle.
3. Randomly choose whether to UNION them or SUBTRACT the second from the first.
4. Repeat for a number of rectangles. Although, only two or three might give reasonable enough results.

Then, I would calculate the area and scale it up or down to more closely match the approximate size you seek, and then test that there are no dimensions less than a required minimum amount.