[MUD-Dev] Finding Space

[clawrenc at cup.hp.com]

In <33F46159.4AD97D09 at sparta.mainstream.net>, on 08/15/97 
   at 10:18 AM, Michael Hohensee <michael at sparta.mainstream.net> said:

>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).

I'm not clear on your problem:

  Do you want to determine if two objects as placed shared volume? 
(ie collision detection)

or:

  Do you want to determine a semi-optimal packing for shaped objects
within a space such that they don't share volumes?

The first is a standard solution is is pretty easy for regular shapes.
You may want to have a look at things like RAPID
(http://www.cs.unc.edu/~geom/OBB/OBBT.html).  They claim to be able to
rotate a 20,000 polygon torus in a 98,000 polygon landscape with full
collision detection in an average of 6.0ms on a mid-range SGI.

The latter question (filling a space) is a mess, a really really nasty
mess.  I know there are partial solutions.  I'm not aware of any
computationally cheap solutions.

--
J C Lawrence                           Internet: claw at null.net
(Contractor)                           Internet: coder at ibm.net
---------------(*)               Internet: clawrenc at cup.hp.com
...Honorary Member Clan McFUD -- Teamer's Avenging Monolith...