Sign in to follow this  
Kris_A

Randomly arranging blocks

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this