[MUD-Dev] Room-based vs. coordinate-based

[clawrenc at cup.hp.com]

In <199706120154.SAA08439 at pc4.zennet.com>, on 06/11/97 
   at 09:37 PM, "Brandon J. Rickman" <ashes at pc4.zennet.com> said:

>J C Lawrence (claw at null.net) wrote:

>>On 09/06/97 at 05:18 PM, "Brandon J. Rickman" <ashes at 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 at null.net
(Contractor)                           Internet: coder at ibm.net
---------------(*)               Internet: clawrenc at cup.hp.com
...Honorary Member Clan McFUD -- Teamer's Avenging Monolith...