Quadtrees?

[coder at ibm.net]

On 28/02/97 at 03:53 AM, Wout Mertens <Wout.Mertens at rug.ac.be> said: >Hi
all,

>I am wondering why quadtrees would be so great for spatial representation
>as it is used in a mud. As you will remember, a quadtree subdivides a
>region into 4 subregions and makes quadtrees of those until the
>subregions are uniform, so that you only keep information about things
>that are different in a region (ok this desc stinks). But in a mud you
>need to do lots of spatial relation searches, like all the objects within
>a range of 3.
>Why not use a list of objects that is multi indexed on X and Y values?

Unfortunately I have to go confront the IRS, so I'll have to keep this
quick.  I think Quadtrees are a *very* bad way to approach spaces in MUDs
as they don't lend themselves to the type of spatial processing that I
think MUDs require.  My own temptation would be to go for something close
to an R*-Tree approach (see below).

The best idea I've come up with so far is two-fold.  One side describes
spatial characteristics, and the other side describes object
characteristics.  I seperate the two essentially as one defines _how_
space changes, and the other defines the behaviour of the contents of that
space.

The whole idea for spaces is that nodes are only stored where there is a
change in characteristic, with the contents of the node indicating _what_
changes, and in what direction from the node.  

Thus, taking the example of a land which is partly forested, and partly
grassy, The only nodes that would be defined are those needed to define
the border between them.  In this manner surfaces, boundaries, conditions,
topology etc can be defined with a minimum of data.  

An old post from the list may illuminate the general area (I think Carter
is a member here now?  Hope so -- we wrote good stuff in r.g.m.*).  It
actually says more about the stuff above than I have time for now.

--<cut>--
From: "Chris Lawrence" <clawrenc at xsvr1.cup.hp.com>
Date: Thu, 12 Sep 1996 12:36:18 -0700
Subject: Re: Rethinking Rooms (Very Long)

> From: raz at mushroom.demon.co.uk (Raz)
> Newsgroups: rec.games.mud.admin,rec.games.mud.misc,rec.games.mud.diku
> Subject: Re: Rethinking Rooms
>
> [Moved the following quote from the Mob thread into this one]
>
> It was all I could do to contain my excitement when Orion Henry wrote:

BTW I've invited him to join the list and set him subscription data in
reply to his request.  If he's not here now, he should be soon.

> > I've stuck with repops, but it's quite a bit more subtle.  That is,
> > the system looks at an EMPTY area and considers what needs to be
> > fixed - doors that should be locked, walls that should be repaired,
> > mobs that should be "born" to fill holes in the population.
>
> Just a part in that paragraph that reminded me of an earlier thing that got
> discussed:  It would presumably be nice to 'liven up' the playing
> environment, for example by allowing characters to hack paths through
> forests, rediscovering lost temples, etc, right?  Well, getting back to the
> challenge of auto-generating Spaces, I'm curious as to how these two ideas
> could be brought together efficently.

This has been tickling the back of my cranium as well.  I like the idea of
a stored mutating state for a generated space (or at least that's the way
I think of it.)

> To elaborate, the forest 'exits' (here the undergrowth blocking passage)
> could easily hold values such as resistence to damage and the ammount of
> hacking which is necessary to break through it, but this is only easy in
> rooms that are predefined.  In the so-called 'virtual spaces' that
> information could not be remembered though, because fields for this data
> wouldn't exist, and assigning those bytes regardless (in the array which
> maps coordinates to defined vnums) would be wasteful in the extreme, as in
> this case only forest Spaces would make use of it...

Which is probably the reason to explicitly NOT go in this direction. Its
wasteful in the extreme.

> I have a feeling I haven't explained that very well, but make what you can
> of it =)  Anyone have ideas on how a 'living environment' like that could be
> supported efficiently?  Perhaps I should say *other* ideas: bearing in mind
> Carter T Shock's detailed (and overpowering for a poor pleb like me! ;) )
> post regarding world storage.
>
> Raz

