<!-- MHonArc v2.4.4 -->
<!--X-Subject: Finding Space -->
<!--X-From-R13: [vpunry Vburafrr <zvpunryNfcnegn.znvafgernz.arg> -->
<!--X-Date: Fri, 15 Aug 1997 14:03:48 +0000 -->
<!--X-Message-Id: 33F46159.4AD97D09#sparta,mainstream.net -->
<!--X-Content-Type: text/plain -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, 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="msg00602.html">Previous</a>
| <a href="msg00604.html">Next</a>
]
Thread:
[ <a href="msg00625.html">Previous</a>
| <a href="msg00607.html">Next</a>
]
Index:
[ <A HREF="author.html#00603">Author</A>
| <A HREF="#00603">Date</A>
| <A HREF="thread.html#00603">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Finding Space</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: MUD-Dev <<A HREF="mailto:mud-dev#null,net">mud-dev#null,net</A>></LI>
<LI><em>Subject</em>: 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>: Fri, 15 Aug 1997 10:02:01 -0400</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>
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.
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.
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).
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. :)
Does anyone have the answer? :)
--
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>
<ul compact><li><strong>Follow-Ups</strong>:
<ul>
<li><strong><A NAME="00657" HREF="msg00657.html">Re: [MUD-Dev] Finding Space</A></strong>
<ul compact><li><em>From:</em> clawrenc#cup,hp.com</li></ul>
<li><strong><A NAME="00653" HREF="msg00653.html">Re: [MUD-Dev] Finding Space</A></strong>
<ul compact><li><em>From:</em> Nathan Yospe <yospe#hawaii,edu></li></ul>
<li><strong><A NAME="00607" HREF="msg00607.html">Re: [MUD-Dev] Finding Space</A></strong>
<ul compact><li><em>From:</em> Shawn Halpenny <malachai#iname,com></li></ul>
</UL></LI></UL>
<!--X-Follow-Ups-End-->
<!--X-References-->
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00602.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00604.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00625.html">Re: [MUD-Dev] Finding Space</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00607.html">Re: [MUD-Dev] Finding Space</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00603"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00603"><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>OT: test</STRONG>, <EM>(continued)</EM>
<ul compact>
<LI><strong><A NAME="00628" HREF="msg00628.html">OT: test</A></strong>,
Jon A. Lambert <a href="mailto:jlsysinc#ix14,ix.netcom.com">jlsysinc#ix14,ix.netcom.com</a>, Sun 17 Aug 1997, 05:42 GMT
</LI>
</ul>
</LI>
<LI><strong><A NAME="00619" HREF="msg00619.html">Re: [MUD-Dev] Finding Space</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Sat 16 Aug 1997, 06:05 GMT
<UL>
<LI><strong><A NAME="00620" HREF="msg00620.html">Re: [MUD-Dev] Finding Space</A></strong>,
Ned Lovely <a href="mailto:njl#NEDS,PLACE.ORG">njl#NEDS,PLACE.ORG</a>, Sat 16 Aug 1997, 09:03 GMT
</LI>
<LI><strong><A NAME="00625" HREF="msg00625.html">Re: [MUD-Dev] Finding Space</A></strong>,
Ned Lovely <a href="mailto:njl#NEDS,PLACE.ORG">njl#NEDS,PLACE.ORG</a>, Sat 16 Aug 1997, 20:53 GMT
</LI>
</UL>
</LI>
<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>
</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>