Pokemon-Go地图技术猜想

盛夏的七月，一款名为Pokemon-Go的游戏火了。基于LBS+AR玩法，使用的宠物小精灵的IP，让千万玩家穿梭于城市之间收集自己心爱的精灵，其核心功能之一便是模拟真实地图，让玩家“身临其境”的奔跑在地球上，那么地图功能是如何实现？

Pokemon-Go总体分析

如右图，和地图相关主要有三大核心内容，一、道路、河流，楼房等地理位置信息；二、由服务器确定的补给站、道馆、触发抓取精灵的位置；三、玩家操作的角色；

设计上来说可以分为二层：一层为地图层，它是静态不变的；二层为动态加载与地图上，它是可变的，主要内容是上述核心的二和三。

实现核心技术点：地图绘制，地图分块

 

 

地图绘制

类似APP或者游戏里地图绘制有二种方法：

第一种是取得地图原始数据（即地理信息数据，指的是一些道路，楼房，水域，绿化地等矢量或者空间标记信息），然后根据这些信息进行自定义绘制。

目前中国比较大的原始数据提供方 – 四维图新，他和很多知名公司都有合作关系，但是这里有一点比较棘手：中国地图绘制是需要资格的，这里可以查询http://chzz.nasg.gov.cn/UnitQuery.aspx有资质的绘制单位和资格申请的相关信息。

第二种是直接使用大公司的地图API，比如高德，百度，腾讯，谷歌（目前在中国未开），图吧。这种方法本质上就是API提供方根据你设定的参数帮你绘制好图，你拿来使用。很明显的缺点少自由度，比如你想更换一下地表的纹理甚至整体颜色基本是不可能的（除非你是他们公司内部的人提了特殊需求:D）。

大概比较如下：

	技术成本	自由度	是否需要资质
第一种（自己绘制）	高	高	是
第二种（接入API）	低	低	否

 

 

 

这里Pokemon Go开发公司Niantic Labs的创立者约翰·汉克（John Hanke）早期创建了地图测绘公司Keyhole，它于2004年被谷歌收购，可想而知有极大的可能性他们使用的第一种绘制方法。包括他们早期游戏ingress。

第二种方法理论上也走的通，只是你需要定制的API，地图上加载自己需要的纹理。所以说，如果要做LBS+AR，上面说的几家提供地图API的公司最方便开发。

 

地图大小

Pokemon Go中的地图缩放比例大小其实是固定的，通俗说法就是再怎么调整镜头，你看见东西精细度与数量是不会变化的。这个不同于网页上的地图，在网页地图上使用鼠标滚轮拉远或者拉近距离，地图上信息的详细程度也会随之变化。

同时这里也涉及到一个关键问题：比如我身处美国在玩Pokemon Go，不可能一次性把全美的地图全加载进来，我们也许会联想到下载APP包的时候附带地图的方法，但是这个方法不太可能，原因有二：

一、若APP包附带地图，当现实地图信息变更时，如何平稳更新游戏地图机制比较复杂，例如增量更新还是全量更新，不同版本之间兼容之类的问题；

二、实际容量，地图数据必然使APP包增大，但是从Pokemon Go的包大小（不到100M）来看比较小；

那么到底如何加载？做过游戏应该都知道，若游戏地图比较大，可以采取分块加载的思路，猜想Pokemon Go应该也类似。如下图：

解释一下，玩家上线之初在位置0（上图小人所在淡黄色块），但是会预加载编号1-8块的信息，客户端的视距范围建议不超过块的宽度。这样设计的话：当走到0与4的边缘朝4的方向看去，不会看到10（10此时未加载数据）。当玩家从方格0移动到方格4，此时预加载方格3、10、11的信息。

简单来说就是更新玩家所在块与这个块其他八个方向块的信息，以这样的方式做地图加载。

 

那么地图如何分块

分块的方法很多，这里抛砖引玉介绍一种 – GeoHash

