# Techniques for mapping “nodes” and paths between nodes in a world space that extends in three dimensions

I'm trying to create a travellable map/world. I want to model able-to-be-occupied nodes/tiles/locations and allowed paths between them to create a space infinitely able to be built upon in all directions (not just flatland), in a browser-based game ( http://ninjawars.net , for a sense of it).

For example your character will be in a node "a field", and could then move north into "the first floor of a shack", or south or east or west. After moving north, movement choices would then be: south back to the field, or up to the second floor of the shack.

Basically, a grid maze with the minor complexity of the up and down option.

What are useful methods for modeling both the inhabitable nodes and the paths between them? X,y,z euclidean coordinates and relational lists of available connections from individual nodes?

Or are there alternatives to grids that could still allow fun visual representation of movement options?

Each node could have a 3d index and 8bit flag where you use 6 of those bits to determine if a direction is walkable or not.

Example node:

XYZ(choose data-type depending on your map size requirements)
128,129,523

UDEWNS(up,down,east,west,north,south)
100001


Would mean you can walk up and south from zone 128,129,523.

When you walk one of the directions increment/decrement the appropriate dimension. Walking up from the example zone would bring you to 128,129,524

Hope this helps.

• I do like the simplicity that this would provide. Perhaps this simple variation on the coordinate system with a wildcard linkage available, e.g. linking from 0, 0, 0 to 23, 23, 23, wouldn't be direct, so it would use the wildcard exit. – Kzqai Dec 21 '10 at 16:55

If your map is not extremely dense, you would be best off defining it with a list of nodes rather than an actual array or grid. Create a list of nodes, where each node has a set of links to what node you will go to if you travel N, S, E, W, U or D. This is how MUDs typically work I believe. Also text-based adventure games.

Here is a bit of pseudo code to define a field node, and a shack and the shack's second floor...

// --- Define field node
node[1].name = "field";
node[1].description = "You are standing in a farmers field.";
node[1].up_to = 0;
node[1].down_to = 0;
node[1].north_to = 2;
node[1].south_to = 0;
node[1].west_to = 0;
node[1].east_to = 0;

// --- Define shack first floor node
node[2].name = "shack";
node[2].description = "You are on the first floor of a shack.";
node[2].up_to = 3;
node[2].down_to = 0;
node[2].north_to = 0;
node[2].south_to = 1;
node[2].west_to = 0;
node[2].east_to = 0;

// --- Define shack second floor node
node[3].name = "second floor";
node[3].description = "You are on the third floor of a shack.";
node[3].up_to = 0;
node[3].down_to = 2;
node[3].north_to = 0;
node[3].south_to = 0;
node[3].west_to = 0;
node[3].east_to = 0;


The "_to" values represent the ID of the node you'll go to if you travel in that direction. If the "_to" value is zero, that means there is no path that direction. With this kind of system, you can see how the player can go north and be on the first floor of the shack. And from the first floor they can go south back to the field, or up to the second floor.

When you program a system like this, it is very easy to use the path information to dynamically give the player information on where they are. For example suppose that the current node they are in is set in the variable "current_node". You can then check each of the 6 directions and print out possible travel information to the player like this...

north_to = node[current_node].north_to;
if (north_to != 0) {
print "A path leads north to " + node[north_to].name;
}

south_to = node[current_node].south_to;
if (south_to != 0) {
print "A path leads south to " + node[south_to].name;
}

east_to = node[current_node].east_to;
if (east_to != 0) {
print "A path leads east to " + node[east_to].name;
}

west_to = node[current_node].west_to;
if (west_to != 0) {
print "A path leads west to " + node[west_to].name;
}

up_to = node[current_node].up_to;
if (up_to != 0) {
print "A path leads up to " + node[up_to].name;
}

down_to = node[current_node].down_to;
if (down_to != 0) {
print "A path leads down to " + node[down_to].name;
}


One thing a system like this lets you do is concentrate detail where you need it, and avoid it where you don't need it. You could let the player cross a mountain pass and enter a shrine in only a few steps, with a set of nodes linked like this...

WEST SIDE OF MOUNTAINS <--> MOUNTAIN PASS <--> EAST SIDE OF MOUNTAINS <--> SHRINE

If you tried to to that on a map of evenly sized tiles, it would take a large number of tiles to simulate the distance across the mountain pass.

Another advantage of a map like this is that it's very expandable. Suppose I want to put a basement in the shack in the pseudo code example above. I just need to add a new node for the basement, and change the "down_to" link on the shack's first floor to point to the basement.

If you'd really like to have some graphics with the game, you could associate a picture with each node, and the picture is shown to the player when they visit that node. These nodes could even be places where players click, walk around, explore, etc. This is about how Club Penguin manages rooms, and also many click adventure games like "Ben There, Dan That".

Of course this approach does not work with a tiled map or one where you want to let the player go any place they'd like to go.

If you want a scalable solution use a graph data structure (Wikipedia Link)

With a graph you can associate each region with a node on the graph. Each node contains the neighbours of that node in the graph (the nodes that are connected to it).

You also have a lot of increased flexibility with a graph, for example:

1. A region had a north, west and east exit (no south) - You wouldn't have to worry about setting the south exit to NULL or whatever, you just wouldn't add that node to the neighbours list

2. Say you wanted to go from a town to a dungeon, but you couldn't go back the same way because for some reason the exit was closed off by demons, this is where Directional Graphs come in. You could have a neighbour called Dungeon in Town's neighbours list, but don't add a Town neighbour to the Dungeon node (meaning that you can go from Town->Dungeon, but Dungeon->Town is impossible)

3. If you wanted a fancy effect of hopping from region to region, you could easily implement some pathfinding like A* to figure out the shortest path for you.

You could go with a connectivity matrix, but as you say you wanted something in 3-dimensions, so this would essentially be a 3-dimensional array which would get VERY big VERY fast.

If you want a solution that you can easily add nodes to (for example, when expanding on your game) then I'd definitely recommend using a graph.

Depending on how you decide to implement this, you could (1) simply build a graph of visitable nodes using pointers or references or (2) if your language supports it, you could use proper tail calls; Programming in Lua has a good example of this directly related to game development.