<!-- MHonArc v2.4.4 --> <!--X-Subject: Re: [MUD-Dev] Finding Space --> <!--X-From-R13: @rq Zbiryl <awyN#SRE,BZOQS.ADU> --> <!--X-Date: Sat, 16 Aug 1997 20:53:52 +0000 --> <!--X-Message-Id: 199708162100.RAA19235#NEDS,PLACE.ORG --> <!--X-Content-Type: text --> <!--X-Reference: 9708160230.8c3o@ami-cg.GraySage.Edmonton.AB.CA --> <!--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:njl#NEDS,PLACE.ORG"> </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="msg00624.html">Previous</a> | <a href="msg00626.html">Next</a> ] Thread: [ <a href="msg00620.html">Previous</a> | <a href="msg00603.html">Next</a> ] Index: [ <A HREF="author.html#00625">Author</A> | <A HREF="#00625">Date</A> | <A HREF="thread.html#00625">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>: Ned Lovely <<A HREF="mailto:njl#NEDS,PLACE.ORG">njl#NEDS,PLACE.ORG</A>></LI> <LI><em>Date</em>: Sat, 16 Aug 1997 17:00:41 -0400 (EDT)</LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> > :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. :) > Also called "bin packing", I believe. Not something I know anything about. Well, I dug out my generic algorithm tome, and I found that one of the questions in the chapter on approximations deals with bin packing. This is from "Introduction to Algorithms," by Cormen, Leiserson, and Rivest, MIT Press, 1990. I'm going to use () for subscripts, and I'll type out the summation in English instead of trying to draw it ;) ---- 37-1 Bin Packing Suppose that we are given a set of n objects, where the size s(i) of the ith object satisfies 0 < s(i) < 1. We wish to pack all the objects into the minimum number of unit-sized bins. Each bin can hold any subset of the objects whose total size does not exceed 1. a. PRove that the problem of determining the minimum number of bins required is NP-Hard. (Hint: Reduce from the subset-sum problem.) The first-fit heuristic takes each object in turn and places it into the first bin that can accommadate it. Let S = (the sum from i=1 to n of s(i)). b. Argue that the optimal number of bins required is at least ceiling(S). c. Argue that the first-fit heuristic leaves at most one bin less than half full. d. PRove that the number of bins used by the first-fit heuristic is never more than ceiling(2S). e. Prove a ratio bound of 2 for the first fit heuristic. f. Give an efficient implementation of the first fit heuristic, and analyze its running time. ---- Any mistakes are, of course, mine in the transcription... Doesn't sound like ensuring non-collision in a 3-D space is a bin stuffing problem... As a quick guess, the fastest way to to it would be to give each object a center. Cache the distance from the center to the farthest out point on that object. To check for collision, measure the distance from center-to-center, and compare it to how much space the objects need. If it is greater, you're golden. If it's closer, do something a lot ickier... I can think of ways to do it in 2-D space, but generalizing it to #-D space feels ugly. > :Does anyone have the answer? :) > Well, this is beginning to sound a *lot* like Winograd's "Blocks World". > He got a PhD degree for implementing that! I dug up a URL that looked kinda interesting. Do you have a pointer to a good site/paper for that? Well, since this is my first message, I should give a little bit of an introduction. I've been interested in muds ever since a local 8-line BBS ran a circle for its subscribers. I've always been fascinated with how people communicated, and I was impressed by the potential for strange and interesting interaction. Right now, I'm looking for someone to hand me specs for a mud so that I can just write it. I know I can write module-level code, and I've got more theory on OO design than I could shake a stick at. I figure I should actually do something with it. -- njl </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="00619" HREF="msg00619.html">Re: [MUD-Dev] Finding Space</A></STRONG> <UL><LI><EM>From:</EM> cg#ami-cg,GraySage.Edmonton.AB.CA (Chris Gray)</LI></UL></LI> </UL></LI></UL> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg00624.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg00626.html">Character evolution</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg00620.html">Re: [MUD-Dev] Finding Space</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00603.html">Finding Space</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#00625"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#00625"><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="00623" HREF="msg00623.html">OT: test</A></strong>, Odysseus Laertes <a href="mailto:jlsysinc#ix16,ix.netcom.com">jlsysinc#ix16,ix.netcom.com</a>, Sat 16 Aug 1997, 19:19 GMT <UL> <li><Possible follow-up(s)><br> <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 </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>