• Advertisement
Sign in to follow this  

Randomly arranging blocks

This topic is 4493 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

Hi, I have a 10x10 array, that's filled with blocks of various sizes and shapes. Image I'm after a way of arranging the blocks randomly, making sure that they all fit in one way or another. Is there any famous algorithm that will help me do this, or will I have to use brute force? If so, what's the best way to approach it? Thanks, Kris PS: The grey blocks represent free slots, which won't exist in 99% of cases. It's going to be a tight fit! PPS: This won't be done in real-time, so speed isn't a major issue

Share this post


Link to post
Share on other sites
Advertisement
This is known as the "2-D Bin-Packing Problem". There's a huge number of famous algorithms, all sub-optimal. The problem is NP-complete, which is to say it gets really hard really fast as the number of blocks increases. It's also a very important problem to the VLSI-CAD industry, so much journal ink has been spilled over it. A google search for "2-D Bin-Packing Problem" should tell you more than you ever wanted to know.

Share this post


Link to post
Share on other sites
That's a great help, thanks both. I know what to search for on Wikipedia now...!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement