<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Finding Space -->
<!--X-From-R13: [vpunry Vburafrr <zvpunryNfcnegn.znvafgernz.arg> -->
<!--X-Date: Mon, 18 Aug 1997 19:22:13 +0000 -->
<!--X-Message-Id: 33F8A056.2330852C#sparta,mainstream.net -->
<!--X-Content-Type: text/plain -->
<!--X-Reference: Pine.GSO.3.95q.970817213842.16831B-100000@uhunix2 -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Re: [MUD-Dev] Finding Space</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:michael#sparta,mainstream.net">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg00655.html">Previous</a>
| <a href="msg00657.html">Next</a>
]
Thread:
[ <a href="msg00653.html">Previous</a>
| <a href="msg00657.html">Next</a>
]
Index:
[ <A HREF="author.html#00656">Author</A>
| <A HREF="#00656">Date</A>
| <A HREF="thread.html#00656">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Re: [MUD-Dev] Finding Space</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <A HREF="mailto:mud-dev#null,net">mud-dev#null,net</A></LI>
<LI><em>Subject</em>: Re: [MUD-Dev] Finding Space</LI>
<LI><em>From</em>: Michael Hohensee <<A HREF="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</A>></LI>
<LI><em>Date</em>: Mon, 18 Aug 1997 15:19:51 -0400</LI>
<LI><em>CC</em>: <A HREF="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</A></LI>
<LI><em>Sender</em>: <A HREF="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</A></LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
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#sparta,mainstream.net
<A HREF="http://www.geocities.com/SiliconValley/Heights/9025/">http://www.geocities.com/SiliconValley/Heights/9025/</A>
Finger me for my PGP Public Key, or use:
<A HREF="http://sparta.mainstream.net/michael/pgpkey.txt">http://sparta.mainstream.net/michael/pgpkey.txt</A>
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<!--X-Follow-Ups-End-->
<!--X-References-->
<UL><LI><STRONG>References</STRONG>:
<UL>
<LI><STRONG><A NAME="00653" HREF="msg00653.html">Re: [MUD-Dev] Finding Space</A></STRONG>
<UL><LI><EM>From:</EM> Nathan Yospe <yospe#hawaii,edu></LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00655.html">Re: [MUD-Dev] Character evolution</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00657.html">Re: [MUD-Dev] Finding Space</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00653.html">Re: [MUD-Dev] Finding Space</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00657.html">Re: [MUD-Dev] Finding Space</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00656"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00656"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><strong><A NAME="00603" HREF="msg00603.html">Finding Space</A></strong>,
Michael Hohensee <a href="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</a>, Fri 15 Aug 1997, 14:03 GMT
<UL>
<LI><strong><A NAME="00607" HREF="msg00607.html">Re: [MUD-Dev] Finding Space</A></strong>,
Shawn Halpenny <a href="mailto:malachai#iname,com">malachai#iname,com</a>, Fri 15 Aug 1997, 18:12 GMT
<UL>
<LI><strong><A NAME="00654" HREF="msg00654.html">Re: [MUD-Dev] Finding Space</A></strong>,
Nathan Yospe <a href="mailto:yospe#hawaii,edu">yospe#hawaii,edu</a>, Mon 18 Aug 1997, 08:01 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00653" HREF="msg00653.html">Re: [MUD-Dev] Finding Space</A></strong>,
Nathan Yospe <a href="mailto:yospe#hawaii,edu">yospe#hawaii,edu</a>, Mon 18 Aug 1997, 07:48 GMT
<UL>
<LI><strong><A NAME="00656" HREF="msg00656.html">Re: [MUD-Dev] Finding Space</A></strong>,
Michael Hohensee <a href="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</a>, Mon 18 Aug 1997, 19:22 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00657" HREF="msg00657.html">Re: [MUD-Dev] Finding Space</A></strong>,
clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Tue 19 Aug 1997, 00:21 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00556" HREF="msg00556.html">[MUD-Dev] Spellcaster, or Waving Hands</A></strong>,
Cynbe ru Taren <a href="mailto:cynbe#laurel,actlab.utexas.edu">cynbe#laurel,actlab.utexas.edu</a>, Thu 14 Aug 1997, 17:50 GMT
<UL>
<LI><strong><A NAME="00583" HREF="msg00583.html">Re: [MUD-Dev] Spellcaster, or Waving Hands</A></strong>,
clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Thu 14 Aug 1997, 22:21 GMT
<UL>
<LI><strong><A NAME="00587" HREF="msg00587.html">Re: [MUD-Dev] Spellcaster, or Waving Hands</A></strong>,
Richard Woolcock <a href="mailto:KaVir#dial,pipex.com">KaVir#dial,pipex.com</a>, Thu 14 Aug 1997, 23:06 GMT
</LI>
</UL>
</LI>
</UL>
</LI>
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>