[MUD-Dev] Finding Space

[Nathan Yospe]

On Fri, 15 Aug 1997, Michael Hohensee wrote:

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

Yes and no. Same as collision detection... exactly the same, in fact, as
this is a big part of what I consider collision detection. I use spheres
around the center of volume (not to be confused with the center of mass)
of a group of objects, single composite object, individual components...
and then I assume that the particulate (smallest tracked) components are
spherical. This reduces any "will I fit?" problem to a series of fast
comparisons that only get ugly when a collision is immenent (and since I
track in four dimensions, the fourth being a minute projection forward in
time, I have a chance to prepare for collisions.)

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

First off, spheres are simpler in 3D than cubes. Little bit of advice from
a graphical engine hand. MUCH simpler.

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

And thus the reason for spheres. Use a transform and a single calculation
gives you the shortest distance between two points. Then just check to
make sure that's more than the radius of both spheres summed.

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

Um. Bin stuffing would have been ints and a grid of locations.

:Does anyone have the answer? :)

Well, if mine made any sense...

"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