I've encluded Carter's post below as reference material.  I suspect that
your confusion sources to his references to R-Trees, Quad-Trees and the
like as that's what got me.  Both R-Trees and QuadTrees are typically used
in relation to image processing, but can be adapted for other uses.  Both
actually map very nicely (if somewhat indirectly for QT's) to mapping
auto-generated spaces.

Possibly some references on the area would help clear up the
definitions.

>From http://www.cs.cuhk.hk/~drsam/methods.html:
- --<cut>--
What is R-Tree

A R-Tree, proposed by Antonin Guttman[1], is an index structure for point
and spatial data at the same time. Insert, delete and search can be
intermixed without periodic reorganization. It uses a tuple to represent a
spatial data in the database. In order to retrieve the data, each tuple
has a unique identifier, tuple-identifier. At the leaf node of a R-Tree,
it has index record that can reference the spatial data. The index record
is (I, tuple-identifier). I is an n-dimensional rectangle and it is the
bounding rectangle of the spatial data indexed. This rectangle is also
known as minimal bounding rectangle, MBR. and each entry in
tuple-identifier is the upper and lower bounds, [upper, lower], of the
rectangle along the
dimension. Non-leaf nodes contain entries (I, childnode-pointer) where I
is the minimal rectangle bounding all the rectangles in the lower nodes'
entries. Childnode-pointer is the pointer to a lower node in the R-Tree.
Let M and m<=M/2 be the maximum and minimum number of entries can be
filled into one node respectively.

Properties of R-Tree

A R-Tree satisfies the following properties:

    A R-Tree is a height balance tree and all leaves are on the same
    level.

    Root node has at least two children unless it is the leaf node.
    Every non-leaf node contains between m and M entries unless it is
    the root.

    For each entries (I, childnode-pointer) in a non-leaf node, I is
    the smallest rectangle that spatially contains all rectangles in
    its child nodes.

    Every leaf node contains between m and M index records unless it
    is the root.

    For each index record (I, tuple-identifier) in a leaf node, I is
    the smallest rectangle that spatially contains the n-dimensional
    data object represented by the indicated tuple.

R*-Tree

The R-tree is based on a heuristic optimization. The optimization
criterion is to minimize the area of each enclosing rectangle in the inner
nodes. R*-Tree which incorporates a combined optimization of area, margin
and overlap of each bounding rectangle in the inner nodes was proposed in
[6]. For slightly higher implementation cost, it outperforms the existing
R-Tree variants.

    Minimizing the area covered by a bounding rectangle should
    minimize the dead space. This will improve performance since
    decisions which paths have to be traversed, can be taken on higher
    level

    Minimizing the overlap between bounding rectangles decreases the
    number of paths to be traversed.

    Minimizing the margin of a bounding rectangle will make the
    rectangle more quadratic. It is because for fixed area, the object
    with the smallest margin is the square. Quadratic rectangles can
    be packed easily and thus building a smaller rectangle.

VP-Tree

Conventional spatial index structures divide the multi-dimensional vector
space into partitions which have approximately the same number of data
points as each other. It facilitates in finding the nearest neighbor of a
given query point because it is only necessary to touch a small number of
partitions. Most partitioning methods are based on absolute coordinate
values of the vector space. R-Tree and R*-Tree described before use this
type of partitioning method. The structures partitioned in this way are
useful for queries based on absolute coordinates, like range queries.
However, in general, it does not maintain any distance information, such
as distance between points within a partition and the partition's
boundaries. Since this information is critical in pruning the search space
for
nearest-neighbor search, index structures using partitioning methods based
on absolute coordinate are thus not so useful for
multi-dimensional nearest-neighbor search.

Nearest-neighbor search by definition is to find out one point with
minimum point-to-point distance from a given query point, so it is natural
to use partitioning method based on relative distance rather than absolute
coordinate values. Vantage-Point tree, or VP-Tree, method was proposed by
Peter N.Yianilos. It uses the partitioning method based on relative
distance and aims for handling multi-dimensional nearest neighbor search.

As mentioned before, VP-Tree method bases the partitioning on the relative
distances among the data points, rather than their absolute coordinate
values. It also bases on a particular vantage
point. Actually, vantage point is nothing special but a point selected
from a vector space, or a set of data points. However, the choice of
vantage point plays an important role in the performance of indexing
algorithm.

- --<cut>--

And for QuadTrees:

- --<cut>--

QUADTREE IMAGES by Bob Glickstein

A ``quadtree'' is a means of encoding an image as a tree structure. Each
node of the tree has up to four children.  The root node represents the
entire image; its children represent the four quadrants of the entire
image; their children represent the sixteen subquadrants; the children of
those represent the sixty-four sub-subquadrants, and so on.

A leaf node corresponds to a single pixel, and is marked with the color of
that pixel (in this implementation, black or white only).  If a non-leaf
node has two or more children of the same color, then that color is stored
in the parent and the children are deleted.  Thus, if an entire quadrant
(subquadrant, sub-subquadrant, etc.) of the image is white, that
information can be stored in a single quadtree node, and all of the
children of that node can be removed.

For certain images, this encoding yields enormous savings in storage size. 
Such images are typically line drawings or other bitmaps with several
areas of solid black or white.  Images with a lot of dithering or
stippling, such as scanned images, tend to yield little or no savings in
space.

An amusing aspect of quadtrees is that they can be displayed according to
a depth-first or a breadth-first traversal of the tree.  In a depth-first
traversal, first the prodemonant color of the entire image is displayed;
then the predominant color of the first quadrant is displayed; then the
predominant color of the first subquadrant of the first quadrant, and so
on.  The user can watch the quadrants and subquadrants being drawn.  A
breadth-first traversal, however, is much more interesting.  Since it
displays first the predominant color of the entire image, followed by the
predominant colors of the four major quadrants, followed by the
predominant colors or the sixteen subquadrants, and so on, the effect is
one of a gradually resolving image with finer and finer detail at each
step.

- --<cut>--

Or to look at it another way, R-Trees, VP-Trees, and Quad-Trees provide a
tree data structure where walking the tree from the root node down towards
the leaves provides finer and finer grained data about the location, with
each system providing various optimisations for that progression.  For
QT's the progression is exactly that of providing more and more finely
grained data.  For R-Trees and the like, the progression is that of
detailing more and more accurately what data sets (nodes) define a
specific location or area.

I've not been able to find a good source for what he describes as "morton
codes", tho I have run into the concept before (and don't remember any
implementation details or algorithms).  <<Can anyone help here?>>  However
I think the concept he describes is fairly clear and understandable.

