15
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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):

enter image description here

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

enter image description here

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:

enter image description here

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.

\$\endgroup\$
16
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you! I remember considering this, but the thought of there being a chance for a several second+ load time stopped me. I now realize how incredibly small that chance is. I'll have to try that out, but I might wait to see if someone has a more direct solution first. \$\endgroup\$ – user2129189 Aug 23 '17 at 7:16
  • \$\begingroup\$ @user2129189 When you got your generator running, you can still tweak its random number ranges to avoid generating layouts which are unlikely to pass the test. Its also possible to parallelize this trial-and-error generation algorithm over multiple cores by having each core generate one layout at a time. \$\endgroup\$ – Philipp Aug 23 '17 at 8:04
  • 3
    \$\begingroup\$ Myself I'm not a fan of reject-and-retry generation methods. They're speedy enough when your generator is doing just one simple thing, but for game levels we usually start layering more features and generation steps to make richer maps. At that point, the probability of hitting a viable map is the product of the probability of each step succeeding, which can shrink rapidly. This isn't just an academic concern — I've talked with devs who had to implement a good/bad seed caching system to avoid excess generation times, when a correct-by-construction single pass generator would have been easier. \$\endgroup\$ – DMGregory Aug 23 '17 at 11:52
  • \$\begingroup\$ @DMGregory yeah I can definitely see that. A basic random generator would work like 99% of the time within a few passes for my case, but if I want to add more complexity later, it could slow down significantly. Anyone know of any real-life programming/game applications of the guess and check-like model? \$\endgroup\$ – user2129189 Aug 23 '17 at 16:05
  • \$\begingroup\$ Maybe there can be tiers of generations functions and checks, taking care to match the phrasing of the conditions to the current level of generation. That way, the entire level does not need to be re-generated whole just from the error found placing an item slightly incorrectly. \$\endgroup\$ – Pysis Aug 23 '17 at 19:57
7
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ I'd simplify things by always starting from a 3x3 block, then adding 3x1 blocks in random positions where each square is adjacent to an existing one. Adding to a 3x3 block, there are four possible positions. All give you a 3x4 block, with six possible positions for the next one. From there it gets more complicated, but not so bad. \$\endgroup\$ – JollyJoker Aug 23 '17 at 10:54
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Your scaling idea to get the desired area is actually quiet clever. I might implement something quiet a bit like this. \$\endgroup\$ – user2129189 Aug 23 '17 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.