Web MMO - Defining the map
Sunday, April 13th, 2008My current technical challange is how to define the map. I’m not entiurely decided what is going to be the most efficient method for doing so.
If this was a desktop game, I would have a map structure that kept track of the terrain and any strange features, but didn’t keep track of objects, creatures or anything else. Instead I would have a dictionary of location coordinates to lists of objects, so to draw a map location we would do something like…
drawTerrain(Location.all().filter("coords =",xy).get().terrain)
for object in Object.all().filter("coords =",xy).fetch(100):
drawObject(object)
for creature in Creature.all().filter("coords =",xy).fetch(100):
drawCreature(creature)
But I’m worried about the performance, as we would make three database calls there. On the other hand trying to denormalise a potential list of objects into the Location class seems to be excessively hard given the type restrictions on what can go into a BigTable (We’d have to use a list of Strings, and stringify each object / creature).
If I accept that the above code is the right way to draw the creatures and objects, I know we’re only doing 3 gets to the database. But we’re going to have to do that bit of code for every mapsquare that the user can see that we want to draw.
So if the user is at 8,3, we need to draw the squares [(7,2), (8,2), (9,2), (7,3), (8,3), (9,3), (7,4), (8,4), (9,4)] at least, and that assumes we dont also draw every square that the user has visited. To get the terrain information for each square at least will require 9 database calls.
So how to denormalise it? Well I think I might have a solution, although it may be ugly. If I split the terrain into say 5×5 blocks, so each block fo 25 tiles is a single super cell, I can store the terrain as a fixed width list or string, so Cell 1 has the terrain list of [1,1,1,2,2,1,1,2,2,3,1,1,2,2,2,1,1,1,2,1,1,1,1,1,1] which if laid out looks like
[ 1,1,1,2,2, 1,1,2,2,3, 1,1,2,2,2, 1,1,1,2,1, 1,1,1,1,1 ]
So now, to get the terrain information for a single location, we only need to load up our cell, and then index into the cell a number of times.
You see this sort of thing happen in real 3d MMORPG’s where it is called Zoning. Our worst case scenario is that the user is at one of the corners of a Cell, in which case they can see into 4 cells around them. The bigger we make the cell, the less likely that becomes, but the more data we need to put into the database, which may not be a problem, but also the bigger memory footprint we need to get the data back out (costing time and memory when we do our actual get).
For this game, I think we are probbaly going to generate a fairly small island map, say only a few hundered squares wide and high, so cells of around 50 or 100 in width is probably around the right number, giving us tens of cells, but thousands of actual locations.