Atlas Semantic Geomaps

Aloril

2002-02-21

Contents
Thanks
Introduction
- Atlas
- Semantic Geomaps
Object model overview
- Oak object example
- Oak class definition example
Containers
Cartography/Geometry at different zoom levels
Hyperlinks
Media
- Example lookup
- Filtering
About this document ...

Thanks

Introduction

Atlas

Atlas is the standard worldforge protocol for client/server interaction. For more about Atlas see http://www.worldforge.org/dev/eng/protocols/.

In order to avoid confusing the concepts of a geographical map and how Atlas currently defines a map, this paper will call the former geomaps. The purpose of the paper is to foster discussion about what should be in the Atlas specification about geomaps and how it will relate to media.

Semantic GeoMaps

A semantic geomap contains the information needed by a world server to model a game or another world. It provides a comprehensive listing of what objects are located in a given portion of the world and the attributes and positions of those objects. The attributes should give meaning to their objects. For example, a road object is used instead of a line object (can this be elaborated? is a road object a line object with special attributes or just a change of attribute?). Clients use an object class and its attributes to find the appropriate media. Different clients will use different media (2D, 3D, text, aural, etc.) to represent the same object. This separates the data, semantic geomaps, from the representation the client assigns it.

In this way, Atlas semantic geomaps resemble object-oriented GIS^0.1 systems (such as Smallworld or LAMPS) rather than the more traditional vector- oriented GIS systems, such as MapInfo and ArcView. VOGIS's primary difference from OOGIS is that it defines a certain standard set of object types and attributes, whereas in OOGIS, objects are constantly redefined from geomap to geomap. This resembles C++, where anyone can create a class, but STL defines a standard set of classes for everyone to use rather than creating their own versions. In addition, Atlas defines a default set of values for the standard attributes for each type, which further allow a consistant way of defining geomaps.

AIs in NPC and user scripts can use semantic information defined in these objects to follow a road or to decide how to react to other objects. Also, they enable smarter tools than pure geographic info would allow. Some example tools might: find the shortest route between two places; select all roads, water, mountains, etc...; or, apply erosion to river drainage basins. From an interface point of view, a two-dimensional, isometric client might represent the game world's geomaps as a set of tiles laid out in a grid with animated sprites moving around on top, whereas the three-dimensional client might use a collection of textured meshes to describe the same geomaps. A text client might provide text-only descriptions of the entities in the game, in a MUD^0.2 style of layout. These aren't the limits, either. A client could have multiple types of media to display a specific geomap.

Beyond this separation of media and object, identification — a trait of semantic geomaps that distinguishes them from ordinary geomaps — allows an object to contain more than just position and related geographical information. (decide whether to make this example of attribute or what...)

Object model overview

Here we will attempt to explain the format for Atlas Objects. There are five basic types of attributes that an atlas object can have:

Integer: A number without decimal precision
Double: A number with decimal precision
String: A ordered collection of characters.
List: An ordered collection of any Atlas type defined here. Members of a list are not necessarily indexed, but can be. The index is typically an integer.
Map: An unordered collection of Atlas types defined here, where each member of the collection is indexed by a string (called a key)

Atlas objects are made up of various combinations of the above types. The following examples will further explain how Atlas defines objects and their classes.

Oak object example

This example shows a typical use of an Atlas Object.
$\begin{Aobjectfigure} % latex2html id marker 104 \begin{Amap} \Attr{id}{... ...\lq\lq human234'')} \end{Amap} \caption{Oak object example} \end{Aobjectfigure}$

Here's an explanation of the above attributes:

Id: - The unique identifier for the object.
Name: - The name of object. The name doesn't need to be unique in the world.
Objtype: - The kind of Atlas object. An ``obj'' is an instance of its parent(see below). These types can specify ``in game'' or ``out of game'' objects. Ex. Character object(in) v. Player object(out) Other possible Objtype values are ``op'', ``class'', or ``op_definition''. ``op'' is the same as ``obj'' except that it pertains to an operation instance as opposed to object instance. ``class'' and ``op_definition'' will be explained below.
Parents: - The inheritance structure of the object. Objects inherit attributes from a parent class. Classes may inherit attributes from one or many parent classes. In the case of an instance object, the parent is its class object's id (``oak'' in this example).
Pos: - The position of the object in relation to its container. Usually the position is given as a list of x, y and z. The directions of x, y and z are mathematical ones: x is from left to right or west to east, y is south to north and z is from down to up. ^0.3
Velocity: - The velocity vector of the object in relation to the container. ^0.4
Loc: - The id of the object that contains this object — the object's container.
Contains: - An id list specifying which objects are contained by this one.

Oak class definition example

