data-structures - 为在线多人游戏存储基于大图 block 的 map

Question

我目前正在制作一个基于图块的 mmorpg，并试图找到一种存储大型 2d 游戏世界的好方法(至少 1000 个平方的图块，但希望更像几千个平方)。这个想法是鼓励人们在共享 map 上创建自己的城市，用户将能够在游戏中 build 房屋和商店，这样瓷砖就可以被编辑并与一些链接表建立一对多的关系。我正在考虑将它们以 64x64 平铺块的形式发送给客户端。

我目前在 php/mysql 中工作，我的表看起来像:

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;

和查询大致像

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

当我只有大约 50 万条记录时，它只需要大约半秒，但是当我获得大约 400 万条记录时，大约需要 5 秒，我相信有一些方法可以改进这一点。

我可以通过缓存 map 请求来解决这个问题，但我想知道是否有更好的配置数据库的方法，以及是否有人有有效存储大型 2d 游戏世界的技巧？

谢谢你的时间

Answer 1

随着数据集大小的增加，范围查询很快就会失控。你可能想看看这方面的一些文献。这里有一些有趣的论文。

范围查询的数据结构:

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

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

快速搜索算法

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