<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds -->
<!--X-From-R13: Qlaor eh Fnera <plaorNynhery.npgyno.hgrknf.rqh> -->
<!--X-Date: from stimpy.globecomm.net [207.51.48.4] by in3.ibm.net id 870801995.174428-1 Tue Aug 5 17:26:35 1997 CUT -->
<!--X-Message-Id: 199708051726.MAA31970#laurel,actlab.utexas.edu -->
<!--X-Content-Type: text/plain -->
<!--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:cynbe#laurel,actlab.utexas.edu">
</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="msg00396.html">Previous</a>
| <a href="msg00398.html">Next</a>
]
Thread:
[ <a href="msg00406.html">Previous</a>
| <a href="msg00422.html">Next</a>
]
Index:
[ <A HREF="author.html#00397">Author</A>
| <A HREF="#00397">Date</A>
| <A HREF="thread.html#00397">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>: Cynbe ru Taren <<A HREF="mailto:cynbe#laurel,actlab.utexas.edu">cynbe#laurel,actlab.utexas.edu</A>></LI>
<LI><em>Date</em>: Tue, 5 Aug 1997 12:26:17 -0500</LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
| 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
| from [100][20][0] to [110][30][10], avoiding going over the room at
|[90][23][5] and its friends.
Bingo, except there's no reason to use spatial clustering like
that for your hash function: Won't help you and is quite likely
to hurt you. Just mangle key (three integers, in this case) into
a pretty arbitrary hashcode to scatter your entries over the table.
Adding them is a quick hack, using something like MD5 will give
you a betterhash which may or may not be worth the coding and run
time. Keep the table empty enough that most of your lists are
one long or empty.
| Would such a system be viable? Could any improvements be made to it?
Well, you're effectively basing your system on a coarse integer
coordinate system. If the idea works at all, I'd predict on past
experience that you'll wind up cursing them eventually and recoding
to use float coordinates. If you wind up doing anything involving
needing to know object orientation, you will then eventually wind
up cursing -that- and representing object coordinate info using
4x4 homogeneous transform matrices... or wishing you could but being
unable to because of installed codebase (e.g., the NASA Panel library
wound up that way). There's still no particular problem hashing
three or sixteen floats into a hashcode and looking them up, if you're
just needing exact matches. (Need to watch precision problems a
bit, depending on what your're doing.) If you can't settle for
exact matches, then you're back to R-trees, which have already
been covered here. :0
</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="00422" HREF="msg00422.html">Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</A></strong>
<ul compact><li><em>From:</em> Michael Hohensee <michael#sparta,mainstream.net></li></ul>
</UL></LI></UL>
<!--X-Follow-Ups-End-->
<!--X-References-->
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00396.html">Re: [MUD-Dev] New Topic: Butthead features</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00398.html">Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00406.html">Re: [MUD-Dev] Graphic MUDS/perspectives</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00422.html">Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00397"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00397"><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>Re: [MUD-Dev] Reputation, was butthead features</STRONG>, <EM>(continued)</EM>
<ul compact>
<ul compact>
<ul compact>
<LI><strong><A NAME="00431" HREF="msg00431.html">Re: [MUD-Dev] Reputation, was butthead features</A></strong>,
Adam Wiggins <a href="mailto:nightfall#user2,inficad.com">nightfall#user2,inficad.com</a>, Fri 08 Aug 1997, 17:15 GMT
</LI>
</ul>
</ul>
</ul>
</LI>
<LI><strong><A NAME="00401" HREF="msg00401.html">[MUD-Dev] Ultima Online/Generalized AI</A></strong>,
Koster, Raph <a href="mailto:rkoster#origin,ea.com">rkoster#origin,ea.com</a>, Wed 06 Aug 1997, 02:13 GMT
<LI><strong><A NAME="00400" HREF="msg00400.html">RE: [MUD-Dev] Graphic MUDS/perspectives</A></strong>,
Koster, Raph <a href="mailto:rkoster#origin,ea.com">rkoster#origin,ea.com</a>, Wed 06 Aug 1997, 01:58 GMT
<UL>
<LI><strong><A NAME="00406" HREF="msg00406.html">Re: [MUD-Dev] Graphic MUDS/perspectives</A></strong>,
Jeff Kesselman <a href="mailto:jeffk#tenetwork,com">jeffk#tenetwork,com</a>, Wed 06 Aug 1997, 09:34 GMT
</LI>
</UL>
</LI>
<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
</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>