node-based 3D coord systems

[Nathan Yospe]

A couple of members have expressed interest in 3D coordinate systems, or
coordinate systems in general, in the last few weeks. The two systems that
follow are both based around what I call "nodes", though their approaches
are significantly different. The first is my concentric/adjacent/connected
system for Physmud++, a hardcoded part of the design that is as much
conceptual as geographical. The second is the rigid grid of my GURU
project, which uses units of fixed size (a cube approx. 10m on a side) and
a (Q-ish)tree based access and compression system. Both address several of
the issues brought up in other posts, and allow for range and lockless
concurency management (though each has limitations - the GURU system has
an event horizon beyond which effects propogate only upon access, or in
the presence of players, thus eliminating things like volcanic effects
being seen for miles with no players present... I may eventually create
daemons capable of generating their own event threads to handle such
things... and the Physmud++ system has to invoke a top-down lock on all
threads lower on the concentricity heirarchy whenever an event ripens in
a non-empty domain (such as a room with a box in it, where the box
happens to have been designed with an active event node of its own).)

In any case, here they are:

Locations and nodes in Physmud++:

The node class has three purposes:
- Contain (and track position of) Physical and Informational objects, and
  track boundaries to concentrically and spacially neighboring nodes
- Handle events for the current location level, including thread
  management*
- Pass objects to and recieve objects from boundaries**

* "threads" means objects capable of holding an OS thread. Threads in
Physmud++ need not actually contain an OS thread at any particular point
in time, and a single OS thread (process) could be used to service the
entire mud, reducing to the lower limit of totally process managed
threads, or, at the opposite extreme, every thread could encapsulate a
seperate OS thread.

** Boundaries borrow processing incentive from the nodes on either side.
Effectively, each boundary is two objects, one in each node, which share
common variables, but effectively bypass the need for locks on the threads
on either side.

A sample world (I'll do a few types) could look like a Diku/Tiny/LP, with
world, zone/areas, rooms, and for the hell of it, roomlike containers in
some of the rooms.

The world would be a single node, with no adjacent nodes, no concentric
external nodes, and a concentric internal node for each area. The spacial
presence of the world is null, which means nothing will fit directly
within the world. Global events can be executed by the world, but rarely
occur, and alert the admins whenever they do, as they effectively render
the entire mud (sans socket related threads) monothreaded. The world would
have a spacial dimension of null as well, as it requires little else, with
no boundaries to worry about.

Each area would be a single node, with adjacent areas becoming adjacent
nodes (determined by the presence of boundaries, which are effectively
directly linked to the room-to-area boundaries that pass out of the edges
of the area), and with a spacial presence of null. Area wide events are
uncommon, as they effectively render the entire area temporarily single
threaded. Area wide events log their occurances, but, as they include such
things as broad weather conditions, do not immediately notify admins,
unless they are watching that particular event type (see wiznet
descriptions). Areas contain a concentric internal node for each room.

Each room would be a single room, with a spacial presence determined by
the size of the room and adjacent linkage (boundaries) to each neighboring
room, whether there is a door there or not. Local events are queued, and
because the queue is chain-linked (think newsgroup threads), events
relating to a particular content object are moved or destroyed with that
object, and destroyed if multiple dependancies are seperated.


Alternatively, there is the roomless model.

The universe is the outermost node, again. Under that are worlds, which
have a generic form (say, for example, desert or ocean over rock) managed
by the world's node, and using a derived node object of type field (one of
the predefined types)... within that field are spaces that are not part of
the generic form of the world - an outpost or an island, for example -
that are composed of discreet fields, each based on the constitution of
that expance. The island may be formed of jungle, beach, and rock... the
outpost may actually be steel walled rooms (rooms are another predefined
type, thus getting around the ackwardness of creating them in a coord
based system.)

As you can see, a highly flexible system, overall. It gets even better
when the boundaries' ability to pass sensory information seamlessly (or
not so seamlessly, as might be the case for a glass boundary and scents)
between node regions. The predefined physical nature of the universe, and
the fact that, in most cases, telling the system the material and
dimensions of an object are sufficient to generate a passable description
and presence in the game (Something gleams in the distance./An imposing
silver-gray smooth barrier rises from the ground, impedeing your progress/
Your missile detonates against the wall, melting a small portion of it and
leaving a blackened residue against the rest. - all from a simple def of
steel/300x7000x6cm and a placement with correct orientation) make it easy
to construct a believable world, leaving the real work in designing the
parts you _want_ to have a strong impact so that they have a literary
feel, and sufficient flexibility that they remain reasonably well 
described even after a good deal of change. (I plan to rate the
persistance of descriptions, and revert to system generated descs as soon
as the persistance limit is overcome, unless contingency descs exist.
Automating this is a long way off, perhaps impossible.)

