<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds -->
<!--X-From-R13: pynjerapNphc.uc.pbz -->
<!--X-Date: Wed, 13 Aug 1997 23:12:20 +0000 -->
<!--X-Message-Id: 199708132310.QAA05793#xsvr3,cup.hp.com -->
<!--X-Content-Type: text/plain -->
<!--X-Reference: 33E7345C.3C59ECBA#sparta,mainstream.net -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:clawrenc#cup,hp.com">
</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="msg00523.html">Previous</a>
| <a href="msg00525.html">Next</a>
]
Thread:
[ <a href="msg00398.html">Previous</a>
| <a href="msg00381.html">Next</a>
]
Index:
[ <A HREF="author.html#00524">Author</A>
| <A HREF="#00524">Date</A>
| <A HREF="thread.html#00524">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</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] Sparse Arrays and co-ordinate based worlds</LI>
<LI><em>From</em>: <A HREF="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</A></LI>
<LI><em>Date</em>: Wed, 13 Aug 97 16:03:10 -0700</LI>
<LI><em>Reply-to</em>: <A HREF="mailto:claw#null,net">claw#null,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>
In <<A HREF="msg00394.html">33E7345C.3C59ECBA#sparta,mainstream.net</A>>, on 08/05/97
at 08:20 AM, Michael Hohensee <michael#sparta,mainstream.net> said:
>The only downside to this is that it is time-intensive to use the
>system as an array. Since you get the contents of a room by going
>down the list until you hit the proper co-ordinates. This, I
>suppose, is the old trade of memory for performance and vice versa
>scenerio.
>Ok, next improvement. Instead of having one linked list, break it up
>into a few hundred lists with a hashtable. That way, when you look
>for a room at [100][23][5], you only look in the list which contains
>objects from [100][20][0] to [110][30][10], avoiding going over the
>room at [90][23][5] and its friends.
>Would such a system be viable? Could any improvements be made to it?
No, it wouldn't be viable as soon as the number of objects got large.
You need to look into the various space representing data structures
such as R-Trees, R*-trees, V-Trees, H-Trees, quad/oct-trees, etc. I'd
suggest getting various books on the area (no specific
recommendations) and thoroughly browsing the LEDA and Stony Brook
sites as well as digging thru the list of available C++ libraries as
posted to comp.lang.c++ (or was it comp.std.c++?). There are a lot of
different possible structures to use, eah with its own benefits and
uses.
Note from my own such survey, still ongoing: A key consideration for
me is the ease and expense of generating a list of all objects within
a defined range of a coordinate, *and* the expense/difficulty of
generating a similar list of ranged objects which meet a standarised
criteria.
--
J C Lawrence Internet: claw#null,net
(Contractor) Internet: coder#ibm,net
---------------(*) Internet: clawrenc#cup,hp.com
...Honorary Member Clan McFUD -- Teamer's Avenging Monolith...
</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="00394" HREF="msg00394.html">Sparse Arrays and co-ordinate based worlds</A></STRONG>
<UL><LI><EM>From:</EM> Michael Hohensee <michael#sparta,mainstream.net></LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00523.html">Re: [MUD-Dev] New Topic: Butthead features</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00525.html">Re: [MUD-Dev] Mud Languages</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00398.html">Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00381.html">PirateMUD and CSL</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00524"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00524"><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="00395" HREF="msg00395.html">[MUD-Dev] Worlds VS Games, etc {was GMuds, UO}</A></strong>,
Koster, Raph <a href="mailto:rkoster#origin,ea.com">rkoster#origin,ea.com</a>, Tue 05 Aug 1997, 23:04 GMT
<LI><strong><A NAME="00382" HREF="msg00382.html">Sparse Arrays and co-ordinate based worlds</A></strong>,
Michael Hohensee <a href="mailto:michael#mainstream,net">michael#mainstream,net</a>, Tue 05 Aug 1997, 00:51 GMT
<UL>
<li><Possible follow-up(s)><br>
<LI><strong><A NAME="00394" HREF="msg00394.html">Sparse Arrays and co-ordinate based worlds</A></strong>,
Michael Hohensee <a href="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</a>, Tue 05 Aug 1997, 21:12 GMT
<UL>
<LI><strong><A NAME="00398" HREF="msg00398.html">Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</A></strong>,
Shawn Halpenny <a href="mailto:malachai#iname,com">malachai#iname,com</a>, Wed 06 Aug 1997, 00:38 GMT
</LI>
<LI><strong><A NAME="00524" HREF="msg00524.html">Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</A></strong>,
clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Wed 13 Aug 1997, 23:12 GMT
</LI>
</UL>
</LI>
</UL>
</LI>
<LI><strong><A NAME="00381" HREF="msg00381.html">PirateMUD and CSL</A></strong>,
Niklas Elmqvist <a href="mailto:croziys#algonet,se">croziys#algonet,se</a>, Tue 05 Aug 1997, 00:25 GMT
<UL>
<LI><strong><A NAME="00501" HREF="msg00501.html">Re: [MUD-Dev] PirateMUD and CSL</A></strong>,
clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Tue 12 Aug 1997, 23:10 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00349" HREF="msg00349.html">Re: [MUD-Dev] New Topic: Butthead features</A></strong>,
Jon A. Lambert <a href="mailto:jlsysinc#ix,netcom.com">jlsysinc#ix,netcom.com</a>, Sun 03 Aug 1997, 14:46 GMT
<UL>
<LI><strong><A NAME="00364" HREF="msg00364.html">Re: [MUD-Dev] New Topic: Butthead features</A></strong>,
Jeff Kesselman <a href="mailto:jeffk#tenetwork,com">jeffk#tenetwork,com</a>, Mon 04 Aug 1997, 08:47 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>