[Home] [Contact]

MindX Article: Why I invented Netmap

Well, when working on GGZ Gathering, I managed the map as I used to in my previous games: 

	/* declaration */
	int map[MAP_WIDTH][MAP_HEIGHT]
	/* assignment example */
	int tile = map[0][3];

The next step was to find a suitable maximum width. If e.g. 16 players play over the Internet, and everyone wants to go through the map without stepping on each other's foots, the map's size must have been at least 128x128 tiles.

An int is 4 bytes, so that map would have taken 64 kBytes. Even as a char[][] array, the memory usage of 16 kB (to be transmitted over the net) requires some seconds to be loaded on the player's side. Not to imagine map updates or even larger maps...

So why not creating a C++ library for it? The code then goes like this: 

	/* declaration */
	NetmapMap *map;
	map = new NetmapMap();
	map->loadMap("/tmp/large.map");
	/* assignment */
	for(int j = 0; j < map->height(); j++)
	  for(int i = 0; i < map->width(); i++)
	    int tile = map->tile(i, j);

This is even the worst case, when all tiles have to be drawn. In games this is normally never the case. Take the usual strategy games as an example: You start with a little piece of map around your character, the rest is black. If you move along, new parts of the map become visible. Maybe the map tiles behind you begin to darken again, but this is only a graphical effect, it has nothing to do with the associated memory (except that it is possible to do some optimization here too, but this follows later on).

Now imagine you have a map of say 16384 x 16384 tiles. They represent water, grass, stones and so on, so that a char datatype is sufficient for their representation. The map is then 256 MB large. For today's computer this is acceptable for a map on hard disk - but not in the RAM, especially if there is other time-critical game information too! Using Netmap, this is no problem, even if the map is transmitted over the network: Depending on how much tiles every vtile (virtual tile) contains (the default is 16x16 = 256), only this amount of data is transmitted. The vtiles are then stored dynamically on the player's computer, as a doubly-linked list.

The map->tile() function does then act as a proxy: If available, the information is taken from the proxy's cache - if not, it is taken from the Resource - which may be either a local file or a network connection, where the server itself uses a file to provide the needed data.

Possible optimizations: In e.g. role-play games, where players mostly see some parts of the map only once, the cache size should not be too high, so that the bottom-most elements of a list can be removed after a certain time. Another optimization could be that vtiles which contain the wanted tile (as requested by map->tile()) are moved on the list to the top, so the search algorithm finds them faster the next time.

Author
Josef Spillner, March 2001
dr_maux@users.sourceforge.net
The MindX Open Source Project