[MUD-Dev] Finding Space

Mon Aug 18 15:19:51 CEST 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