[MUD-Dev] Re: Hex-grid mapping (fwd)

[J C Lawrence <claw#under,engr.sgi.com>]

On Thu, 3 Dec 1998 11:15:45 -1000 Nathan F Yospe<yospe#hawaii,edu>
wrote for sunnywiz#radiks,net:

> I don't have posting permissions...

We'll have to see about that.

> "Tesselation" of a sphere using UNIFORM shapes is a pretty hard
> task.  

Rephrasing: Tesselation of an arbitrary "sphere" with uniform shapes
of constant size is damned near impossible if not factually
impossible.  There are regular sphere-proximate shapes, such as the
well known dodecahedron and a few others which Nathan has referenced
which are both well known and work very nicely (I make no comments
on their ease of manipulation).

  The bitch is: "I want regular tesselation shapes of size X and,
umm, a sphere of size Y.  How do I do it?"

There is *NO* answer to the question if the ratio of X:Y is
arbitrary (ie known tesselation unit size, unknown sphere size, or
visa-versa).  In fact, there are only answers to that question for
very specific values of X:Y (such as for a dodecahedron*), and the
actual shape of X varies with eaach ratio (note that a cube is a
valid if crude tesselation of a sphere-proximate shape).

  * Computing out the value of X:Y for a dodecahedron is left as an
exercise for the reader

> According to one source (Hipparchus GIS library introduction) its
> pretty much impossible - end up with a bunch of hexagones and one
> pentagon.  If one were to relax the rules, though, one could use
> non-uniform tesselations, and the problem becomes much simpler.
> The method that source goes into is using Voronoi cells.  (wish I
> could give you a link.  Its supposed to be pretty standard).

I've attached a GIF of a sphere so tesselated to this message, taken
from:

  http://www.voronoi.com/application.htm

The following:

  http://www.cs.unc.edu/~turk/reaction_diffusion/rd_steps.html

gives a fairly simple algorithm for generating Voronoi poly maps for 
an arbitrary (and known) surface.  There's some more interesting
links on this under:

  http://www.cs.unc.edu/~turk/reaction_diffusion/reaction_diffusion.html

And the movies under:

  http://www.ccsf.caltech.edu/ismap/image.html

are peculiarly disgusting and amazing.

There's quite a bit of data out there on Voronoi, but nothing
comprehensive to my aging geometry skills that I've found yet.  A
good definition of a Voronoi region however can be found at:

  http://www.cast.uni-linz.ac.at/vision/Papers/visgeo-95/visgeo-95/

--<cut>--

From all the definitions, we consider that the Voronoi neighborhoods
provide an intuitively appealing definition of the neighborhood of
an image element, namely, the neighborhood which corresponds to that
portion of the Euclidean plane which is closer to any given image
element than to any other. ...

--<cut>--

A good discussion, if very particular in its focuse can be found at:

  http://ndsun.cs.ndsu.nodak.edu/www/ORION/report1.html

and concerns the problem of computing the path that a Remote
Autonomous Vehicle (RAV) will follow in moving from A to B across a
field of various hazards (ie don't drive over the mine field).  I
found this discussion particularly useful from the viewpoint of the
following scenario:

  Bubba is a player.

  Boffo is a NPC.

  The world is a coordinate space (as versus rooms model, which is
actually a huge directed graph).

    > l at me
    You are Bubba.
    > l
    You are standing in the center of the courtyard at Castle Krak.
    > tell boffo "Hey, Boffo, where are you?"
    Boffo tells you, "I'm in the Elven Forest."
    > tell boffo "I'm in the courtyard at Castle Krak.  Come here!"
    boffo tells you, "Okay."

  How do we, ie the MUD system, intelligently move Boffo the NPC
from the Elven Forest to the courtyard of Castle Krak in a
reasonably efficient manner?  (ie no recursive descent crow's-flight
algorithims).

This is *exactly* the point that this paper discusses a solution to.

Note that this is actually a variation of the problem more typically
solved with "speed walks", ie a player knows where he is and where
he wants to go and doesn't necessarily know verbatim the command
sequence required to get there from here.

  "I'm in the kitchen and I want to go to the attic, why can't I
just type, 'goto attic' and have the game take me there?"

Of course the paper assumes that the computer is omniscient, which
is a bitch for a game where we want the data set available to the
NPC to be fragmentary and augmented in (fairly) real time by what
the NPC can see.  eg:

  The NPC knows to go down the road to get to the Castle, but the
road is flooded by a stream at one point, blocking his path.  The
NPC encounters the stream, determines that he cannot ford the
stream, and notices a felled tree spanning the stream some ways
away.  The system then regens the Voronoi diagram with this new data
set and the path is recomputed to cross the stream via the felled
tree.

Other links that hit this area enclude:

  http://www.eecs.tulane.edu/www/Jennings/papers/map-making.ps

Another reasonable discussion can be found at:

  http://www.research.microsoft.com/research/graphics/hoppe/siggraph96bspline/node4.html

which seemed interesting for world/object mapping/drawing sofware,
but that's a seperate concern.  There are some other pretty good
(haven't read them all yet) stuff under:

  http://www.cl.cam.ac.uk/users/pjcb2/Publications/index.html

OTOH this is utterly fascinating from another perspective:
neighborhoods.  Have a look at the attached JPEG (the monochrome one
with the dots and surrounding ares), taken unreservedly from
http://www3.sympatico.ca/olanglois/voro.html.

This gives a new potential definition of a dynamically generated and 
defined neighborhood:

  1) Generate a Voronoi map for your object distribution.

  2) Starting with a random point on the map, aggregate adjacent
Voronoi areas around that location until the total aggregate area
equals or exceeds Y (where Y is a pre-defined threshold value), or
the total number of enclosed points exceeds Z (where Z is a
similarly pre-defined threshhold value).

  3) Further qualify the selection of aggregated areas to attempt to 
