Maps and Mapping

This was originally written for CVu magazine.

The other day a couple of people asked me how I designed and coded the maps in my new game (Age of Adventure). The map is a central feature in the game and people were interested in how I did maps for adventure/rpg games. I said I would do a piece explaining the basics, so here it is...

The first and most important thing to realise is that if you are going to make this useful, then you have to decouple the representation of the map from the map itself.

What do I mean by that?

I mean that at this stage we have not the faintest interest in how the map is going to be represented on the screen. We don't care if the locations are round, square, hexagonal, or even rhomboids. What we are interested in is getting the map data in a form where it can be manipulated to do the things we want without having to worry about how it looks.

Of course, this is not completely possible, such things never are, but we will reduce the assumptions to a minimum, and maybe later we can look and see if there is any way - such as the use of templates - that will allow us to remove even those dependencies.

So - the first thing we want to do is to have a look at the locations and see what information a location should have. Well for a start, every location has a position on the map, so we can give it a unique identifier for that position. Depending on how general you want to make it, the identifier could either be a set of co-ordinates, or a single number derived from those co-ordinates (e.g. row_no * width + col_no).

We also need some way of specifying what locations this location connects with. Even if you are using (say) all the locations on a flat map, you may have impassable barriers between adjacent locations. There are, again different ways you can represent this with differing degrees of generality. You could actually list all the locations connected to this one. This makes no assumptions about the dimensionality of the map, which could be anything from 1 to n dimensions (yes, you can have a game played on a one dimensional map). Alternatively, you could specify the directions in which there are exits - for instance a 32-bit wide bitmap would allow you to specify up to 32 different allowable exits for the location.

Really that's all you need for a base class, which looks like this:

class Location { protected:: int loc_no; // location identifier; unsigned exits; // bitmap identifying exits

public:: Location(int num,unsigned the_exits);; ~Location();; virtual void Display() = 0;
};

We may discover later on that we will need more virtual functions, but for the time being we can stay with just the one.

Next, we want to look at the map itself, so what are we going to need?

Well, most importantly, we need a container index to the locations, and this is where we get into the reality of real life - we can no longer duck the question of what the map is like. This is because we need to choose a container which will handle access to our locations efficiently. Possibly, we could use templates to keep it more general, but there are other considerations, like the dimensionality of the map which are not amenable to templatisation.

There are two obvious cases. The first is where all the locations are adjacent and the map is full - there is no areas where there is no location. Some form of a vector would be the best representation for this - either an STL vector, or if your map is not going to expand, then perhaps a straight array.

The second case is where only some - possibly a relatively small number - of the potential locations on a map have actual locations in them. A vector would be a serious waste of space for such a sparsely populated array. What we want here is an STL map container. (Note, the fact that the container and the thing we are modelling have the same name is not significant!)

If we are going to use this map in the real world, we also need to know how many dimensions the map has and the size of those dimensions. If, in the interests of generalisation, we keep them out, then we have to derive the location number from the co-ordinates somewhere else. It seems to me that the proper place for such information and calculation is in the map object.

For our purposes, I will assume a two dimensional map.

There are a couple of other things that we should add into our map at this stage. The map is going to have to keep track of what object, computer controlled characters (mobiles), and player characters are on it - and where they are. Since mobiles are souped-up objects that move around, we can derive mobiles from objects, giving us two lists to maintain.

Theoretically, you could have each location maintain its own lists of the players and objects in that location, but there are usually far more locations than objects or players. Even in a treasure trove location you will not have dozens of objects, just a couple of high level objects and a few smaller - say the +4 trousers of golfing, the asparagus spear of destiny and a pile of gold coins. This is a classic trade off of space against time.

So what are we looking at now for our map?

class Location;
class GameObject;
class Player;

typedef map< int,Location *,less<int> > LocationList;
typedef map< int,GameObject *,less<int> > ObjectList;
typedef map< int,Player *,less<int> > PlayerList;

class GameMap
{
private:: int width, height; // map width and height; LocationList loc_list; // the locations; ObjectList obj_list; // the objects on the map; PlayerList player_list; // players on this map
public:: GameMap(int width,int height);; ~GameMap();
}

ObjectList and PlayerList are indexed by the location identifier.

An alternative would be to make LocationList actually contain the locations - i.e. typedef map< int,Location,less<int> >. (Incidently, if you don't leave a space between the last two '>'s', the compiler will throw a wobbly!)

I tend to use STL maps as indices into collections of objects, rather than as containers holding the collections. This is because I frequently find that I need multiple indices into the collections, and it is less confusing in the long run if none of the containers 'own' the objects. The downside, of course is that I am responsible for making sure the objects are properly destroyed. To my mind this is very much a horses for courses issue.

One final note for this month. You don't have to have a single huge map for your game - you can break it into smaller maps with links between them. This is really a judgement call balancing breaking the map into more easily searchable chunks against having everything in one place.

Well that's probably enough for one month. Next month I'll have a look at how we use this map in a game.

Have fun programming.

Alan Lenton
13 April, 2014