Finding Space

[Michael Hohensee]

I've been working up a system in which objects take up space in a
co-ordinate based world, and I seem to have hit a stumbling block.  I
know that others have probably solved this problem (Physmud++ *must*
have had to solve this ;), so maybe someone can help me.

Here's how it works:

We are representing a three dimensional space, but in this example we'll
restrict it to two dimensions.

4-----------------------------
3------******--------**-------
2------******-----**-**--*****
1----*-******-----**-**-------
0-----------------------------
 0 2 4 6 8 1012
  1 3 5 7 9 11
'-' = empty space, '*' = space taken up by an object.

For simplicity, all objects take up a cubical volume of space (square,
in this case).  Objects are held in a tree or linked list of structs
which contain the origin point of the object, and the dimensions of the
object.  For example, the big square in the picture above would be
Location=6,1 -- Dimensions=6,3.

I can store anything to any location I want, but I want to avoid
overlapping objects onto each other (it's bad), so I need to be able to
find empty space between objects.  I can't just try to place an object
in every location, since there isn't any granularity to this space (I
use floats instead of ints).

A friend of mine glanced at this problem and said, "Oh, that's a
bin-stuffing problem."  Of course, he didn't remember anything else
about the problem, so here I am. :)

Does anyone have the answer? :)

--
Michael Hohensee       michael at sparta.mainstream.net
http://www.geocities.com/SiliconValley/Heights/9025/
      Finger me for my PGP Public Key, or use: 
http://sparta.mainstream.net/michael/pgpkey.txt