A星寻路中 节点对象的内存空间优化

这周做到超大地图寻路的时候,进行一次性能测试。在超大地图 5500 * 5500 的地图中,若每个网格的大小为 20 像素。 那么总共需要创建 col : 275, row : 275 个 Node 对象。 那么 单单Astar 的寻路样本数组中就包含了共75625个Node对象,这还不包括寻路中临时创建的open数组和close数组。 就75625个Node对象来说,需要占用的内存在6kb,由于avm进行gc的时机为程序请求新的内存空间,而程序自身又要大量空闲对象的时候,不是即时的。因此,当一个玩家快速的进行多次寻路后,由于之前的寻路的没有触发gc,导致内存中还驻留上一次保存的Node数据,其内存占用是几何级增长的,会达到十几MB。这显然是不科学的。
于是决定使用一种更加不科学的方法来解决这个问题。

即,使用int型而非Object对象来存储Node。好吧,这显然脱离了oop的思想,嘛~不过作为数据结构来说,一个int型可是比Object来说,省内存了多哦。
一个Node中一般保存3个数据,Col,Row,Walkable。
首先构建3个int:

1
2
3
4
5
var col : int = 200 << 24;
var row : int = 400 << 12;
var walkable : int = 1;
var result : int = col + row + walkable;
trace(result); //-937885695

讲解下,一个int是一个32位的数值,于是把32位抽象的拆分为 0-11 位保存 col 值, 12 – 23 位 保存 row 值, 24 – 32 位 保存 walkable 值。
将3个值合并后输出结果为 -937885695 。

当数据被保存为 -937885695 后,使用如下方法进行解析。

1
2
3
trace("col:",result >> 24 & 0xff); //200
trace("row:",result >> 12  & 0xfff); //400
trace("walkable:",result & 0xf); //1

解析的原理是 result 向右移位 24 位,然后与 0xff 进行比对,取出2进制中同位置中同为1的数。
例 1011 & 0011 , 结果为 0011 。
至于 为什么 col 与 0xff, row 与 0xfff, walkable 与 0xf 比较呢。
原因为 0xf 是十六进制,一个f的大小为16。
那么 col = 200 , 0xff(256) > 200 > 0xf(16), 0xfff(4096) > 400 > 0xff(256) , 0xf(16) > 1 > 0;

接下来是性能测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var num : Number = 100000;

var intVec:Vector.<int> = new Vector.<int>(num);
var objVec:Vector.<Object> = new Vector.<Object>(num);

var startMemory : Number = System.totalMemory;

var col : int = 200 << 24;
var row : int = 400 << 12;
var walkable : int = 1;


for(var i:int = 0; i < num ; i++)
{
    intVec[i] = new int(col + row + walkable);
}

trace("cast Memory:", (System.totalMemory - startMemory)); //cast Memory: 667648

startMemory = System.totalMemory;

for(i = 0; i < num ; i++)
{
    objVec[i] = {
        col : 200,
        row : 400,
        walkable : 1
    };
}

trace("cast Memory:", (System.totalMemory - startMemory)); //cast Memory: 8462336

测试中,同时创建10万个 int型 和 Object型。测试结果为 Object占用的内存空间是int的 12 倍。随着数据量的增大,内存差距会进一步拉开。
试想一下,在超大地图中,创建10 万个节点,值占用 667648B 的空间是非常令人兴奋的。

btw: 移位操作有很多很好用的地方 比如 200 >> 1 的结果为 200 / 2 或 200 * .5 。 在速度方面 >> 快于 * 快于 / 。
同时 200.00 >> 0 的结果为 200 ,是一种取整的方法。 速度方面 >> 快于 uint(value) 快于 Math.floor(value) 。
话说,还有一种更加更加不科学的优化方案,即将寻路信息draw在一张bmd上,然后通过取像素点的方式来判断行走信息,同时bmd提供一种将像素点转换成数据流的方法,而数据流又可以进行压缩。嘛~很神奇的样子的说。有兴趣的童鞋可以去研究研究哦。

发表评论

电子邮件地址不会被公开。 必填项已用*标注