My own thoughts I posted at the time:

} Another option, which could be done as an extension of your idea for
} the mapping/surface portion, is to avoid the concept of continuous
} mapping.  Instead only those specific coordinate points (cells) would
} be defined which deliniate changes in pattern in the
} surface/map/object.  Additionally a cell could define its linkage, or
} lack of linkage, and the character of that linkage, with other
} immediately proximate points
}
} In this way the map would be be a net of defined points and
} interpolations between those points.  A sparsely detailed area would
} consist of very few defined points and render/access quickly.  A high
} detailed area would have far more defined points and could provide a
} computational challenge.

In a crude sort of way you could consider this derived from fractal
compression, or at least the concept of a node which marks a change of
characteristic, and having that node also indicate the quality of the
changed characteristic when moving in various directions from the node
bears some resemblance.  (eg The node says that this the edge of the
water.  Everything to the south and down of the node is water, and
everything else in every other direction is not water)

I believe this could be extended in line with Carter's system to offer a
pretty slick system.

Consider a system ala:

  Nodes are only stored if the _location_ of that node indicates a
    change in character in whatever that node is describing.

  If the characteristic being described is water, there would be nodes
    located along the edges of the body of water, but ONLY where the
    direction of that edge changed direction.  If the character of the
    water changed within its space (eg colour, waves, etc) nodes would
    only be present at the locations where the characteristic changed.

  Thus there would be nodes all around edge of the area where the
    water changed from blue to green, with only just enough nodes to
    define the shape of that area.

  Store the nodes in say an R*-Tree as described above, and finding
     the the nodes which affect the view of a player located at
     specific coordinates is just a matter of descending the tree
     until finding a node which is larger than the player's view, but
     whose children are smaller than the player's view.  Then just
     descend from there to define the area.

