• ### What is your GameDev Story?

#### Archived

This topic is now archived and is closed to further replies.

# Algorithm to pack items into container

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

## Recommended Posts

Are there any popular algorithms that can be used to pack a number of items into a container. I need to fit a bunch of 2D rectangular objects into the smallest amount of space possible such that no object overlaps another object. The algorithm doesn''t need to be very fast. Any ideas or links? Thanks for your help.

##### Share on other sites
Are those rectangle allowed to rotate (by increment of 90°)Intuitively I would:

§I'll cal the space wher you must pack your rectangles the main area.

1 - sort all rectangles by decreasing surface/area.
2 - go through the list and try to pack the rectangles, favoriting main area edges

I'm also thinking of another method which could work even if it could be slow (not sure however):

Use genetic algorithm, I once found a GA demo demonstrating you're kind of problem.

In your case, the goal of the GA is to minimize the empty space in the container.

However, the fact that not all rectangles can fit in a single container could male that more complicate, I don't know ... investigate

I can't remember the link, maybe I found that on AIDepot ...

[edited by - bender77 on June 15, 2003 2:53:37 AM]

##### Share on other sites
Thanks for the idea, but I have been googling it. All I get are discussions about the various algorithms and heuristics, never the actual algorithms and heuristics themselves. Does anyone know the name of an algorithm or heuristic that solves the 2d bin packing problem?

##### Share on other sites
quote:
Original post by Bender77
Are those rectangle allowed to rotate (by increment of 90°)Intuitively I would:

no, they cannot.

quote:

In your case, the goal of the GA is to minimize the empty space in the container.

I found a lot of talk about GAs, too.

quote:

I can''t remember the link, maybe I found that on AIDepot ...

I''ll check it out, thanks.

##### Share on other sites
Alright, I can''t seem to find anything definitive on the web. Everything I read talks about the pros/cons of an algorithm or heuristic, but they never tell you what the actual steps are! So, I''ve devised my own based on something I think is called the "guillotine method" (I don''t know if that is write, but who really cares).

The algorithm goes something like this:

1) Sort rectangles into descending order by height
2) Place the rectangles into the container in a row
3) When you reach the end of the row, drop down to the next line and continue.
4) Repeat until you run out of rectangles.

This algorithm works very well since my rectangles are all very close in size. If you have a more varying array of sizes, this may not work so well. Anyway, unless someone comes along with a better solution, I think my question is answered and the problem is solved.

Here are some images that demonstrate how well this method works for my situation:

##### Share on other sites
The first few results from Googling for "texture packing" look pretty good to me.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 17
• 14
• 10
• 9
• 11
• ### Forum Statistics

• Total Topics
634094
• Total Posts
3015498
×