[MUD-Dev] Re: Quadtrees?

[Greg Munt]

>From the archives, dated 27 Feb 1997... (Whats up with WebGlimpse, btw?)

> > [Wout Mertens]
> >
> > 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?
>
> [JCL]
>
> 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).

Why such a strong aversion to quad trees? Maybe this is illuminating my poor
understanding of R-Trees, but the two don't seem to be as different as the
degree of your aversion would attest. When you get down to it, they both
model the world, both starting from a general, 'big-picture', with child
nodes describing smaller and smaller areas, in more and more detail. Would I
be right in thinking that Q-Trees model only 1 aspect of the world, whereas
R-Trees (anyone know what the 'R' means, btw?) can model the world in its
entirety - and that this is why you don't like them? I think that you allude
to this, later on.. (Marked [1])

> 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.

Spatial characteristics - where an object is in the world, and in relation
to other objects?
Object characteristics - properties of the object, e.g. a hole knocked
through a wall?

> 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.

To clarify: high-level nodes define the object itself, lower-level nodes
define changes to that object? For example, a high-level node A might define
a window. If someone throws a rock through that window, node A gains a child
node, B, which defines a broken window. Would it be correct to say that the
further down the tree you go, the further into the future you go? Is this
how you do your database rollbacks? (I remember you saying that you can
rollback ALL parts of your world to a certain point in time, given suitable
disk space?)

> 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.

Could this be likened to a 2D grid, much like the 'wilderness' mode of those
old SSI (I think it was SSI.. Hmm..) AD&D games? I.e. Square (2,2) is
forest, square (2,1) is a plain, square (2,0) is a lake, etc? And you are
basically defining the gridlines themselves? As in, everything before this
point is a plain (until told otherwise), and everything after this point is
a forest (until told otherwise)?

> > > [Raz]
> > >
> > > 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?

This is something I strive for - a rich, detailed world. (Who cares if it
has zero playability.. *grin*) Conventional room-based worlds just can't
provide the effects that I desire. Inevitably this means that all parts of
the world have to have dynamic descriptions. Does anyone want to throw any
algorithms for generating *interesting* descriptions onto the list? I'm
thinking of something like a definition file, and then having multiple ways
of describing the same thing, for variation.

> > > > [Carter T Shock]
> > > >
> > > > From http://www.cs.cuhk.hk/~drsam/methods.html:
> > > >
> > > > [What is R-Tree]
> > > > [Properties of R-Tree]
> > > > [R*-Tree]
> > > > [VP-Tree]
> > > >
> > > > QUADTREE IMAGES by Bob Glickstein
> > > > [Q-Trees]

> 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 don't see the difference. Aren't "providing more and more finely grained
data" and "detailing more and more accurately what data sets define a
specific location" the same thing?

> 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.

Has anyone found anything out about Morton Codes since this post? (It was a
while ago.)

> My own thoughts I posted at the time:
>
> } 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.

So, the more that PCs/NPCs 'change' the environment (by construction, using
natural resources, etc) - or the more that natural disasters (floods,
earthquakes, volcanoes) occur in an area - the more nodes are required to
describe that area, and therefore proportionally more database space is
required to describe that area, over time, as things happen to/within that
area. Would any sort of database optimisation be beneficial here, including
things like predictions about which parts of the world will grow/become more
detailed.. or would any kind of generic database still be sufficient?

> 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.

OK... But my head can only see a 2D world represented, right now. Higher
nodes represent bigger MBRs... But these are *rectangles*, not *cubes*...
How would you, for example, represent an undersea city (cf Atlantis)?

> 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.

This sounds good, and cool, and all that... But it is bending my mind into
lots of wierd and wonderful shapes. Hyelp!

[Stuff about VRML snipped]

>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

I'd imagine smoke would be seen for a great distance - depending on the
surroundings of its source. For example, smoke from a fire in a forest
clearing might not be seen for as great a distance as one in a wide-open
plain.. Trees hide the smoke (not the smell however) to an extent. Anyhow,
you get what I mean. We need to be modelling these tall trees (i.e. we need
to be modelling 3 dimensions, and I don't see how to, with this model...),
so that we can tell (a) how long it takes for the smoke to get above the
trees, (b) who can see this now-thin smoke - people in higher locations,
especially if they were looking down on the trees, would have a greater
opportunity at doing this.

>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

So certain node types last for a specific amount of time, after which they
are replaced by another.. Underneath all that smoke, I smell events.

>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.

I just don't get how R-Trees can model the third dimension. Re: node types
discussed above, do you have a special node type for the z-axis?

Greg.



_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev