[MUD-Dev] Finding Space

[Nathan Yospe]

On Fri, 15 Aug 1997, Shawn Halpenny wrote:

:Michael Hohensee wrote:

[something I have replied to already]

: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?

Well... that's more the parser. My book would end up on top of a couple
more books. Of course, we DO have a problem here. A book is shaped as a
non-sphere... But acts like a sphere until further notice, further notice
being a collision or placement on the table or objects on said table. The
solution I posed in the last post neglected this particular situation...
the plane. Planes are simple constructs that often occur in dispute of the
simple sphere to sphere collision. Moreover, planes in Physmud++ have
depth and equilibrium angles... that book might, if placed on a table,
just possibly end up end down, or on its side as expected. Both would
occur _after_ a "collision" was detected, however.

: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

Um. This is an attempt to fit an analog scenario into a binary (bin)
solution.

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

This IS a possible alternative to my solution... it only really makes
sense with a cubic object system, where orientation is Always orthoganal,
and with the motion distance dependant on the size of your object, and
with an adjustable checkpoint solution... its slow and unwieldy, however.

The clustering spherical collision solution is a rather effective one, if
you have the support for treatment of a set of objects as a virtual
object.

"You? We can't take you," said the Dean, glaring at the Librarian.
"You don't know a thing about guerilla warfare." - Reaper Man,
Nathan F. Yospe  Registered Looney                   by Terry Pratchett
yospe at hawaii.edu   http://www2.hawaii.edu/~yospe           Meow