This is the definition of the oak class of which the above object is an instance:
$\begin{Aobjectfigure} % latex2html id marker 113 \begin{Amap} \Attr{id}{\lq\lq o... ...'')} \end{Amap} \caption{Oak class definition example} \end{Aobjectfigure}$
There are no attributes in the oak class definition example that aren't in the oak trees' instances in the world. Despite this, the descriptions of each are somewhat different:

Id: is the unique class name.
Name: This field is typically just a placeholder without real significance to the class. In this case, the Latin name is used. Usually, it is identical to the id attribute. It's different here to show that that's possible ;-).
Objtype: The value ``class'' specifies a new object type. These objects are out of game. The purpose of these definitions is to provide the layout of the class for any instances, and also to store default values for the object type. A benefit of this might be to allow the server to pass any new definitions to the client via Atlas (if that functionality is implemented.) ``op_definition'' defines a new operation type. It is basically the class definition for operations — much like ``class''.
Parents: All superclasses of this class definition are placed in this list.

Containers

Containers organize the objects in geomaps. Each object has two attributes, loc and contains, that are used to designate containment. Containers provide many convenient benefits.

Since a container is independent from any other, each may have its own coordinate system to designate the position of objects within it. This allows the ability to change the container's position without having to modify the position of those objects contained within it. Second, the coordinate system can be a generic floating point system, while still providing accurate positioning at detailed levels. Though each container uses the same system, the depth of containment would specify the actual scale between two containers. See the examples later for further explanation. (I assume this is further explained in examples below)

Another benefit of containers is scope. With certain actions, such as sight or collision detection (CD), containers provide a way to limit which objects need to interact. For example, there is no need to display what items a box might contain or to show objects in a neighboring forest. Scope also can limit the detail of information in the same way. For instance, someone standing on a mountain looking out would see other mountains, forests, and perhaps cities, but would not know what was contained within them.

Lastly, containers provide a way to logically group objects. This can be a useful way to define sections of a game world, so it can be distributed to several game servers or ``canned'' into a packaged realm.

Container examples

