[MUD-Dev] Finding Space

[Shawn Halpenny]

Michael Hohensee wrote:

[ picture of object placement ]

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

Are the objects you are placing required to end up in a position relative
to surrounding objects?  For example, given "put the book on the table" and
no space on the table, where does the book go?

If relative object placement is not a big deal, and you just need the
objects to sit such that no parts of them are occupying the same space, how
about something along these lines:

1.  consider the room a box having known dimensions
2.  try to put the object A at the first open space in the box using
    your favorite 3D intersection algorithm.  Start at the spot off in the
	corner on the floor, say.
3.  if it doesn't fit there because of an object B already sitting there, move
    to the edge of B in some direction and try again.
4.  repeat until A is placed

Of course, a substantial number of objects in the room already will slow
you down, so you'd probably want to throw some partitioning into the mix
so as to minimize the number of intersection tests you have to do--after a
failed test, partition your space and try to place object at a new position
in one of the partitions.  You'll need a breaking point, though, or else
as the number of objects increases you'll be unable to find anywhere to put
them.  At that point, you'll have to go back to the original algorithm.

I think I remember seeing good algorithms for this a few years ago...maybe
in a Graphics Gems or something...

--
Shawn Halpenny

"You got a one way ticket on your last chance ride."
                                        - "Coma"