Imaginary Realities Imaginary Realities About Search Glossary
What's new? Index :)
Select issue:
Join a discussion Resources
     

Dangerous Realism
- Scatter ///\oo/\\\
The love song of an anonymous mudder
- Twiggy@Discworld (with notable help from T. S. Eliot
NPC Intelligence
- David Bennett
Multilayed Mapping
- Telford Tendys

Letters to the editor

Enter your email to be informed when this site is updated.


Comment on articles

Letter 1
Contact editors

   

Multilayed Mapping

by Telford Tendys

This article explains an alternative technique for mapping within MUD environments that allows for the calculation of real distances and can be used for a complete map containing locations whose relative size may be greatly different.

Background of the problem

Outline of traditional mapping

Traditional mapping is based on ``rooms''. A character can either be inside a room or outside a room but no other positional state is considered. In other words the game knows the character's location to a resolution of one single room.

Rooms are linked by ``exits'' which hop a character from one room to the next. Some MUDs also support characters climbing into objects (i.e. a tree of rooms). From the point of view of graph theory, the exist and rooms make a ``directed graph'' which the character can traverse.

Problems with traditional mapping

The old world

A map of the world.

The concept of distance is usually absent from room based mapping. Using a directed graph, distance can be calculated in terms of how many hops along the graph are required to complete a journey or by summing of weightings along each hop (i.e. exists that have a distance value attached). Neither of these is satisfactory: the former has little or no relation to actual physical distance and the latter only relates to physical distance if the builders have gone through the arduous process of calculating a set of weightings. If these weightings turn out wrong then anomalous ``short cuts'' will exist, possibly making the game interesting but at a great expense to realism.

Outline of gridular mapping

Many computer games make use of a grid map, consisting of usually either hexagons or squares. Such a grid map enforces accurate distances and can be a very convenient way of organising a game. The disadvantage is encountered when large scale differences occur. For example, a town sits in the middle of a forest. We don't want to model each individual tree in the forest but we do want to model each doorway and room within the town. Using a grid requires that many of the forest grid locations contain identical information to each other in order to provide a fine enough mesh to map the town,

Using more than one grid

To get the advantage of the grid system for measuring distance but still allow flexible scaling, we need to weave multiple grids together. Each grid is a different size so that for each object that we want to map, appropriate sized grid squares can be chosen. I have settled on using grids that are based on the powers of two. Each grid is named by a logarithmic scale number such that scale 0 has squares with length of 1 unit, scale 1 has sides with length of 2 units, scale -1 has sides with length 1/2 of a unit. I also decided to make these grids slightly offset from one another such that no two grids share the same corner points, no matter what scale they may be. This last requirement may sound difficult or even impossible but (as will hopefully be shown below) there is at least one system of grids that has this property.

Simple grid template for a multiscale map

 7.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 7.0        1   1   1   1   1   1   1   1 
 6.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 6.0          2       2       2       2   
 5.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 5.0        1   1   1   1   1   1   1   1 
 4.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 4.0              3               3       
 3.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 3.0        1   1   1   1   1   1   1   1 
 2.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 2.0          2       2       2       2   
 1.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 1.0        1   1   1   1   1   1   1   1 
 0.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0.0      
-0.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1.0        1   1   1   1   1   1   1   1 
-1.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-2.0          2       2       2       2   
-2.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-3.0        1   1   1   1   1   1   1   1 
-3.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-4.0              3               3       
-4.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
-5.0        1   1   1   1   1   1   1   1  
-5.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
-6.0          2       2       2       2    
-6.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
-7.0        1   1   1   1   1   1   1   1  
-7.5       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

Resolving overlap

The diagram above shows corner points of four scales of grid and gives the Y coordinate of each row of points. It should be seen from this that each grid consists of non-overlapping squares but that squares from different scales will overlap.

The one remainimg point is a rule that resolves the overlap, this is a simple rule that says smaller squares always over-rule larger squares when both cover the same point.

Game world example

The old world

Older than most muds.

Here I build up a game world using a few squares at a time. The diagrams here were drawn using my current prototype mapping software. The mechanism and internal data structures used to perform mapping with this system are not discussed here because they represent implementation issues that cloud the presentation of the general principle.

The example provided here should give readers a feeling for how this mapping system works in practice and for how few map regions are required to construct an acceptable map thanks to the availability of many grid scales.

Most General Features

To start the ball rolling, we define a map that contains just an outer region which is impassable and an inner region which is terrain of light difficulty. The outer region is scale 10 and the inner region is scale 9. This provides a bounded playground with plenty of space for further building. More complex top level regions that could wrap their edges to make a cylinder or torus but here I stick to a flat, bounded area which is the simplest of all.

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

To add a bit of interest to this, a few special regions are defined around the edges, these may be mountains, forest, seas, etc. These features are of scale 8.

################
################
######$$$$######
######$$$$######
####..$$$$..####
####..$$$$..####
####......;;;;##
####......;;;;##
####......;;;;##
####......;;;;##
##::::::::..####
##::::::::..####
##::::::::######
##::::::::######
################
################

The further addition of squares from the scale 7 grid gives something that begins to resemble a wilderness map.

################
################
######$$$$######
###****$$$#..###
###****$$$...###
###**.$$$;;.####
###**....;;;;;##
####......;;;;##
####......;;;;##
###;;.....;;;;##
##:;;:::::..####
##::::::::.$$###
##::::::::#$$###
##::::::::######
################
################

Now I zoom into the southeast corner of the map where I have the edge of the world delimited by an impassable mountain range and I also have a smaller region of mountains that can be crossed with great difficulty. I want to place a few canyons through these mountains and maybe some caves reaching out toward the edge of the world. This uses a handful of smaller scale squares.

::::................################
::::................################
::::................################
::::................################
::::................################
::::................################
::::........$$$$$$$$$$$$$$$$########
::::........$$$$$$$$$$$$$    #######
::::......        $$$$       #######
::::......        $$$$ $$  $########
::::......             $$  $########
::::......                $$########
::::........$$$$        $$    ######
::::........$$$$        $$    ######
::::########$$$$        $$    ######
::::########$$$$              ######
::::########$$$$           $########
::::########$$$$        $$$$########
::::########$$$$$$$$$$$$$$$$########
::::########$$$$$$$$$$$$$$$$########

This process of adding finer detail where required can be used to map castles, towns and other such things.

Extensions to the basics

Three dimensions

In principle, the same method works in three dimensions, in practice it is difficult to visualise and work with. At present I am limiting things to two dimensions in order to get the most of out of that before complicating the issue.

Descriptions

Since each location on the world exists in a region, attaching descriptions to each region allows a description to exist for each point in the world. This does require that the builder take into account the immediate surroundings of each region when they write their prose but the other option would be to track line of sight around each location which is very CPU intensive. Noises and smells however, can easily be tracked just by distance and it is quite easy to have nearby regions share parts of their description with each other.

Movement

My current best solution for movement is to step along a path of movement, using the scale of nearby regions as a measure for each step. These steps will try to stop halfway between region borders where possible in order to provide an element of ``snap'' that the players can get comfortable with. Movement is similar to but not the same as standard discrete mapping but a fairly simple grid map can behave as the equivalent to a quite complicated discrete map.