Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm wondering, are there any algorithms or theories in existence (that aren't patented/proprietary/protected) that would take a series of 3d rectangular prisms (or cubes but a cube is a prism) and stacks them in such a way as they form another cube or fit together in the best possible format?

I'm working on logistics software at work and this might be an interesting feature.

I'd also accept good articles that discuss the theory of this, if an algorithm isn't already available for me to look at and study.

share|improve this question
Worth noting that there's nothing game related in this question. You may well get a better answer from math.stackexchange.com. –  Trevor Powell Feb 15 '13 at 23:50
add comment

closed as off topic by Trevor Powell, bummzack, Byte56, Sean Middleditch, Josh Petrie Feb 19 '13 at 16:05

Questions on Game Development Stack Exchange are expected to relate to game development within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

Essentially you are asking for a derivation of the Cube Packing Problem, which is just a special case of a Packing Problem. This class of problems is known to be NP-Hard (non polynomial time solvable and at least as hard as the hardest NP-Complete problem).

There are heuristics to try and solve this that aren't guaranteed to return the optimal solution. You're going to have to refer to papers though to dig deeper.

This paper may help you get started(behind a pay wall)

A heuristic algorithm for cube packing with time schedule - Wei Li, WenQi Huang, DongChen Jiang, XiangLong Liu

share|improve this answer
I'll look into this. Thank you. –  DavidScherer Feb 15 '13 at 21:25
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.