Storing large tile based maps for an online multiplayer game

Question

Hi All, I'm currently making a tile based mmorpg and am trying to find a good way to store a large 2d game world (at least 1000 squared tiles, but hopefully more like a few thousand squared). The idea is to encourage people to make their own cities on the shared map and users will be able to build houses and shops ingame so the tiles would be able to be edited and have a one to many relationship with some linked tables. I'm thinking of sending them to the client in 64x64 tile chunks.

I currently have it working in php/mysql, my table looks like:

CREATE TABLE  `fbmmo`.`tiles` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `x` int(11) NOT NULL,
  `y` int(11) NOT NULL,
  `realm` varchar(45) NOT NULL,
  `image_id` varchar(45) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `Index_X` (`x`),
  KEY `Index_Y` (`y`)
) ENGINE=InnoDB AUTO_INCREMENT=4327236 DEFAULT CHARSET=latin1;

and queries roughly like

select * from tiles where x<1000 and y<1000 and x>936 and y>936;

When I've only got about half a million records it only takes about half a second, but when i get up to about 4 million records it takes about 5 seconds and I'm sure theres some way to improve that.

I can get around it by cacheing the map requests but I wondered if there is a better method of configuring the database, and also if anyone has tips for effectively storing a large 2d game world?

thanks for your time

Answer 1

Maybe you could chunk the tiles already at the database level?

Answer 2

Just my small 2 cent. Maybe, depending on how ppl scroll the map, you can prefetch the next N visitable 64x64 tile sets. A small thing about image_id varchar(45) NOT NULL, are you sure you want to store the realm in each tile? Cant imagine what it is good for.

Answer 3

As the size of the data set increases, range queries can get out of hand very quickly. You might want to look at some literature on this. Here are some interesting papers.

Data structures for range queries:

http://portal.acm.org/citation.cfm?id=1035798

www.siam.org/proceedings/soda/2010/SODA10_014_yuanh.pdf

Algorithms for quick searching

www.cccg.ca/proceedings/2005/3.pdf