本文后续示例参考的算法实现代码为 点击这里 ，注意该算法实现与wiki样例有所区别，这里不额外讨论，主要是介绍算法思想。

首先关于地球地理信息的一些基础知识：

地球坐标轴上连接南北极经度(longitude -180~180)，纬度(latitude -90~90)

* 在纬度相等的情况下：
* 经度每隔0.00001度，距离相差约1米；
* 经度每隔0.0001度，距离相差约10米；
* 经度每隔0.001度，距离相差约100米；
* 经度每隔0.01度，距离相差约1000米；
* 经度每隔0.1度，距离相差约10000米。

* 在经度相等的情况下：
* 纬度每隔0.00001度，距离相差约1.1米；
* 纬度每隔0.0001度，距离相差约11米；
* 纬度每隔0.001度，距离相差约111米；
* 纬度每隔0.01度，距离相差约1113米；
* 纬度每隔0.1度，距离相差约11132米。

GeoHash主要思想就是把整个地球铺开当成一个平面，再将平面划分成很多个小块，每个小块由唯一的二进制标识，这个区域内的经纬度都对应这个唯一标识。

二进制标识如何生成？我们以想要标识经度18.76543纬度45.27886这个地方为例，首先看经度：

第一次迭代，经度范围-180~180，0为中点，18.76543落在区间(0~180，大区间-180~180右边)，二进制位置1

第二次迭代，经度范围0~180，90为中点，18.76543落在区间(0~90，大区间0~180左边)，二进制位置0，后续迭代参考下表：

迭代次数	bit(18.76543)	区间下限	中点	区间上限
1	1	-180	0	180
2	0	0	90	180
3	0	0	45	90
4	0	0	22.5	45
5	1	0	11.25	22.5
6	1	11.25	16.875	22.5
7	0	16.875	19.6875	22.5
8	1	16.875	18.28125	19.6875
9	0	18.28125	18.984375	19.6875
10	1	18.28125	18.6328125	18.984375
11	0	18.6328125	18.80859375	18.984375
12	1	18.6328125	18.720703125	18.80859375
13	1	18.720703125	18.7646484375	18.80859375
14	0	18.7646484375	18.78662109375	18.80859375
15	0	18.7646484375	18.775634765625	18.78662109375
16	0	18.7646484375	18.7701416015625	18.775634765625

 

 

 

 

 

 

 

 

 

 

 

 

 

那么对于经度来说，我们迭代16次，得到二进制1000 1101 0101 1000；

同理，纬度迭代16次，得到二进制1100 0000 0110 0101；

然后我们将经度二进制数插入到偶数位，纬度二进制数插入到奇数位，得到经度18.76543纬度45.27886块标识：

1101 0000 1010 0010 0011 0110 1001 0001（十六进制输出为：d0a23691）

我们就可以用一个int64_t存储的二进制标识，它最高支持32次迭代。

 

那么迭代多少次才合适呢

掌握一条规则：迭代的次数越多，分块就越多，分块越多，那么精度越高。以整个地球为例，总分块数量 = 4^迭代次数。

再打个比方：

比如我们迭代16次，那么地球会被划分成4^16=4294967296小块

其中一块按经度划分 360/2^16 = 0.005493，长大约549.3米；纬度划分 160/2^16 = 0.002747，宽大约304.9米；将块看成长方形精度为对角线的一半大约314米

接着这个数据，一块占面积549.3*304.9=167481.57平方米，中国960平方公里，那么需要960 000 000/167481.57=5732块（实际会比这个多一点，因为版图不规则）

当迭代次数为18时，5732*4*4=91712块

当迭代次数为17次时，精度=314/2=157米；迭代次数为18次时，精度=157/2=78.5米。

迭代次数越高精度越高，所以说根据实际需求选取合适的迭代次数比较关键。

 

最后

可以联想到技术点就这么多，其实没看过Pokemon-Go的源码，以上都是一些分析与猜测。不过我相信整体应该大同小异：D

（全文结束）

转载文章请注明出处：漫漫路 - lanindex.com