<!-- MHonArc v2.4.4 -->
<!--X-Subject: Sparse Arrays and co-ordinate based worlds -->
<!--X-From-R13: [vpunry Vburafrr <zvpunryNfcnegn.znvafgernz.arg> -->
<!--X-Date: from stimpy.globecomm.net [207.51.48.4] by in2.ibm.net id 870790333.52776-1 Tue Aug 5 14:12:13 1997 CUT -->
<!--X-Message-Id: 33E7345C.3C59ECBA#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, Sparse Arrays and co-ordinate based worlds</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="msg00393.html">Previous</a>
| <a href="msg00395.html">Next</a>
]
Thread:
[ <a href="msg00382.html">Previous</a>
| <a href="msg00398.html">Next</a>
]
Index:
[ <A HREF="author.html#00394">Author</A>
| <A HREF="#00394">Date</A>
| <A HREF="thread.html#00394">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Sparse Arrays and co-ordinate based worlds</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>: Sparse Arrays and co-ordinate based worlds</LI>
<LI><em>From</em>: Michael Hohensee <<A HREF="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</A>></LI>
<LI><em>Date</em>: Tue, 05 Aug 1997 10:10:36 -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>
This topic was discussed earlier, but I missed the beginning of it, and
so was lost trying to read the end. I also suppose that the other
people who popped in recently miught have something to say in the
matter, or at least find it interesting...
I've been sitting around for a while, thinking about how nice it would
be to have rooms arranged as if they were each entries in a vast matrix.
That is, the Throne Room of Castle Aghhh is at *world[104][42][2], etc.
This means that I can take any path I choose to the Throne Room, as long
as there aren't any walls in the way. Further, I don't have to worry
about wandering to places that don't currently exist as "written" rooms,
since I will get some generated description based upon the type of room
I enter. (time to wipe the drool off our chins).
Unfortunately, this kind of array is very large and memory consuming.
So memory consuming that my compiler chokes on any program with an array
of dimensions, say: [1000][1000][100]. Now we all know that it is very
unlikely that we would ever get 100000000 objects of any sort in play at
once, but we could imagine (stretching a little) a builder lining 1000
rooms in a row. Such a builder should of course be shot on sight. But
it'd be nice to be *able* to do it, should the need arise...
Ok, we can't use arrays outright, because they waste memory. (I
haven't, as the subject of the message suggests, read anything about
"sparse arrays", so bear with me) I figured that instead, each object
could contain its own co-ordinates, and be placed, in order, upon a
linked list with every other object in the world. In the gaps in
between objects (ie: The big rock is 5 rooms/units away from Castle
Aghh), a filler link would be located, which says that the 5 rooms in
between it and the next object are grassland.
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?
--
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="00524" HREF="msg00524.html">Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</A></strong>
<ul compact><li><em>From:</em> clawrenc#cup,hp.com</li></ul>
<li><strong><A NAME="00398" HREF="msg00398.html">Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</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="msg00393.html">Re: [MUD-Dev] Graphic MUDS.</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00395.html">[MUD-Dev] Worlds VS Games, etc {was GMuds, UO}</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00382.html">Sparse Arrays and co-ordinate based worlds</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00398.html">Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00394"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00394"><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="00397" HREF="msg00397.html">Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</A></strong>,
Cynbe ru Taren <a href="mailto:cynbe#laurel,actlab.utexas.edu">cynbe#laurel,actlab.utexas.edu</a>, Wed 06 Aug 1997, 00:26 GMT
<UL>
<LI><strong><A NAME="00422" HREF="msg00422.html">Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</A></strong>,
Michael Hohensee <a href="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</a>, Thu 07 Aug 1997, 16:08 GMT
</LI>
</UL>
</LI>
<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>
</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>