# [MUD-Dev] Finding Space

Michael Hohensee michael at sparta.mainstream.net
Mon Aug 18 15:19:51 New Zealand Standard Time 1997

```Ok, I should mention that I finally do have a working collision
detection and space finding system written, even though it
isn't the most efficent in the world (it is a grinder.. ;).
I'll post it at the bottom of this message, for those who are
interested.

Nathan Yospe wrote:
>
> 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.

Yes, spheres would be a *lot* more resource-friendly, but the problem
I have with spheres is that they aren't very good at tiling space, since
there are always little gaps between spheres.

I might be able to get around this by differentiating between the world
and the objects within it, (world is a cubical construct, objects are
spheres) but this runs counter to my mud-coding philosophy, which states
that every component of the world should be able to generally behave
like
any other component. (objects can hold worlds of various flavors).
Putting
a square inside a circle would probably just drive players (and me)
nuts.
:)

I suppose you could overlap some spheres and get full coverage, but how
do you decide which sphere an object is actually in?

Here's my "solution" I promised you.  Note that it is written
for a linked-list implementation of a container.  Depending
upon the number of objects it contains, I plan to have it
switch to a more efficient container list. (good old separation
of implementation from interface.)

struct LL_Holder {
A_Obj *holding;
Location *loc;
};

struct Location {
double X;
double Y;
double Z;
};

struct Dimensions {
double Xwidth;
double Ywidth;
double Zwidth;
};

class LL_Container : A_Container {

bool does_overlap(A_Obj *obj, Location *loc)
{
LL_Holder *ptr;
double  X,  Y,  Z,  pX,  pY,  pZ;
double oX, oY, oZ, opX, opY, opZ;

X = loc->X;
Y = loc->Y;
Z = loc->Z;
pX= obj->my_dimensions->Xwidth;
pY= obj->my_dimensions->Ywidth;
pZ= obj->my_dimensions->Zwidth;

for (ptr = held; ptr != 0; ptr = ptr->next)
{
oX = ptr->loc->X;
oY = ptr->loc->Y;
oZ = ptr->loc->Z;
opX= ptr->holding->my_dimensions->Xwidth;
opY= ptr->holding->my_dimensions->Ywidth;
opZ= ptr->holding->my_dimensions->Zwidth;

/* Somewhat hard to read..  I check for
linear overlap in each dimension.
To visualize this, draw two cubes, and label
their origins (X,Y,Z) , and (oX,oY,oZ).
Label the corner directly opposite the
origins of the cubes (pX,pY,pZ) and (opX,opY,opZ)
respectively.  Then label the other corners
appropiately. */

if ( ((oX <= X) && (oX + opX >= X + pX)) ||
((oX > X) && ( (oX < X + pX) ||
(oX + opX < X + pX) )) )
if ( ((oY <= Y) && (oY + opY >= Y + pY)) ||
((oY > Y) && ( (oY < Y + pY) ||
(oY + opY < Y + pY) )) )
if ( ((oZ <= Z) && (oZ + opZ >= Z + pZ)) ||
((oZ > Z) && ( (oZ < Z + pZ) ||
(oZ + opZ < Z + pZ) )) )
return 1;
}
return 0;
}

bool find_space(A_Obj *for_me, Location *loc)
{
LL_Holder *ptr;
Location try, *a_loc = &try;
double x, y, z;
double xp, yp, zp;

a_loc->X = 0.0;
a_loc->Y = 0.0;
a_loc->Z = 0.0;

if (!does_overlap(for_me, a_loc))
{
loc->X = a_loc->X;
loc->Y = a_loc->Y;
loc->Z = a_loc->Z;
return 1;
}

for (ptr = held; ptr != 0; ptr = ptr->next)
{
x = ptr->loc->X;
y = ptr->loc->Y;
z = ptr->loc->Z;
xp = ptr->holding->my_dimensions->Xwidth;
yp = ptr->holding->my_dimensions->Ywidth;
zp = ptr->holding->my_dimensions->Zwidth;

a_loc->X = x;
a_loc->Y = y;
a_loc->Z = z;
if (!does_overlap(for_me, a_loc))
{
loc->X = a_loc->X;
loc->Y = a_loc->Y;
loc->Z = a_loc->Z;
return 1;
}

a_loc->X += xp;
if (!does_overlap(for_me, a_loc))
{
loc->X = a_loc->X;
loc->Y = a_loc->Y;
loc->Z = a_loc->Z;
return 1;
}

a_loc->X -= xp;
a_loc->Y += yp;
if (!does_overlap(for_me, a_loc))
{
loc->X = a_loc->X;
loc->Y = a_loc->Y;
loc->Z = a_loc->Z;
return 1;
}

a_loc->Y -= yp;
a_loc->Z += zp;
if (!does_overlap(for_me, a_loc))
{
loc->X = a_loc->X;
loc->Y = a_loc->Y;
loc->Z = a_loc->Z;
return 1;
}

a_loc->Y += yp;
if (!does_overlap(for_me, a_loc))
{
loc->X = a_loc->X;
loc->Y = a_loc->Y;
loc->Z = a_loc->Z;
return 1;
}

a_loc->Y -= yp;
a_loc->X += xp;
if (!does_overlap(for_me, a_loc))
{
loc->X = a_loc->X;
loc->Y = a_loc->Y;
loc->Z = a_loc->Z;
return 1;
}

a_loc->Z -= zp;
a_loc->Y += yp;
if (!does_overlap(for_me, a_loc))
{
loc->X = a_loc->X;
loc->Y = a_loc->Y;
loc->Z = a_loc->Z;
return 1;
}

a_loc->Z += zp;
if (!does_overlap(for_me, a_loc))
{
loc->X = a_loc->X;
loc->Y = a_loc->Y;
loc->Z = a_loc->Z;
return 1;
}
}
return 0;
}
};

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

```