Jump to content
  • Advertisement
Sign in to follow this  
HellRaiZer

Tetris packing with complex shapes

This topic is 4401 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 problem and i don't know how to search for a possible answer. I have an infinite number of things with this shape: Tetris Block and an empty 2D lattice. I want to fill this lattice with as much of these things as i can, thus minimizing the free space in the lattice. Any object can be rotated +-90 degrees. Because of the shape is symmetric in both x and y axis, only one rotation makes sense. Every colored square in the shape has exactly the same dimensions as the others. This looks a lot like Tetris, but with more complex shapes. I tried to search how this can be done, but i haven't found something useful (a paper, an algorithm). Does somebody have any suggestions/papers on that? Any keywords for searching on Google? Anything? As you can figure out, packing multiple objects like the above, always leave some empty space. This is because you can't have one object perfectly fit inside the other. There will always be some empty cells, left and right of the blue cells. Knowing this, is there any way i can calculate the minimum empty space that can be formed inside an arbitrary lattice? Thanks in advance. And if you have any questions, please ask. HellRaiZer

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by lima
is this a homework assignment?

No. I have stopped doing any homework 1.5 years ago (when i graduated from uni) :)

After all i'm not asking for the solution. I'm asking for directions/suggestions/etc. Something to read on the subject. I don't even know if this is possible, so i'm searching. Don't you think that if this was homework, i would already have something to start searching?

Do you have any info on that?

HellRaiZer

Share this post


Link to post
Share on other sites
Quote:
Original post by HellRaiZer
After all i'm not asking for the solution. I'm asking for directions/suggestions/etc. Something to read on the subject. I don't even know if this is possible, so i'm searching. Don't you think that if this was homework, i would already have something to start searching?
Do you have any info on that?


Look for the algorithm called 'back tracking'...

Share this post


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

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