A packing problem

From: gkhan (oskarsigvardsson_at_gmail.com)
Date: 02/23/05 

Date: 23 Feb 2005 03:09:31 -0800

A friend showed me the game Diablo 2 a while ago, and while he was more
interested in slaying zombies I started to ponder an algorithmic
problem that the game poses. In the game you have a sort of "knapsack"
which is basically a two-dimensional grid where you could put your
items. The items had certain dimensions that could be packed in this
knapsack where no two items could overlap. For instance say that the
knapsack is 3 times 4 spaces (btw, I apologise for the crappy
ascii-art, I hope it renders correctly)

 -----------
| | | | |
| | | | |
| | | | |
 -----------

Then we for instance can put in a 3 times 1 sword (SW) as such

 -----------
| |SW| | |
| |SW| | |
| |SW| | |
 -----------

Then we want to pack a 1 times 3 spear (SP), but it does not fit.
However if we move the sword it does.

 -----------
|SW| | | |
|SW|SP|SP|SP|
|SW| | | |
 -----------

But now my 2 times 1 dagger doesn't fit! Well, actually....

 -----------
|SW|SP|SP|SP|
|SW| |DA| |
|SW| |DA| |
 -----------

This example is ofcourse trivial, but it serves to demonstrate the
general problem. Given a x times y knapsack and k items with dimensions
x_n times y_n can you fit them all into the knapsack (obviously the sum
of the areas of the itmes is less than the area of the knapsack)? I've
tried to figure out a nice algorithm for this and I've come up blank.
Is there one already? If not, has anyone got any tips? My first idea
was some sort of optimum-substructure variation using dynamic
programming or a greedy strategy, but that didn't pan out (maybe it
does and I just missed it though). Maybe some sort of adaptation of
graphing algorithms (no I am just brainstorming), an adaptation of DFS
perhaps?

Oskar

PS. My intrest in this problem is pure curiosity, it's not homework or
anything.

Relevant Pages

  • Re: new here, my lang project...
    ... > the thread management when playing off game time vs. refresh time vs. ... > shadow algorithm has. ... > behavior Y execute first in an algorithmic sequence. ... the precondition is usually fairly easy to ...
    (comp.object)
  • Re: new here, my lang project...
    ... Just the thread management when playing off game time vs. refresh time ... that the shadow algorithm has. ... the precondition is usually fairly easy to ... The point here is that the sender/receiver associations aren't ...
    (comp.object)
  • Re: An Intelligent Toy
    ... To the learning algorithm, the reward input is what gives the ... It does this by using statistics to analize all it's actions and to ... and small - like the state of a tic-tac-toe game. ...
    (sci.cognitive)
  • [ANN] NP
    ... This extension, 'NP,' is a module for the Ruby language. ... Multiple Knapsack 0-1 ... This algorithm could be used to assign n tasks to m machines for even load distribution. ... found such that every clause evaluates to true? ...
    (comp.lang.ruby)
  • Re: Chinese and Japanese scoring
    ... I never understood Chinese scoring until I studied the Wally source code. ... claim victory in a game in which all of Wally's pieces are lost: ... That makes it useless to try to use Wally's scoring algorithm ... lot more than just the positional evaluation), ...
    (rec.games.go)