Now add in the concept of having multiple trees, with each tree
representing a different characteristic of the "land".  Say one tree could
be weather, another could be object locations cross linked with object
descriptions/definitions, a third could be light level, another define the
surface of the land etc.

You could even cross-link the trees to each other to help quickly locate
the nodes relevant to a given area.  Heck you could actually just make it
one R*-Tree and have each node be one of a variety of types so that as the
tree is descended the different types fill in as their unique
characteristics change.

Thinking about this has gotten me thinking further about the
possibilities of a true graphical MUD ala VRML.  I could see definite
possibilities for coding an R*-Tree of the VRML descriptions of the
various objects in game, and then following an algorithm something like
this to draw the image for the end user:

  Presuming that the structure of VRML supports some concept of detail
  level, and thus the ability to retrieve only the relevant data about
  an object at a given detail level (eg you can't see the crags on the
  mountain in the far distance, but you can when you are close to it):

  From root of tree, descend tree.

  For each node, determine the spatial distance of that node from the
  player.

  If "close enough", get data from that node at the resolution level
  comparable for the distance to the node.  ie of the node is close,
  get highly detailed data.  If farther away, get less detailed.

  Draw and render as appropriate, rezz'ing in the image.

Noting again that I don't know squat about VRML, or if it would lend
itself to this at all.

None of this of course registers the _change_ to the location because of
recent events there (eg hack down the trees).  This could be done by
inserting nodes in the R-Tree to define new changes in characterisitic. 
Consider the case of two nodes:

  NodeX<---distance--->NodeY

NodeX is defined as light scrub for everything east of it.  NodeY is
defined as heavy forest for everything east of it.  (I'm simplifying a lot
here, as normally each node would also define its relationship to other
proximate nodes).

A player happens to be standing somewhere in the light forest, and lights
a fire.  There is now a smoke plume, and so a new node is created.

  NodeX(scrub)<--->NodeZ(smoke)<--->NodeY

Later on he walks a bit and hacks out a clearing:

  NodeX(scrub)<--->NodeZ(smoke)<--->NodeQ(clearing)<--->NodeY

After a while the fire he started burns out, leaving a charred area:

  NodeX(scrub)<--->NodeR(charred)<--->NodeQ(clearing)<--->NodeY

Of course in actual fact the structure would be a heck of a lot messier
than this, as the smoke plume would have to have boundaries, and would
have considerable height.  This it would probably be decribed by say half
a dozen nodes sketching out a circle (the base of the plume) and a series
of matching nodes describing how the plume ascends thru space.  Similar
would be true for the clearning, and ultimately for the charred area when
it replaces the smoke.

