Putting items into a 3D space

Question

Imagine a fridge and a bunch of random foods. I want to take one food item, automatically put it somewhere in the fridge, and repeat. I can stop at any time.

Basically, the filled fridge should look like it has been gradually stocked over the course of a week or so (as opposed to deliberately organized at once) by a calm human being (as opposed to by someone who's just thrown things into it).

Formally, this procedure has to satisfy the following:

• Similar items should stack or be next to each other given that there is sufficient space (ex. egg cartons cases go in one stack, 2L milk cartons go side by side)
• Other items should not stack until there is no more space left at the bottom
• Placed items should be as upright as possible (ex. plastic-wrapped leftovers shouldn't be sideways), unless limited space requires rotation
• Items should be put somewhere in the center of the fridge when it is relatively empty (instead of being squished to one side)
• The procedure should automatically stop when the fridge no longer has any room left

Ignoring any dividing racks that may be present in the fridge (say it's just one big container), how should this be done? What variables would I need to define with an Item, and/or what algorithms should I use to determine where to put the next item and how to find out which angle of rotation will give me the fit?

Answer 1

This appears to be a "do my homework for me" type of question. There is no special algorithm or a clear answer. Still, it's a somewhat interesting piece of homework. :)

And since there is no special algorithm, I'd implement it using the equivalent of constraint relaxation in physics. All the things you have stated as requirements are rules, or constraints. Which basically means that you can insert any new item anywhere, and then adjust the positions of all items to fit the rules:

• Items too close to each other? Move them further apart.
• Eggs are placed near some milk cartons and now you've got no space for more milk? Swap them.
• Can't insert a new item because of lack of continuous space? Move other items closer together, trying to make space at the best-fit position first.

Just like in real life people have limited amount of time and interest to deal with their fridges, you can assign a cost to every action and use that to limit the number of actions to take.

The complexity of the simulation is very much up to you, though. I wouldn't go for packing algorithms for placement, at least not at first - moving things further apart or closer together is much easier to do on a straight line, followed by collision resolution of convex polygons. It's pretty much unnecessary for a tiled grid of the right size, so that's a good option as well.

The reason for me being against packing algorithms is that every one of them I've seen requires a complete repack of all items on any change, always tightly together, which I think you wanted to avoid. Since most packing algorithms tend to fill a side or two first, scaling the packed data to the full size for proper spacing probably won't work as well.

Answer 2

You might want to look into Packing Problems, specifically Bin Packing (google for more sources).

Angle of rotation is a little more difficult and the easiest you can do is to use an axis-aligned bounding box (AABB) to represent objects with non-axis-aligned orientations. These AABBs then are what you pack:

...which means things will look a little strange, with spaces between the objects (space between blue and red wireframes in diagram). For better accuracy than this, you'd have to use some sort of physics engine, place the object and let it settle according to it's actual shape and the shapes of its neighbours, and then lock the physics state to ensure no further perturbations - a lot of trouble but perhaps worth it for you. If you want accuracy, a physics engine is the only sane approach.

As for uprightness, placing near centre etc., it should become clear to you how to tackle those issues once you have basic bin packing working, which applies whether or not you use physics.