Jump to content
  • Advertisement
Crayz92

Filling a rectangle with randomly chosen rectangles of specific size?

This topic is 392 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

The size of my root rectangle will be power of 2 and the size of the children rectangles will always be divisible by 4.

Say I have a rectangle of size 128x128, is there an algorithm that can fill it with rectangles who's size is randomly chosen from an array (i.e. [(8, 8), (8, 16), (16, 16), (16, 24), (24, 24)]).  There should be no gaps

My first attempt involved splitting the root rectangle recursively, but this result is uniform to a grid and won't work:

4d810bc144.png

 

I need it to look more like this:

556e838f0f.png

Share this post


Link to post
Share on other sites
Advertisement

I don't know any algorithm, but my first thought is to start with the entire rectangle, and repeatedly split one rectangle in two, with a direction (horizontal / vertical), and an offset from eg top-left corner.

You can play with several parameters, like throwing smaller rectangles out, or give priority to larger rectangles, or cut the longest direction. Hopefully you'll find a setup that gives nice results.

Share this post


Link to post
Share on other sites

My first thoughts were opposite to Alberth's idea. Note that this is all untested.

 

Fill a grid cells that are all the same size (smallest size wanted). In your example image, it looks like there could be 8x8.

Randomly select a cell, and merge it with an adjacent cell if the dimensions match.

 

Alternatively, mark all cells as unused. Then select x of them and give their own identifier. Grow them to merge with adjacent cells if they are unused.

At the end loop over and deal with e.g. non-rectangles and any potential other cases.

Share this post


Link to post
Share on other sites

Offsetting improved the result though I think I'm going about it wrong with splitting as it always results in seams which are separating areas from the rest

 

I'm gonna give Lactose's idea a try now and see how it works out :)

 

Edit: Final result:

271c0c8417.png

 

I can work with this.  Thanks for the ideas :)

Edited by Crayz92

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!