对于基于格子的mmorpg来说,按照格子来存储周围所见的物件,是一个比较好的选择。
但是,由于主角的移动,常常要对格子里的物件进行搬移,这大大影响了处理效率。
今天介绍一种方法来优化这个搬移操作。
(1)- 名字
偏移网格,从字面上来讲,就是使用偏移量来进行处理和计算的网格。实际上,也是这么做的。这个方法保存了角色看得到的格子里的所有物件,并且确保离开视野的物件被及时地清理出去,以及在这个视野切换过程中不动的物件牢牢地呆在原地,而不用对他们进行搬移。
(2)- 原理
首先,让我们先来看看下面这张图示(简单起见,只假设玩家能看到1格的范围):
一开始,我们的主角在 5 号位置,他能看到 1 2 3 4 5 6 7 8 9 这9个格子的物件。接下来,他移动到了9号位置,他现在看不到1,2,3,4,7格内的物件了,而他又看到了 A,B,C,D,E 格内的东西。
这个过程中,如果用老方法,我们需要把一个 3 x 3 的格子数组中的 5,6,8,9 格子内的物件搬移到原来 1,2,4,5 的格子内,同时还要清理那里原来的物件。然后清理 3,6,9,8,7格子,把 A, B, C, D, E 格子中的物件丢到原来 3, 6, 9, 8, 7 的格子内。
现在,我们换一种思路,原来1号格子,做为数组的原点,而现在,我们分离出两个原点:一个物理原点,也就是格子数组的起始点;另一个是逻辑原点,也就是当前主角的可是范围的原点。在从 5 到 9 的移动完成之后,5 就变成了主角的逻辑原点了,那么这个逻辑原点记作(1,1),也就是表示,主角可视范围的原点是在物理数组的 (1,1)位置上。这时候,我们就不用去进行 5,6,8,9 到 1,2,4,5 的搬移了,因为他们在逻辑原点所确定的视觉范围内的位置已经随着逻辑原点从位置1(0,0)到位置5(1,1)的更新而更新了。那么,接下来,就是去安排新看到的 A,B,C,D,E了。这里用的是一个循环计数,也就是当物理格子数组越界之后,把他们折到数组界内,比如字节范围内的 254+2 之后,会被折返成 254+2-255 = 1。这里,他们被折返到原来 1,2,3,4,7 的位置。
经过这样一个过程之后,我们看到,新的思路下,我们会减少4次搬移的操作,这扩展到正常数量的格子之后,我们可以消减掉很大的一个双重循环和搬移操作。
(3)- 总结
从图上可以看出,这个算法的精髓就是用两个网格数组和一个偏移进行工作,从而减少一些实际的操作。也正是因为如此,所以,我才叫这个方法是偏移网格。