[MUD-Dev] Senses & geographical events

[Chris Gray]

[Wout:]

...

:I propose that all the objects that can sense that signal, are put in
:sorted lists:
:
:One list for the leftmost x-coordinate of the squares and one for the
:rightmost x-coordinate.
:
:Each entry contains a list for topmost y-coord and a list for bottommost
:y-coord, and of course those entries refer to an object.

...

:The lists should be something that is efficient in searches, and inserts
:can be priceier (sp?). Note that it is normally less pricey to move an
:entry in the list than to insert it, so you insert when an object enters
:the plane and move when the object moves or changes sensitivity.

...

:Thoughts?

This is starting to sound a lot like something I've had vaguely in mind
since I first started dreaming about full multiplayer 3D worlds something
like 15 years ago (I think I mentioned a bit about that in Wout's list).

I deliberately didn't think in any detail since I knew I didn't have a
computer or system powerful enough to use it (I was on CP/M then). The
basic concept is that the whole world would be positionally represented
by a 3D graph. There would be links in all six directions from each object
to one or more objects that are closest in that direction. (Already you
can see that I've never worked out the details!) The goals were several:

    - to be able to traverse the structure when displaying the scene,
        finding out what obscures what in the direction the player is
        looking
    - to be able to find what is close to what, ala the neighbourhoods
        being discussed on the list
    - to have reasonable costs for these searches, and for moving things
        around in the structure, and adding/deleting them
    - to have the entire structure not have to have a lot of changes
        continuously as a few things move around, so that not many of
        the nodes of the graph (or associated structures) are "dirtied"

I think I was planning on objects of all sizes being in the graph,
including things like mountains. Clearly, some warts would be needed to
handle container-type objects (just allow overlapping objects?)

There are more questions than answers in this, but that's because I haven't
thought about it for more than a few seconds! E.g.:

    - you've got a long wall sitting on the ground. There is an orchard
        to the north of it. What objects are north of the wall, and how
        is that set represented? In general, objects are not nice regular
        cubes - what special representations work best for them?
    - if large objects like mountains are represented, they need to show
        up in the graphical display even when they are a long way away.
        Some kind of hierarchical representation might be best for that,
        so that you can find small objects in the lower-level hierarchies,
        and then progressively move up in the hierarchies, looking for
        larger objects that can be further away but still visible. Can this
        be done by adding a fourth dimension to the graph? Details?
    - you need to find things like buildings before you find the stuff
        inside the buildings, even though the center point of the building
        is further away from you than many of the objects in the building.
        How is this done - via searching the above higher-levels first?
    - I'm sure there are a billion more, but I just got out of bed...

Am I completely out to lunch on this? Is this some kind of structure that
is well known in graphics circles? It's sort of like quad trees, but
differs in being a graph rather than a tree, and isn't any where near as
well defined. Anyone got any references to something like this?

--
Chris Gray   cg at ami-cg.GraySage.Edmonton.AB.CA