Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 1 down vote favorite

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
1  
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 at 23:50

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

Questions on Game Development Stack Exchange are expected to relate to game development within the scope defined in the FAQ. 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 closed questions here.

1 Answer

up vote 2 down vote

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 at 21:25

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