Discreet database points in GURU:

The GURU (Graphical User Rendered Universe) is not designed either to be
readilly programmed or described (naturally, being graphical) once
released. Instead, it is designed to be the ultimate in effective mass
social modeling, within the context of a completely dynamic and intensely
vast world. (User Rendered refers to the client's purported 3D rendering
capabilities... something that has yet to be completed. We're still
playing with generic tiles, even after three years of work.) The server,
which is my part of the design, uses a massive sort of tree based
database, mostly compressed and with details of the terrain extrapolated
from neighbors by a delta factor (a little more complex than that,
actually, but oh, well.) Parents of a leaf on a tree are cross
polinating... each leaf (room) shares parents with each of its 8(+18)
neighbors. Most rooms not on the ground level never evaluate, and are
therefore never even generated in the first place. There are exceptions. A
room is defined as a space 30m on a side. Internally, everything is
tracked as in a 3D coordinate system.

Now to the trick to management of the whole thing.

Rooms are active only in the viscinity of a player. This means the current
room, the 8 adjacent horizontals, and the 18 others above and below.
That's a cube 90 meters on a side, quite reasonable considering all races
are humanoid. (All players see their own race as human, and all other PC
races as humanoid bestial... they never are informed that there are PCs
that do NOT appear humanoid. This is added to the trick I have described
before about linking two PC/NPC pairs so that the NPCs mirror remotely
located PCs in combat - resulting in a (supposed) NPC fighting as
intelligently as a PC... remember, also, combat is supposedly eventually
going to become totally twitch here, if igt ever makes it to VR. In any
case, what happens is, a thread is assigned to each active PC, provided
that PC is not within the active region of another PC. If two PCs' regions
cross, one of the threads dumps all data and pending events into the other
and dies. If the two PCs drift away (twice as far away as the crossing
region - I create an ameobic fission effect here) the thread spawns a new
thread for the smaller player (or at random) and dumps everything into it.
If something happens that should be visable for a certain range, the
message propogates to the nth parent, and to each thread currently owning
a piece of the db in that range. Thus, effects as follows:

#### #### #### .... .... .... ....
#### #### #### .... .... .... ....
#### #### #### .... .... .... ....

#### #oo# #### .... &&&& &&&& &&&&
#### /][\ #### .... &&&& &&&& &&&&
#### #/\# #### .... &&&& &&&& &&&&

#### #### #### .... &&&& &@@& &&&&
#### #### #### .... &&&& A()A &&&&
#### #### #### .... &&&& &UU& &&&&

.... .... .... .... &&&& &&&& &&&&
.... .... .... .... &&&& &&&& &&&&
.... .... .... .... &&&& &&&& &&&&


--


#### #### #### .... .... .... .... .... ....
#### #### #### .... .... .... .... .... ....
#### #### #### .... .... .... .... .... ....

#### #oo# #### &&&& &&&& &&&& .... .... ....
#### /][\ #### &&&& &&&& &&&& .... .... ....
#### #/\# #### &&&& &&&& &&&& .... .... ....

#### #### #### &&&& &@@& &&&& .... .... ....
#### #### #### &&&& A()A &&&& .... .... ....
#### #### #### &&&& &UU& &&&& .... .... ....

.... .... .... &&&& &&&& &&&& .... .... ....
.... .... .... &&&& &&&& &&&& .... .... ....
.... .... .... &&&& &&&& &&&& .... .... ....


--


.... &&&& &&&& &&&& .... .... .... .... ....
.... &&&& &&&& &&&& .... .... .... .... ....
.... &&&& &&&& &&&& .... .... .... .... ....

.... &&&& &oo& &&&& &&&& &&&& .... .... ....
.... &&&& /][\ &&&& &&&& &&&& .... .... ....
.... &&&& &/\& &&&& &&&& &&&& .... .... ....

.... &&&& &&&& &&&& &@@& &&&& .... .... ....
.... &&&& &&&& &&&& A()A &&&& .... .... ....
.... &&&& &&&& &&&& &UU& &&&& .... .... ....

.... .... .... &&&& &&&& &&&& .... .... ....
.... .... .... &&&& &&&& &&&& .... .... ....
.... .... .... &&&& &&&& &&&& .... .... ....


Seperation results in shapes like

###
#O#
#####
   #####
     #O#
     ###

This design is far more PC centric, and assumes a rather limited model of
PC, something the Physmud++ design does not do.

--

"You? We can't take you," said the Dean, glaring at the Librarian.
"You don't know a thing about guerilla warfare." - Reaper Man,
Nathan F. Yospe  Registered Looney                   by Terry Pratchett
yospe at hawaii.edu   http://www2.hawaii.edu/~yospe           Meow