Title: Thinking Aloud

A bunch of players were sitting around talking in one of my games the other day when the subject inevitably came round to Microsoft and its current legal troubles. Most of the non-US people found the legal action completely incomprehensible. Even leaving that aside, there seemed to be a consensus that inviting the US government in was very much the thin end of the wedge.

Let us face it, no one likes Microsoft all that much, they have irritated too many people over the years. None the less there was a feeling that on the whole the US government is acting on behalf of a bunch of losers who screwed up competing with Microsoft in the market place.

The truth is that at most of the critical junctures, going right back to the adoption of MS-DOS by IBM, Microsoft delivered by one means or another and its opponents screwed up. Sometimes what they delivered was dire, but none-the-less they delivered.

The feeling was summed up by a programmer who said, "At least Bill Gates is one of us..." There is some truth in that. I suspect if Oracle, for instance, had been in Microsoft's position we would probably all be renting our software and paying for how many times a day we use it!

Not that people did not have some interesting ideas for what Microsoft's punishment should be. The one I really liked was the suggestion that Microsoft should not be allowed to release any new software until all the bugs are out of their current products!

Pretty neat I thought.

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 do not 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 is 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 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 that 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 & height
  LocationList  loc_list;  // the locations
  ObjectList  obj_list; // 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> >. (Incidentally, if you do not 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 is probably enough for one month. Next month I will have a look at how we use this map in a game.

Have fun programming.