| From: ctso at umiacs.umd.edu (Carter T. Shock)
| Newsgroups: rec.games.mud.admin,rec.games.mud.misc,rec.games.mud.diku
| Subject: Re: Rethinking Rooms
|
| In article <840439466.9428.1 at mushroom.demon.co.uk>,
| Raz <raz at mushroom.demon.co.uk> wrote:
| >[Conversation moved from 'Skill-based systems' to here =) ]
| >
| >representing the whole world on a matrix of 1m x 1m squares... =)
| >
| [snip]
| >
| >Yep, plus it's a sod to map, and the values on the axes would get
| >astronomical (imaging mapping a world the size of Earth with 1m x 1m
| >units... circumference is, what, 35000kms?  Ouch.)
| >
| [snip]
| >Oh, while I remember: my rambling diatribe above doesn't even begin to
| >include the joys of the Z axis! =)  It's no problem at all to allow players
| >to fly over any of the outdoor locations in the game,
|
| >From the player's perspective, yeah, it could be a bear to map, but
| then maps (and movement) could be more natural. If we're going to
| allow the player to sight distant objects, then it is reasonable to
| have them map by landmark. (follow the river until you see the
| mountains.. etc. perhaps an orienteering skill? :)
|
| The only other obstacle appears to be disk storage and granularity of
| your grid. In short, the 1m x 1m granularity poses no special
| problems. You can even go smaller if you want. The trick is to map
| only "what's there".
|
| I'm kind of excited to have stumbled on this topic, as I've started to
| build the rudiments of such a toy. The basics go like this:
|
| Assume for the moment that we've got a 1m x 1m gridding of the
| world. We'll talk about how to store it efficiently in a minute.
|
| Rather than keeping all known information about the world in a single
| grid with each cell having lots of attributes, we'll break it up into
| several layers. One layer can be a resource map (description of where
| ores and other fun raw materials are found). Another can be forest
| cover, a third can be water. Each of these can be represented as a
| collection of regions. i.e. there is absolutely no reason to go thru
| the damned grid and mark every single cell as "water" or "not-water".
| You just declare it as a region and throw it into an appropriate
| structure (like a region quadtree or an R-Tree). These fancy spatial
| data structures can store off the whole world in very little space.
|
| For buildings and such, store them as polygons in either an R-Tree or
| a PMR-Quadtree. Again, no reason to ever store off the explicit cells
| in the grid, only those objects that are in the cells.
|
| Elevation is a bit trickier. If you maintain the previous data
| structures in 3-D they can get kinda big, and the average world
| doesn't tend to have many discontinuous tall features (not too many 1
| meter square, mile high objects floating 100 feet off the ground)
|
| You can do elevation with additional region maps, one for each step in
| elevation. Limit things by saying your people can only fly so high
| before the air runs out or dig so deep before they hit magma and fry.
|
| So, how much space does it take to encode a point in an earth sized
| world on a 1m x 1m grid? First things first, cheap and dirty way to do
| a round world as a flat representation is to generate a square matrix
| and stand it on one corner (like a diamond). Moving from square to
| square is trivial except for the edges where you need to wrap the same
| "latitude". Again not hard, but you have to do it. Each cell needs a
| unique code. The earth is about 40,000km around at the equator.
| Let's make it a 40,000km sphere.
|
| 40,000,000m / (2^32) = .009
|
| So, if we grid the earth using a long integer, minimum granularity is
| what? 9 millimeters?
| So, "longitude" and "latitude" are longs.
| Altitude...
| Make the earth's crust and breatheable atmosphere 20 miles deep/high
| ~100K feet
| ~33km
| 2^15 = 32K
|
| So, with a vertical granularity of 1 meter, you can do about 40 miles
| with a 16 bit short.
|
|
| The final trick is coming up with a way to store this stuff off on
| disk such that you can get it back in a hurry. Bonus points if you
| come up with location codes for objects (rooms, structures, people)
| that result in objects that are spatially close being stored close
| together out on the disk.
|
| Again, trivial. Any space filling curve will do. Morton codes
| are easiest. It works like this:
|
| given an x,y,z location, interleave the bits of the three values
| to produce a single key, then sort all objects using that key.
|
| Example: using just x = 5, y = 3
| x = 0101
| y = 0011
|
| y-major code = 00011011
| x-major code = 00100111
|
| The beauty of this is that the code preserves in its most significant
| bits the most significant bits of the individual pieces that were used
| to make it. It's also nice because you can do range searches. To find
| all objects in the list in a 4m x 4m area (assuming a granularity
| of 1m) you search the list with a key like: 1001XXXX The key matches
| any code with 1001 as the first 4 bits and anything in the last 4
| bits. So things like "this sound can be heard for 30 meters" and
| "everybody within a mile radius dies" become trivial.
|
| Sorry about the length, but it really is pretty easy to store a highly
| detailed world without using up gobs of space.
| 	-Todd
| ..
| |-------------------------------------------------------------------------|
| |      Carter T. Shock          |        University of Maryland           |
| |    ctso at umiacs.umd.edu        | Institute for Advanced Computer Studies |
| | "Onward through the fog..."   |      #include <std/disclaimer.h>        |
--<cut>--

--
J C Lawrence                               Internet: claw at null.net
----------(*)                              Internet: coder at ibm.net
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...