make the resultant neighborhood as close to circular as possible.
This is a lot easier than it sounds:

    a) From the initially selected point, select the point on the
nearest boundary of the surrounding polygon which is closest to the
selected point.

    b) Aggregate the polygon on the other side of that point with
the current polygon.  

    c) Repate from #a with the new aggregated polygon.

    (its crude, its very approximate, but its probably good enough).

I've attached an GIF (looks like a green/red board with red areas
around green blobs) that sort of shows the sort of thing I'm talking
about, taken from:

  http://www.cosy.sbg.ac.at/~held/projects/voronoi_2d/voronoi.html

The remaining problem is determining when the map should be regenned
due to object motion, and then how the map should be regenned (local
resolution (ie hack a semi-fit that doesn't break too many Y/Z
rules), or a semi-global regen).  Sample problem scenario:

  There is a field.  It is full of hoppity bunny rabits.  Lots of
them.  They are also multipling fairly rapidly (gestational rate
measured in seconds, Okay?).  They are hip hopping about the field,
in semi-random fashion, forming and disolving localised flash
crowds (ie the distribution is highly uneven and changes dynamically).

  There is a travelling herd of deer.  Being deer, and being fairly
flighty sorts, they are very loosely grouped, but are all generally
travelling in the same direction.

  The herd of deer crosses the field of bunnies.

  If you really want, the bunnies can be suffering from periodic
attacks of myxomatosis and as such suffer from periodic mass
die-offs (ie no infinite population explosions)

The field of rabbits is already a neighborhood problem.  The
constant motion of the rabbits means that the neighborhoods which
are defining the computationsl/range groups for the bunnies need to
be regularly regenned.  The bunny breeding means that any one
neighborhood won't survive long as its internal population growth
will cause it to be split fairly soon.  The deer pass thru and, in a
wave travelling across (part of?) the field of bunnies, cause
everything to be very rapidly regenned as the localised combos of
bunnies and deer utterly nuke the prior maps.
  
> Gives you irregular tesselation with all kinds of really cool
> properties that make things really fast for finding data/cell
> memberships, intersections, neighbors, etc.

Aye, I've noticed a couple commercial libraries for manipulating
such, that claim high performances.  I haven't looked (yet) for
anything Open Source on the area.  It strikes me like Colour
Management Systems: Really hairy, boring, intricate math with lots
of special cases and not a whole lot of cool factor.

> Mudwise, it translates to having a sphere broken down into
> (roughly) square, pentagonal, and (mostly) hexagonal shapes (which
> could easily be rooms, or "visible areas").  

<nod> The attached GIF, referenced above, shows this clearly.  From
the vantage of a client rendering the view via tiles this gets
*REALLY* interesting (and hell for your underpaid artists).

Consider the problem of drawing a castle which has been placed on
such a sphere, where the castle spans a moderately large number of
polygons...

> The shapes are not symmetrical(? - all sides being equal is what I
> mean), 

"Regular" is the term I'm familar with for this concept.

> but to the eye, they look pretty good.  And in the case of varying
> densities of information, the cells can be dynamically split down
> in size.  And its VERY fast.

Do you know of any available code bases for this?  I'm aware of
Hipparchus, but am looking for something OSS (oughta go check the
C++ libraries FAQ).

-- 
J C Lawrence                              Internet: claw#kanga,nu
(Contractor)                             Internet: coder#kanga,nu
---------(*)                    Internet: claw#under,engr.sgi.com
...Honorary Member of Clan McFud -- Teamer's Avenging Monolith...

Voronoi image

Voronoi sphere

bunny beighborhood