<!-- MHonArc v2.4.4 -->
<!--X-Subject: RE: [MUD-Dev] Spatial datastructures and their application (Was Re: Hilbert Curves) -->
<!--X-From-R13: "Zb, Ynz" <ZbYNybtvpn.pbz> -->
<!--X-Date: Fri, 05 Nov 1999 11:04:47 -0800 -->
<!--X-Message-Id: 4FBF540FF16FD1119D9600A0C94B2B51058B80C6#napier,logica.co.uk -->
<!--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] Spatial datastructures and their application (Wa</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:LoK#logica,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="msg00127.html">Previous</a>
| <a href="msg00128.html">Next</a>
]
Thread:
[ <a href="msg00129.html">Previous</a>
| <a href="msg00130.html">Next</a>
]
Index:
[ <A HREF="author.html#00125">Author</A>
| <A HREF="#00125">Date</A>
| <A HREF="thread.html#00125">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>RE: [MUD-Dev] Spatial datastructures and their application (Was Re: Hilbert Curves)</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: "'<A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A>'" <<A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A>></LI>
<LI><em>Subject</em>: RE: [MUD-Dev] Spatial datastructures and their application (Was Re: Hilbert Curves)</LI>
<LI><em>From</em>: "Lo, Kam" <<A HREF="mailto:LoK#logica,com">LoK#logica,com</A>></LI>
<LI><em>Date</em>: Fri, 5 Nov 1999 10:30:40 -0000 </LI>
<LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
<LI><em>Sender</em>: <A HREF="mailto:mud-dev-admin#kanga,nu">mud-dev-admin#kanga,nu</A></LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
> From: Christopher Allen
> Sent: 05 November 1999 03:13
>
> A faster alternative is to do a Hilbert search to find those objects that
> are within 100x100 points around the player. This delivers a list of
> potential visible objects in a rectangle around the player. This typically
> is a relatively small list, say of a dozen objects.
> You can then sort that list by actual linear distance, modified by height
> and possibly the intervening terrain. Then only tell the player about
those
> that might be visible. If you wanted to add some more complication, you
> could even have slightly different descriptions depending on the
visibility
> and distance. These functions do not take that much time.
> The result: "You see a house not too far to the north, an unusual rock
> outcropping far to the west, and the top of tower beyond the horizon to
the
> southeast."
That still sounds like a lot of computations for each and every look.
Here's another half-baked idea from Ling's Fantastic Brain (tm). (Don't
argue with that description)
Assuming a sexy description generator is available, describe the world with
primitives, such as oblongs, spheres and cylinders. Builders arrange these
primitives and give them attributes then bind a bunch together in a
rectangle (as in r-tree rectangle). The builder then marks some attributes
on the rectangle (eg: building, mountain, tree, or whatever) and attaches
this to a bigger rectangle which describes the terrain the children
rectangles are in (eg: park). This proceeds up the tree with each parent
holding attributes that encompasses the children (eg: town, borough, county,
country, continent, planet, etc). Rectangles are allowed to grossly
overlap, don't see why not. The description generator works top-down by one
step, that is, descriptions are composed from the immediate kids of this
rectangle, no further.
Prominent features are propagated up the tree with attenuation, so a
particularly bright beacon on the rooftop of a skyscraper will affect the
description of the rooftop which in turn affects the skyscraper's
description which in turn affects the city's description. This should be
done in a semi-lazy manner. For each new effect that can propagate in any
medium, the affected parent rectangles should be marked as requiring a
description update.
Observers should grab descriptions depending upon their relative location.
The immediate parent rectangle should give a clue as to where the character
is (eg: in a park, city, room, under a desk). Next, adjacent rectangles at
the same level are grabbed (room next door), followed by rectangles from
higher up the tree further out (church opposite, Rockies in the background).
Admittedly, the r-tree is not really an r-tree since it breaks the rules for
number of branches per node.
My reasons for this odd arrangement include: distant landmarks might have a
chance of appearing in the description, eg: distant cities will appear
exactly as so, not a sporadic spam of buildings; it seems sensible; and I
have no idea what I'm doing.
Disadvantage of this system is obvious, I've assumed the descriptions will
be the same for each and every character. This can be adjusted by
propagating attributes instead of completed descriptions, observers can then
generate their own descriptions. In fact, this would probably be workable
if attributes were sent to the client which then generate the description.
Another disadvantage is that this is theoretical and I have not and will not
implement it.
Ling
_______________________________________________
MUD-Dev maillist - MUD-Dev#kanga,nu
<A HREF="http://www.kanga.nu/lists/listinfo/mud-dev">http://www.kanga.nu/lists/listinfo/mud-dev</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="00130" HREF="msg00130.html">RE: [MUD-Dev] Spatial datastructures and their application (Was R e: Hilbert Curves)</A></strong>
<ul compact><li><em>From:</em> Owen <owend#obscure,org></li></ul>
</UL></LI></UL>
<!--X-Follow-Ups-End-->
<!--X-References-->
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00127.html">[MUD-Dev] A simple plan for establishing a history.</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00128.html">[MUD-Dev] Server: Momoko</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00129.html">[MUD-Dev] Scripting in java... (was Momoko)</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00130.html">RE: [MUD-Dev] Spatial datastructures and their application (Was R e: Hilbert Curves)</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00125"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00125"><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="00134" HREF="msg00134.html">RE: [MUD-Dev] players who "take away from the game"</A></strong>,
Koster, Raph <a href="mailto:rkoster#origin,ea.com">rkoster#origin,ea.com</a>, Sat 06 Nov 1999, 00:44 GMT
<LI><strong><A NAME="00132" HREF="msg00132.html">[MUD-Dev] ADMIN: Library goof</A></strong>,
J C Lawrence <a href="mailto:claw#cp,net">claw#cp,net</a>, Fri 05 Nov 1999, 23:40 GMT
<LI><strong><A NAME="00128" HREF="msg00128.html">[MUD-Dev] Server: Momoko</A></strong>,
J C Lawrence <a href="mailto:claw#cp,net">claw#cp,net</a>, Fri 05 Nov 1999, 19:06 GMT
<UL>
<LI><strong><A NAME="00129" HREF="msg00129.html">[MUD-Dev] Scripting in java... (was Momoko)</A></strong>,
Owen <a href="mailto:owend#obscure,org">owend#obscure,org</a>, Fri 05 Nov 1999, 19:45 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00125" HREF="msg00125.html">RE: [MUD-Dev] Spatial datastructures and their application (Was Re: Hilbert Curves)</A></strong>,
Lo, Kam <a href="mailto:LoK#logica,com">LoK#logica,com</a>, Fri 05 Nov 1999, 19:04 GMT
<UL>
<LI><strong><A NAME="00130" HREF="msg00130.html">RE: [MUD-Dev] Spatial datastructures and their application (Was R e: Hilbert Curves)</A></strong>,
Owen <a href="mailto:owend#obscure,org">owend#obscure,org</a>, Fri 05 Nov 1999, 19:56 GMT
<UL>
<LI><strong><A NAME="00131" HREF="msg00131.html">RE: [MUD-Dev] Majik (Was Re: Hilbert Curves)</A></strong>,
Owen <a href="mailto:owend#obscure,org">owend#obscure,org</a>, Fri 05 Nov 1999, 20:33 GMT
<UL>
<LI><strong><A NAME="00133" HREF="msg00133.html">[MUD-Dev] players who "take away from the game"</A></strong>,
msew <a href="mailto:msew#trilogy,com">msew#trilogy,com</a>, Fri 05 Nov 1999, 23:46 GMT
<UL>
<LI><strong><A NAME="00135" HREF="msg00135.html">Re: [MUD-Dev] players who "take away from the game"</A></strong>,
Matthew Mihaly <a href="mailto:diablo#best,com">diablo#best,com</a>, Sat 06 Nov 1999, 01:01 GMT
</LI>
</UL>
</LI>
</UL>
</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>