Pokemon-Go地图技术猜想

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

Pokemon-Go总体分析

pokermongo地图图片

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

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

实现核心技术点:地图绘制,地图分块

 

 

地图绘制

类似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应该也类似。如下图:

LBS方格

解释一下,玩家上线之初在位置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

Leave a Comment

Your email address will not be published.