<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Room-based vs. coordinate-based -->
<!--X-From-R13: pynjerapNphc.uc.pbz -->
<!--X-Date: from stimpy.globecomm.net [207.51.48.4] by in4.ibm.net id 866141096.47376-1 Thu Jun 12 18:44:56 1997 CUT -->
<!--X-Message-Id: 199706121842.LAA15405#xsvr3,cup.hp.com -->
<!--X-Content-Type: text/plain -->
<!--X-Reference: 199706120154.SAA08439#pc4,zennet.com -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Re: [MUD-Dev] Room-based vs. coordinate-based</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="msg01309.html">Previous</a>
| <a href="msg01311.html">Next</a>
]
Thread:
[ <a href="msg01300.html">Previous</a>
| <a href="msg01318.html">Next</a>
]
Index:
[ <A HREF="author.html#01310">Author</A>
| <A HREF="#01310">Date</A>
| <A HREF="thread.html#01310">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Re: [MUD-Dev] Room-based vs. coordinate-based</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] Room-based vs. coordinate-based</LI>
<LI><em>From</em>: <A HREF="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</A></LI>
<LI><em>Date</em>: Thu, 12 Jun 97 11:04:53 -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="msg01300.html">199706120154.SAA08439#pc4,zennet.com</A>>, on 06/11/97
at 09:37 PM, "Brandon J. Rickman" <ashes#pc4,zennet.com> said:
>J C Lawrence (claw#null,net) wrote:
>>On 09/06/97 at 05:18 PM, "Brandon J. Rickman" <ashes#pc4,zennet.com>
>>said:
>>Thanks. I'll now go scrap a few thousand lines of proof-of-concept
>>code and head back to the deisgning board.
>>
>> <deeper bow>
>Are you trying to hold me responsible for such a rash action? :)
Certainly. Guido the kneecap driller will be visiting shortly.
Please don't struggle.
>>>So now we have <N neighborhoods scattered on a plane (or line, space,
>>>n-space, whatever). An object propagating an event only has to
>>>propagate in its neighborhoods (*) (which at worst would be _all_ of
>>>them).
>>
>>It would seem the rare case where an event would not be propagated to
>>all neighborhoods of an object.
>Ah, my comment was poorly worded. It would be a rare case for an
>event to propagate to _all_ neighborhoods, to the entire universe.
Ahh. This makes more sense. As you comment later the real problem
gets to be determining what neighborhoods that the object is not a
member of that an event should be propagated to.
>>Actually that level of removal could be many deep. It may well need
>>to propagate to its neighbors' neighbor's neighbor's...neighborhoods.
>>Consider the case of a long set of neighborhoods (a long passage
>>containing a line of many thousands of ants). A message at one end of
>>the tube should likely propagate to the other end.
>This is the kind of application that I was trying to deal with, a way
>to propagate messages - or radiate events. But with events the
>propagation may be blocked (intentionally) somewhere down the tree.
This is where I suspect putting something like an R*-Tree structure
over the top of the base neighborhood structure might prove useful.
>>Which means that 7 and 8 see the trick despite being at the corner
>>with 9, thru 12 who don't see the trick. There's a non-implicit data
>>loss there.
>One man's data loss is another's noise filtering. For 9-12,
>Shoehorn's trick-event is so much noise they don't need to see.
Change the scenario to:
Shoehorn is in a room,
There are two other players A and B in the room as well.
A is near shoehorn.
B is some distance away.
There are also 15 tiny or invisible objects in the room
near shoehorn (lint ball, a dropped cherry stone, etc).
The extra objects create the following neighborhoods:
#1{Shoehorn,...A}
#2{A,...B}
Shoehorn pulls a rabbit out of his hat.
The rabbit is too distant to be a member of #2.
#1 is too full to add the rabbit, resulting in:
#1{Shoehorn,...A}
#2{A,...B}
#3{Shoehorn, rabbit}
All the objects tiny, invisible, A, B, etc should see Shoehorn pull
out the rabbit. As far as A & B are concerned, it is the only thing
happening in the room, and as such is not drowned in detail (or 50M
rabbits).
>...It is probably an
>_unlikely and unintentional_ state, but when it does happen it needs
>an elegant resolution. ("Unlikely" because at any given time any
>given object probably isn't in two minimally intersecting
>neighborhoods, but there will almost always be some object somewhere
>with this property.) If the event propagation is clever enough, 7
>might choose to filter out a "weak" event (an event coming from only
>one/few of the object's many containing neighborhoods), while 8 might
>want the extra noise.
This raises a more interesting question:
Should an neighborhood filter the events that it presents
to an object?
or
Should an a neighborhood be compleatly transaparent to all
events and let the object determine what events it accepts?
There are advatnages to both sides.
>I was going to provide a mathematical diversion of how to split up
>large neighborhoods but I haven't convinced myself that what I want
>to do works. There's got to be a book on this problem somewhere.
Its a non-trivial problem. Essentially it devolves to the problem:
Given a graph with a defined random distribution of data points,
derive the minimum number and placement of circles of at least X
diameter required to enclose all data points, with the restrictions
that while circles may overlap, no circle may contain more than Y
datapoints.
It smells like a variation on the Travelling Salesman problem with
touches of Hamiltonian circuits.
Some messy points:
May more than one datapoint have the same coordinates?
If yes, then a general solution becomes impossible when Y + 1 data
points share the same coordinates.
Does the fact a datapoint lies within a circle's borders define it
as a member of that circle?
If yes, this allows handling of the most pessimal case where
datapoints are packed solidly into every possible (presumed integer)
coordinate point. You essentially end up with an overlapping
hexagonal tesselation of circles.
I suspect that a general solution for the most optimal answer is way
beyond both the available computational resources (esp given it has to
be dynamic), and unnecessary. A "pretty good" computationally cheap
approximation would likely do.
First hack:
1) Upon initialisation of the world pick an outlieing
data point.
2) Place it on the edge of a circle of X diameter.
3) Rotate the circle until a maximum (< Y) # of data points
are enclosed.
4) If this is impossible, shrink the diameter of the circle
by interger units until it is possible.
5) Pick another point <insert clever algorithm>
6) Repeat from #2 until no free datapoints left.
Requirements:
Y has to be larger than 5 to avoid unit circles.
A lot of brainwork can be profitably poured into #5.
After that mutate the neighborhood structure at runtime in the
cheapest possible manner. Have a background thread track
concentrations of such changes and re-semi-optimise the neighborhood
definitions at a low priority.
--
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>
<ul compact><li><strong>Follow-Ups</strong>:
<ul>
<li><strong><A NAME="01318" HREF="msg01318.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>
<ul compact><li><em>From:</em> Marian Griffith <gryphon#iaehv,nl></li></ul>
</UL></LI></UL>
<!--X-Follow-Ups-End-->
<!--X-References-->
<UL><LI><STRONG>References</STRONG>:
<UL>
<LI><STRONG><A NAME="01300" HREF="msg01300.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></STRONG>
<UL><LI><EM>From:</EM> "Brandon J. Rickman" <ashes#pc4,zennet.com></LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg01309.html">Re: [MUD-Dev] The laws of probability</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg01311.html">Re: [MUD-Dev] "From Kansas to Oz"</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg01300.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg01318.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#01310"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#01310"><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] Room-based vs. coordinate-based</STRONG>, <EM>(continued)</EM>
<ul compact>
<ul compact>
<ul compact>
<ul compact>
<ul compact>
<LI><strong><A NAME="01316" HREF="msg01316.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Fri 13 Jun 1997, 11:37 GMT
</LI>
<LI><strong><A NAME="01320" HREF="msg01320.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Miroslav Silovic <a href="mailto:silovic#srce,hr">silovic#srce,hr</a>, Fri 13 Jun 1997, 21:12 GMT
<UL>
<LI><strong><A NAME="01322" HREF="msg01322.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Jeff Kesselman <a href="mailto:jeffk#tenetwork,com">jeffk#tenetwork,com</a>, Sat 14 Jun 1997, 01:12 GMT
</LI>
</UL>
</LI>
</ul>
</ul>
</ul>
</ul>
<LI><strong><A NAME="01300" HREF="msg01300.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Brandon J. Rickman <a href="mailto:ashes#pc4,zennet.com">ashes#pc4,zennet.com</a>, Thu 12 Jun 1997, 08:54 GMT
<UL>
<LI><strong><A NAME="01310" HREF="msg01310.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Fri 13 Jun 1997, 01:44 GMT
<UL>
<LI><strong><A NAME="01318" HREF="msg01318.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Marian Griffith <a href="mailto:gryphon#iaehv,nl">gryphon#iaehv,nl</a>, Fri 13 Jun 1997, 13:28 GMT
</LI>
</UL>
</LI>
</UL>
</LI>
<LI><strong><A NAME="01326" HREF="msg01326.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Brandon J. Rickman <a href="mailto:ashes#pc4,zennet.com">ashes#pc4,zennet.com</a>, Mon 16 Jun 1997, 15:13 GMT
<UL>
<LI><strong><A NAME="01336" HREF="msg01336.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Wed 18 Jun 1997, 07:25 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="01517" HREF="msg01517.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Brandon J. Rickman <a href="mailto:ashes#pc4,zennet.com">ashes#pc4,zennet.com</a>, Thu 26 Jun 1997, 11:40 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>