February 1997
- Its nice to be back Nathan Yospe
- Its nice to be back coder@ibm.net
- Its nice to be back Nathan Yospe
- Testing coder@ibm.net
- Invitation to MUD Design Mailing List Chris Gray
- Invitation to MUD Design Mailing List coder@ibm.net
- Invitation to MUD Design Mailing List coder@ibm.net
- Invitation to MUD Design Mailing List coder@ibm.net
- Invitation to MUD Design Mailing List coder@ibm.net
- Wout's mailing list and old digests coder@ibm.net
- Wout's mailing list and old digests Wout Mertens
- Wout's mailing list and old digests coder@ibm.net
- Just a bit of musing Nathan Yospe
- Just a bit of musing Adam Wiggins
- Just a bit of musing coder@ibm.net
- Just a bit of musing Chris Gray
- Just a bit of musing Carter T Shock
- Just a bit of musing Chris Gray
- Just a bit of musing S001GMU@nova.wright.edu
- Just a bit of musing Dmitri Kondratiev
- Just a bit of musing Chris Gray
- Just a bit of musing Dmitri Kondratiev
- Just a bit of musing coder@ibm.net
- Just a bit of musing Jon A. Lambert
- Just a bit of musing coder@ibm.net
- Just a bit of musing coder@ibm.net
- Just a bit of musing clawrenc@cup.hp.com
- Just a bit of musing coder@ibm.net
- Just a bit of musing Carter T Shock
- Just a bit of musing Alex Oren
- Just a bit of musing Wout Mertens
- Just a bit of musing coder@ibm.net
- Just a bit of musing coder@ibm.net
- Just a bit of musing Wout Mertens
- Just a bit of musing Carter T Shock
- Just a bit of musing S001GMU@nova.wright.edu
- Just a bit of musing Chris Gray
- Just a bit of musing coder@ibm.net
- Just a bit of musing Nathan Yospe
- Just a bit of musing coder@ibm.net
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Adam Wiggins
- Just a bit of musing coder@ibm.net
- Just a bit of musing GnomesHome@aol.com
- Just a bit of musing Carter T Shock
- Just a bit of musing Chris Gray
- Just a bit of musing coder@ibm.net
- Just a bit of musing Adam Wiggins
- Just a bit of musing Chris Gray
- Just a bit of musing Adam Wiggins
- Just a bit of musing claw@null.net
- Just a bit of musing Chris Gray
- Just a bit of musing claw@null.net
- Just a bit of musing Chris Gray
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Chris Gray
- Just a bit of musing Carter T. Shock
- Just a bit of musing claw@null.net
- Just a bit of musing Wout Mertens
- Just a bit of musing coder@ibm.net
- Just a bit of musing Adam Wiggins
- Just a bit of musing coder@ibm.net
- Just a bit of musing Chris Gray
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Chris Gray
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Chris Gray
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Travis Casey
- Just a bit of musing Jon A. Lambert
- Just a bit of musing clawrenc@cup.hp.com
- Just a bit of musing Nathan Yospe
- Just a bit of musing clawrenc@cup.hp.com
- Quadtrees? Wout Mertens
- Quadtrees? coder@ibm.net
- Quadtrees? Greg Munt
- Quadtrees? Ola Fosheim Grøstad
- Quadtrees? Ling
- Quadtrees? Miroslav Silovic
- Quadtrees? Chris Gray
- Quadtrees? Carter T Shock
> previous example, you could use one quadtree for 'forest-ness', another
> for 'mountain-ness", etc. This allows you to automatically generate the
> description/picture/representation of a location in the grid, based on
> traversing the small quadtree to get the property value.
exactly
>
> Objects are a different matter. They are each individual, and possibly
> unique. With objects, the concern is more "what objects are here?". An
Two points:
1) Quadtrees are not the be-all and end-all of spatial data structures.
Just what came to mind as I wrote.
2) Quadtrees come in lots of flavors.
The "forest-ness" et. al. would most likely be done as a region quadtree.
It just works out that these are handy structures for binary spatial tests.
Any region is either forest or it ain't. The particularly nice thing about
these structures (versus other representations) is the ability to perform
efficient spatial joins. Recall that you can use these puppies for more
than simple terrain. If you support clans you can describe a clan's "zone
of influence", you can do no magic, lawful, silent, safe, etc. areas. The
spatial join property is more of an implemetor's bonus. It lets you ask
questions like "show me all of the areas that are forest but no-magic" so
you can tune those spots where (ferinstance) druid spells will fail.
As far as objects go, their are various point-based structures that come to
mind including the sparse matrix, K-D trees, and point-based quadtrees.
Depending on how fancy you want to be, it's handy not only to ask "is there
an object here?" but it is also handy to look for the nearest object from
here.. let's you do things like bring critters to life only when folks
approach (or leave), also let's you determine a range for how far folks can
hear things that hum, see things that are lit, etc. The classic
implementation is pointer-based, but for large implementations (and we
expect to index several thousand items) there are linear implementations.
Basically you implement a B-Tree and then use some space-filling curve
(Peano, Hilbert et. al.) to index the tree's contents (your objects). The
Peano or Morton curve is particularly nice 'cuz you can do algebra on it
and the code also implicitly tells you the depth and quadrant of the
corresponding pointer-based tree. The B-Tree behavior works well for a mud
cuz usually huge chunks of your world aren't being played... so you just
cache the active nodes/pages of the tree. Insertion and deletion can be
expensive, but there are all sorts of ways to fudge things so you don't
rebuild the tree every time. For rooms (walls etc.) the tree becomes
read-only. Or am I going way overboard here?
-Todd - Quadtrees? S001GMU@nova.wright.edu
- Quadtrees? Carter T Shock
- Quadtrees? S001GMU@nova.wright.edu
- Quadtrees? coder@ibm.net
- Quadtrees? Carter T Shock
- Quadtrees? Chris Gray
- Quadtrees? Carter T Shock
- Quadtrees? coder@ibm.net
- Quadtrees? claw@kanga.nu