Only attributes related to ``containership'' are included. Note that orientation is not yet included in these examples.
$\begin{Aobjectfigure} % latex2html id marker 132 \begin{Amap} \Attr{id}{\lq\lq g... ...')} \end{Amap} \caption{Containers examples, part 1} \end{Aobjectfigure}$

$\begin{Aobjectfigure} % latex2html id marker 204 \begin{Amap} \Attr{id}{\lq\lq a... ...''} \end{Amap} \caption{Containers examples, part 2} \end{Aobjectfigure}$

The galaxy inherits default pos=(0.0, 0.0, 0.0) from the ``game_entity'' class definition.
Before space travel is implemented, the server will omit loc and pos attributes from the ``dural9'' object and thus `pretend' it's the highest-level object for clients.
When looking from far away at the Earth, the contains attribute will be shown as empty and only filled when the spaceship is near enough to see ``dural9''. Similarly, if Shewla Danylsen is too far from the ``oak123'' tree, she won't see her son. Also unless ``backpack6788'' is open, the backpack's contents are not visible.
Note that ``apple11111'' does not have the pos attribute. Its position inside ``backpack6788'' is undetermined.
In the example, ``backpack6788'' is defined using numerical coordinates. Another possibility might be to set its loc attribute to ``human234#back''. Another possibility might be to use something like symbolic_pos with ``back'' as value.

Example on how to calculate ``absolute'' position

This example uses python syntax.

def get_xyz(self):
    """get location: if relative to location (container),
       add our position to actual container location"""
    if self.loc:
        return self.loc.get_xyz() + self.pos
    else:
        return self.pos

Your actual implementation can certainly optimize beyond the above code. It can, for example, also store an absolutePosition attribute. You'd calculate that for every object and when the object moved, update both the pos and absolutePosition attributes. When object changes containers, you'd calculate its new absolutePosition using the formula loc.absolutePosition + pos.

Alternative: containers as separate objects

loc, pos, and contains attributes could be made into separate objects. This object would also have a separate class hierarchy.

Discussion with bryce about containers:

``In the real world, every item contained within another item has a specific position and identity. However, in some situations it is immaterial where the item is, exactly, and in others we don't care too much about that specific item. Knowing that we don't care, we can then throw that information away and compress our data down by a great deal.

For example, consider a bag full of apples, pears, and bananas. Certainly in real life, each of these items has a specific position within the bag; however, if within a game server we had to go to the work of calculating exact positions of each piece of fruit taking into account physical shape, smooshiness, etc. it'd be a waste of cycles. Instead, all we really, truly need to know is that within the bag there are 4 apples, 2 pears, and 7 bananas. We don't care about the position. This not only saves us the processing work of positioning the items, but also allows us to skip keeping track of the positions of the items.

Alternatively, consider an orchard's 300m x 300m field of apple trees. The field consists of rows 3 meters apart, with each tree within a row spaced 3 meter apart. In a generic container, we'd need to describe the area by sending data on 10,000 entities to the client, but because every tree is identical, and because they're spaced in a deterministic grid, this is extremely wasteful. Instead, what we want to do is tell the client, ``Put 10,000 Apple Trees in a grid according to this formula...''

As you can surmise, there are probably other different styles of containers beyond 'bags' and 'fields', so we generalize the notion of a ``container'', separately from an ``entity''. An entity could contain other entities in different ways, depending on how we want to store things within it. For example, consider if we cut down all the apple trees and pile them up in a jumble along with bits of broken stone and some dead bodies. In this case we may want to treat the field just like a bag - a random collection of specific items. On the other hand, if we cleared the field and two groups of brigands faced off across it, engaged in battle, we'd suddenly care about both the exact positions and exact natures of everything on the field.

Thus, we want to allow a given entity to be able to change its type of container, as needed. This is modelled by saying that ``an entity has a container'' instead of ``entity is a container''.

Here are some kinds of containers:

Map - Items have a specific identity and a specific position.
Pile - Items do not have specific positions and are assumed to be randomly distributed within the container. The quantity of items of each specific type is given.
List - Items are ordered and have a specific identity, but are not geospacially positioned. This can be thought of as a queue or stack.
Set - Rather than using 3D coordinates, this uses abstract named ``locations'' within the container. For example, within a spacecraft we could identify crew positions as ``Pilot'', ``Gunner 1'', ``Gunner 2'', ``Engineer'', etc. In such circumstances it is assumed that the ``role'' is much more important for the game to know than the coordinate location. In a ship-to-ship space combat game, coordinates within a ship may be irrelevant (unless it's being boarded) than it is to know who's in which chair. In a roleplaying game, this style of container would be used for a character's possessions - he'd have named locations ``neck'', ``torso'', ``left foot'', and ``top of head''. An article of clothing (or weapon or armor) could be placed in each of these named locations.

In container info, the object model above might be modeled by having special object and/or special attributes.

Cartography/Geometry at different zoom levels

Object can be a point. Usually characters, trees, etc... are like this.
Object can be a line. Usually roads, fences, etc... are like this.
Object can be an area. Usually fields, forests, etc... are like this.
Object can be a volume. Usually caves, houses, etc... are like this.

One object can be different kinds of geometry types at different zoom levels. For example, you are far away from some star. You see the star as point object. When you get nearer to the star you see it as a volume object. Then, you get even nearer and see a river as a line object in the planet that orbits the star. You descend toward the river. You see the big river as an area object. You dive into it and see it as volume object. ^0.5

More detailed object(s) should be referred to in the contains attribute.

Point (0D) objects

This and following cartography subsections are based largely on discussion with James Turner, Anubis, DragonM, tbp, bear, malcolm and Jorrit (in order of time). Point objects have only position.
$\begin{Aobjectfigure} % latex2html id marker 279 \begin{Amap} \Attr{id}{\lq\lq h... ...ckpack6788'')} \end{Amap} \caption{Human point object} \end{Aobjectfigure}$
Also there can be ``point data'' objects which have coordinates for many positions. These objects are referred to by line, area and volume objects. ^0.6
$\begin{Aobjectfigure} % latex2html id marker 296 \begin{Amap} \Attr{id}{\lq\lq c... ... for river, all points could be in one object if wanted} \end{Aobjectfigure}$

Line (1D) objects

Line objects refer to point objects in polyline attribute. The format is object_id.attribute_name.index. Even if a polyline is made loopy, it does not cover area: the center is empty unless there is an area object.
$\begin{Aobjectfigure} % latex2html id marker 320 \begin{Amap} \Attr{id}{\lq\lq r... ...also, reference then would be \lq\lq river9.points.0'', \ldots} \end{Aobjectfigure}$

$\begin{Aobjectfigure} % latex2html id marker 333 \begin{Amap} \Attr{id}{\lq\lq r... ...e is holding other end and Michael is holding other end} \end{Aobjectfigure}$

Area (2D) objects

Area objects are triangle meshes. They refer to point objects in the area attribute. Each triangle is defined by 3 point ids. Every triangle should share at least one edge with another triangle, so you can get into any triangle from any other triangle by traveling from triangle to another. If you need areas that consist of separate pieces, make a higher level object and ``contain'' area objects in it. ^0.7

until the figure is made, here is an ascii version...
        ____
       /    0
      /  ___1
     4 _2
     3/

$\begin{Aobjectfigure} % latex2html id marker 348 \begin{Amap} \Attr{id}{\lq\lq r... ...r\_volume10'')} \end{Amap} \caption{River area object} \end{Aobjectfigure}$
Area objects can also have holes in them. Holes are defined by missing triangles inside area. ^0.8

until the figure is made, here is an ascii version...
 0    1
   45 
   67
 2    3

$\begin{Aobjectfigure} % latex2html id marker 368 \begin{Amap} \Attr{id}{\lq\lq l... ...{Amap} \caption{River area object with island \lq\lq holes''} \end{Aobjectfigure}$
You could also make holes by using ``negative'' area: the island is contained by a lake and removes water from its area.

Volume (3D) objects

Volume objects consist of one or more tetrahedrons. They refer to point objects in the volume attribute. Each tetrahedron is defined by 4 point ids. Every tetrahedron should share at least one face with another tetrahedron, so you can get into any tetrahedron from any other tetrahedron by traveling from one tetrahedron to another. If you need volumes that consist of separate pieces, make a higher level object and ``contain'' volume objects in it.
$\begin{Aobjectfigure} % latex2html id marker 396 \begin{Amap} \Attr{id}{\lq\lq r... ...{Amap} \caption{Volume river object: surface and bottom} \end{Aobjectfigure}$
Volume objects can have 1 or more holes or empty spaces by lacking tetrahedrons somewhere. Alternatively they can contain ``negative space'': for example, a mountain contains a cave or a house contains a room.

Higher (4D or more) dimensional objects

A higher dimensional object is defined using a collection of primitive objects which are defined using N+1 points and with N+1 N-1 dimensional limiting objects similarly to how 2D and 3D is done.

Connecting neighbouring objects

For topological consistency neigbouring objects should be connected to each other via common points/lines/triangles meshes/etc... More about this later.

Hyperlinks

URI (ids in Atlas) consists of: atlas://server.org/acorn/root
Protocol is ``atlas://''.
Server is ``server.org''.
World id is ``acorn''.
Root object (=id) is ``root''. Maybe the ``world id'' and ``id'' parts should be separated by something different than just '/'?

Media

Media is completely separate. Objects in a world server don't know anything about media objects. The world server only gives list of recommended media server(s) but the client can override selection.

So how does a client know which media to use for objects?
It uses the object's id, parents and other attributes to look for it at a media server. First client searches using object id, then using parents' ids, then grandparents ids', etc. until it finds a match. Searches are cached on the client and it probably makes good sense to cache a list of the ids each media server offers.

Example lookup

Client sees the character named ``Halek''.
$\begin{Aobjectfigure} % latex2html id marker 420 \begin{Amap} \Attr{id}{\lq\lq c... ...ap} \caption{\lq\lq Halek'' character and \lq\lq elf'' definition} \end{Aobjectfigure}$
First the client queries the media server for info about ``ch98''. If no info about that exists, then it queries about ``elf''. If there's still no info, then it queries for ``humanoid''. The client can fetch all the info objects from the media server beforehand, so querying, in practice, can be just cache lookups. Let's assume the client finds a media info object for ``elf''.
$\begin{Aobjectfigure} % latex2html id marker 437 \begin{Amap} \Attr{id}{\lq\lq e... ...vel media info object for \lq\lq elf'': 2 alternative versions} \end{Aobjectfigure}$

$\begin{Aobjectfigure} % latex2html id marker 469 \begin{Amap} \Attr{id}{\lq\lq e... ...\end{Amap} \caption{Media info object for 3D female elf} \end{Aobjectfigure}$

Filtering

Media info objects can contain also other attributes to use for filtering. For example, there might be different media available for different sized objects.

Footnotes

... GIS ^0.1: Geographic Information System http://www.usgs.gov/research/gis/title.html
... MUD ^0.2: MultiUser Dungeon http://www.mudconnect.com/mudfaq/mudfaq-p1.html
... up.^0.3: Worlds with more than three dimensions are possible, but are rare. Also, some games servers might want to use different method to specify position. For example sim games set in the Earth/Moon space, where the position is specified by six parameters, may want to use different way to specify position. In this case server should by default use the pos attribute. If the client supports an alternative system, then the server can use that instead: for example orbit_pos.
... container.^0.4: An object's pos and velocity should be in reference to their container.
... object.^0.5: If the server is using 2 coordinates and the client is using 3 coordinates, then the client should add/remove element as needed: Server: (x, y) becomes Client: (x, y, 0.0), Client: (x, y, z) becomes Server: (x, y). Similarly, if the server has 4 or more coordinates and the client is using 3 coordinates, the client should add/remove elements as needed.
... objects.^0.6: Using p in point data objects instead of points because it will be referred more than any other attribute: in binary2 encoding length doesn't matter but for every other encoding it does matter.
... that.^0.7: Even if area is made loopy so it seems like it covers volume, it doesn't: there is no inside and outside and both sides are empty unless there is real volume object.
... area.^0.8: In binary2 river and lake example objects can be encoded as series of int16 numbers or even as series of int8 numbers

Current Issue: February 2003, Recent Issues: January 2003, November 2002, October 2002