|
|
本文标题的定语很重要，网络游戏和单机游戏中每个玩家的可利用资源差别极大。一般来说，网络游戏中，服务器端每个玩家占有2MHz的CPU、1KB/s的网络带宽，网络时延在10-500ms之间不等，内存中需要保留所有玩家引用到的数据；而单机游戏，单个玩家占用整个cpu，比网游中高1000倍，局域网12.5MB/s的带宽任意使用，时延也在1ms以下，内存中只需要存储很少的相关数据。
在整个游戏逻辑体系内，和显示引擎不同，所有数值都是以整数形式存储、传输和计算的。这是因为受到了内存和带宽占用的影响。所以，离散化所带来的精度损失，是我们面临的主要问题，也是本文讨论的主题。本文的具体分析其实很简单，但是牵涉面较广；在实际工作中权衡调整系统参数的时候，往往会忘记考虑某些因素。因此本文的另一个目的是试图将这些参数相互之间的影响系统化，以便日后查阅。
0. 名次约定
时间最小单位是帧（Frame），每秒帧数（FPS）
空间最小单位是点（Point），每米点数（PPM）
格子（Cell），每格点数（PPC）
区域（Region），每个区域的格子数（CPR）
1. 时间片划分
虽然说是时空划分，但其实绝大多数是在讨论空间划分。和时间有关的概念只有一个，就是每秒帧数（FPS）。帧数是什么，游戏为什么要按一帧一帧的方式运行，这些问题不在本文讨论范围内，假定读者都已经了解。下面讨论一下帧数的数值设定，受到了那些因素的影响。
1.1 操作时延
当移动指令到来时，并不是立即计算移动的，只是改变了角色的状态。到了计算下一帧的时刻，才统一计算所有角色的移动。因此，引入了指令到来时刻和下一帧计算时刻的时间差T1。从用户在客户端发出指令开始，依次的时延有：组包发送时延T2、网络时延T3、服务器平均接收周期T4，最后就是T1。从用户按键到最后服务器上的角色移动的时间差，就是这四项之和。T2、T4和客户端、服务端的网络库模型有关，一般极小，可以忽略（某些特殊模型，为了提高效率缓冲了数据，可能会带来10－50ms左右的时延）；T3是最重要的环节，一般在10－500ms；而T1的平均值等于1/(2*FPS)，比如10FPS就会带来50ms的平均时延，某些情况下甚至会大于T3。很明显，1FPS会带来500ms的时延，是绝对不可忍受的。
1.2 移动速度
每秒移动10米，和每十分之一秒移动1米，是完全不同的。
速度是距离/时间，因此速度的精度和时间、空间两者的精度相关。比如，我们要求速度最小可以达到0.1m/s，在FPS＝10的时候，就要求空间精度达到1cm，即PPM>=100；否则由于相关数值都是离散化的整数，每帧连一个距离单位都不到，速度就变成零了。其实，最小速度并不能这样确定，由于角度的离散化，这样计算出来的最小速度只能在4个轴上精确的达到，而在其他方向上精度损失非常大，具体分析后详。
在垂直方向上，我们还需要计算每帧的重力加速度。假设X点＝1米，Y帧＝1秒，那么重力加速度G＝10m/s^2＝10X/(Y^2)。在以点每帧平方为单位时，整数G必须大于等于1。假设FPS＝10，则10X/100>=1，X>=10；FPS＝20，则X>=40。很明显，提高帧数后，距离的精度要求呈平方倍增长。如果我们希望改变每个角色受到的重力加速度，那么精度要求就会进一步提高。例如要求以1m/s^2的精度修改G，那么在FPS＝10时，要求PPM>=100；FPS＝20，要求PPM>=400。
1.3 攻击速度
攻击速度不可能有1秒10次那么高，但是由于攻击速度反映了攻击力，而攻击力常常需要按照1％的比例增长，所以攻击速度需要1秒10次以上的精度。需要注意的是，攻击速度一般以两次攻击之间的间隔TA表示，TA的最小单位是帧，而TA是处于攻击力计算公式的分母上的，因此TA的线性增长，对攻击力的影响并不是线性的，这往往导致了对FPS的更高要求。和攻击速度类似，具体游戏内容中还可能有这样的时间精度需求，其变化量往往都需要较高的精度。
1.4 CPU开销
随着FPS的提高，CPU的开销呈线性增长。对于网络游戏来说，单个玩家占有的CPU是十分少的，因此在权衡利弊时提高FPS并不是明智之举。
2. 角度划分
在2D游戏中，一般需要准备8方向或者16方向的图片，供显示之用。这样的精度并不能满足逻辑计算的要求。我们在进行移动计算时，需要根据方向，查表获取对应的sin和cos数值，然后计算出新的坐标点。
2.1 子弹的飞行碰撞
先看下面的64方向图：
24 24 23 23 22 22 21 21 20 20 19 19 18 18 17 16 16 15 14 13 13 12 12 11 11 10 10 9 9 8 8 8
24 24 24 23 23 22 22 21 21 20 20 19 18 18 17 16 16 15 14 13 13 12 11 11 10 10 9 9 8 8 8 7
25 24 24 24 23 23 22 22 21 21 20 19 19 18 17 16 16 15 14 13 12 12 11 10 10 9 9 8 8 8 7 7
25 25 24 24 24 23 23 22 21 21 20 20 19 18 17 16 16 15 14 13 12 11 11 10 10 9 8 8 8 7 7 6
25 25 25 24 24 24 23 22 22 21 21 20 19 18 17 16 16 15 14 13 12 11 10 10 9 9 8 8 7 7 6 6
26 26 25 25 24 24 24 23 22 22 21 20 19 18 18 17 16 14 13 13 12 11 10 9 9 8 8 7 7 6 6 5
26 26 26 25 25 25 24 24 23 22 21 21 20 19 18 17 16 14 13 12 11 10 10 9 8 8 7 6 6 6 5 5
27 27 26 26 26 25 25 24 24 23 22 21 20 19 18 17 16 14 13 12 11 10 9 8 8 7 6 6 5 5 5 4
27 27 27 26 26 26 25 25 24 24 23 22 21 20 18 17 16 14 13 11 10 9 8 8 7 6 6 5 5 5 4 4
28 28 27 27 27 26 26 26 25 24 24 23 21 20 19 17 16 14 12 11 10 8 8 7 6 5 5 5 4 4 4 3
28 28 28 28 27 27 27 26 26 25 24 24 22 21 19 18 16 13 12 10 9 8 7 6 5 5 4 4 4 3 3 3
29 29 29 28 28 28 28 27 27 26 26 25 24 22 20 18 16 13 11 9 8 6 5 5 4 4 3 3 3 3 2 2
30 29 29 29 29 29 29 28 28 27 27 26 25 24 21 19 16 12 10 8 6 5 4 4 3 3 2 2 2 2 2 2
30 30 30 30 30 30 29 29 29 29 28 28 27 26 24 20 16 11 8 5 4 3 3 2 2 2 2 1 1 1 1 1
31 31 31 31 31 31 30 30 30 30 30 29 29 28 27 24 16 8 4 3 2 2 1 1 1 1 1 0 0 0 0 0
32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
32 32 32 32 32 32 33 33 33 33 33 34 34 35 36 40 48 56 59 60 61 61 62 62 62 62 62 63 63 63 63 63
33 33 33 33 33 33 34 34 34 34 35 35 36 37 40 43 48 52 56 58 59 60 60 61 61 61 61 62 62 62 62 62
33 34 34 34 34 34 34 35 35 36 36 37 38 40 42 44 48 51 53 56 57 58 59 59 60 60 61 61 61 61 61 61
34 34 34 35 35 35 35 36 36 37 37 38 40 41 43 45 48 50 52 54 56 57 58 58 59 59 60 60 60 60 61 61
35 35 35 35 36 36 36 37 37 38 39 40 41 42 44 45 48 50 51 53 54 56 56 57 58 58 59 59 59 60 60 60
35 35 36 36 36 37 37 37 38 39 40 40 42 43 44 46 48 49 51 52 53 55 56 56 57 58 58 58 59 59 59 60
36 36 36 37 37 37 38 38 39 40 40 41 42 43 45 46 48 49 50 52 53 54 55 56 56 57 57 58 58 58 59 59
36 36 37 37 37 38 38 39 40 40 41 42 43 44 45 46 48 49 50 51 52 53 54 55 56 56 57 57 58 58 58 59
37 37 37 38 38 38 39 40 40 41 42 42 43 44 45 46 48 49 50 51 52 53 53 54 55 56 56 57 57 57 58 58
37 37 38 38 39 39 40 40 41 41 42 43 44 45 45 46 48 49 50 50 51 52 53 54 54 55 56 56 56 57 57 58
38 38 38 39 39 40 40 41 41 42 42 43 44 45 46 47 48 48 49 50 51 52 53 53 54 54 55 56 56 56 57 57
38 38 39 39 40 40 40 41 42 42 43 43 44 45 46 47 48 48 49 50 51 52 52 53 53 54 55 55 56 56 56 57
38 39 39 40 40 40 41 41 42 42 43 44 44 45 46 47 48 48 49 50 51 51 52 53 53 54 54 55 55 56 56 56
39 39 40 40 40 41 41 42 42 43 43 44 45 45 46 47 48 48 49 50 50 51 52 52 53 53 54 54 55 55 56 56
39 40 40 40 41 41 42 42 43 43 44 44 45 45 46 47 48 48 49 50 50 51 51 52 52 53 53 54 54 55 55 56
40 40 40 41 41 41 42 42 43 43 44 44 45 46 46 47 48 48 49 49 50 51 51 52 52 53 53 54 54 54 55 55
例如在45度方向上，目标点A（15，15）和B（13， 15）对应与原点的角度都是8，假设目标在B点，而从原点出发按照方向8飞行的子弹，却是向着A点飞行的，如果子弹的碰撞范围很小，那么很可能碰撞检测时错过了在B点的目标。距离更远表更大后，如果要确保碰撞，那么必须加大碰撞检测范围。看了下面的16方向图，就会更加明了这种问题了。
6 6 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2
6 6 6 5 5 5 5 5 5 5 5 4 4 4 4 4 4 3 3 3 3 3 2 2 2 2 2 2 2 2 2 1
6 6 6 6 5 5 5 5 5 5 5 4 4 4 4 4 4 3 3 3 3 3 2 2 2 2 2 2 2 2 1 1
6 6 6 6 6 5 5 5 5 5 5 5 4 4 4 4 4 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1
6 6 6 6 6 6 5 5 5 5 5 5 4 4 4 4 4 3 3 3 3 2 2 2 2 2 2 2 1 1 1 1
6 6 6 6 6 6 6 5 5 5 5 5 4 4 4 4 4 3 3 3 3 2 2 2 2 2 2 1 1 1 1 1
6 6 6 6 6 6 6 6 5 5 5 5 5 4 4 4 4 3 3 3 2 2 2 2 2 2 1 1 1 1 1 1
6 6 6 6 6 6 6 6 6 5 5 5 5 4 4 4 4 3 3 3 2 2 2 2 2 1 1 1 1 1 1 1
6 6 6 6 6 6 6 6 6 6 5 5 5 5 4 4 4 3 3 2 2 2 2 2 1 1 1 1 1 1 1 1
7 7 6 6 6 6 6 6 6 6 6 5 5 5 4 4 4 3 3 2 2 2 2 1 1 1 1 1 1 1 1 0
7 7 7 7 6 6 6 6 6 6 6 6 5 5 4 4 4 3 3 2 2 2 1 1 1 1 1 1 1 0 0 0
7 7 7 7 7 7 7 6 6 6 6 6 6 5 5 4 4 3 2 2 2 1 1 1 1 1 0 0 0 0 0 0
7 7 7 7 7 7 7 7 7 6 6 6 6 6 5 4 4 3 2 2 1 1 1 1 0 0 0 0 0 0 0 0
7 7 7 7 7 7 7 7 7 7 7 7 6 6 6 5 4 2 2 1 1 0 0 0 0 0 0 0 0 0 0 0
7 7 7 7 7 7 7 7 7 7 7 7 7 7 6 6 4 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 10 12 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15
8 8 8 8 8 8 8 8 8 8 8 8 9 9 10 10 12 13 14 14 14 15 15 15 15 15 15 15 15 15 15 15
8 8 8 8 8 8 8 8 8 9 9 9 9 10 10 11 12 12 13 14 14 14 14 14 15 15 15 15 15 15 15 15
8 8 8 8 8 8 8 9 9 9 9 9 10 10 10 11 12 12 13 13 14 14 14 14 14 14 15 15 15 15 15 15
8 8 8 8 9 9 9 9 9 9 9 10 10 10 11 11 12 12 12 13 13 14 14 14 14 14 14 14 14 15 15 15
8 8 9 9 9 9 9 9 9 9 10 10 10 10 11 11 12 12 12 13 13 13 14 14 14 14 14 14 14 14 14 15
9 9 9 9 9 9 9 9 9 10 10 10 10 10 11 11 12 12 12 13 13 13 13 14 14 14 14 14 14 14 14 14
9 9 9 9 9 9 9 9 10 10 10 10 10 11 11 11 12 12 12 12 13 13 13 13 14 14 14 14 14 14 14 14
9 9 9 9 9 9 9 10 10 10 10 10 10 11 11 11 12 12 12 12 13 13 13 13 13 14 14 14 14 14 14 14
9 9 9 9 9 9 10 10 10 10 10 10 11 11 11 11 12 12 12 12 12 13 13 13 13 13 14 14 14 14 14 14
9 9 9 9 9 10 10 10 10 10 10 10 11 11 11 11 12 12 12 12 12 13 13 13 13 13 13 14 14 14 14 14
9 9 9 9 10 10 10 10 10 10 10 10 11 11 11 11 12 12 12 12 12 13 13 13 13 13 13 13 14 14 14 14
9 9 9 10 10 10 10 10 10 10 10 11 11 11 11 11 12 12 12 12 12 12 13 13 13 13 13 13 13 14 14 14
9 9 10 10 10 10 10 10 10 10 10 11 11 11 11 11 12 12 12 12 12 12 13 13 13 13 13 13 13 13 14 14
9 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 14
10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13
因此，我们需要根据子弹飞行的最远距离D，和最小碰撞检测范围R，计算出所需的角度划分精度。假设子弹最远飞行32米，由于碰撞检测的单位是格子而不是点（具体分析后详），如果每个格子是一米的话，最远距离D＝32；要求子弹正好碰上目标，这样的要求太高也没有必要，所以碰撞检测范围R>=1，也就是说64方向图中方向7和9是可以接受的（不过距离只有16）。此外，为了避免除法，我们要求角度划分为2的整数次幂。最后经过试验表明，划分成256方向，可以满足以上要求。距离32的256方向图就不贴了，太大了。
2.2 长距离移动路线
当两点之间距离很远时，可以约减至给定的方向图范围内。但是，这样计算出来的移动路线并不是直线，而是像下图中0所标识的折线
7 7 7 7 7 7 7 7 7 6 6 6 6 6 5 4 4 3 2 2 1 1 1 1 0 0 0 0 0 0 0 0
7 7 7 7 7 7 7 7 7 7 7 7 6 6 6 5 4 2 2 1 1 0 0 0 0
7 7 7 7 7 7 7 7 7 7 7 7 7 7 6 6 4 2 1 0 0 0
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 0 0 0 0
这个问题对于玩家来说并不严重，因为玩家不会进行长距离的移动，但是对于会巡逻的npc来说，如果巡逻路径中两点之间距离过远，那么实际路径可能会和想象中的大相径庭。虽然提高角度划分的精度和表的大小，可以获得很好的效果，但是考虑到cpu的cache命中，方向表不宜太大，应该控制在8K以内。因此，在路径上多加几个中间点，是比较合理的解决方法。
2.3 低速移动的速度损失
严格说来，这个问题并不是由于角度的离散化导致的，而是由于距离的离散化导致的。
在第一节中讨论移动速度时，就说到了角度划分对移动速度有影响，现举例说明如下：
假设FPS＝10，最低移动速度0.1m/s，则要求的最低PPM＝10。当移动速度为0.1m/s时，每帧移动1点，如果移动方向为0度，那么很轻松的在X轴上右移一点；如果移动方向变成了除0、90、180、270之外的其他度数，那么计算出来的sin和cos值都会小于1，最后整除出来的结果就变成0了，实际速度也变成了0。
假设速度为V1点每帧，移动方向为X，那么每帧的实际移动距离为V2 ＝ sqrt((floor(V1 * cosX))^2 + (floor(V1 * sinX))^2)
定义(V1 - V2) / V1 为速度损失百分比，V1和X的变化对该百分比的影响见下图：
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16 100 25 18 10 5 2 3 7 5 3 2 2 1 4 3 3
32 100 6 15 19 6 10 2 6 0 3 6 2 4 0 2 4
48 100 25 18 10 5 2 3 7 5 3 2 2 1 4 3 3
64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
80 100 25 18 10 5 2 3 7 5 3 2 2 1 4 3 3
96 100 6 15 19 6 10 2 6 0 3 6 2 4 0 2 4
112 100 25 18 10 5 2 3 7 5 3 2 2 1 4 3 3
128 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
144 100 25 18 10 5 2 3 7 5 3 2 2 1 4 3 3
160 100 6 15 19 6 10 2 6 0 3 6 2 4 0 2 4
176 100 25 18 10 5 2 3 7 5 3 2 2 1 4 3 3
192 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
208 100 25 18 10 5 2 3 7 5 3 2 2 1 4 3 3
224 100 6 15 19 6 10 2 6 0 3 6 2 4 0 2 4
240 100 25 18 10 5 2 3 7 5 3 2 2 1 4 3 3
其中，第一列为对应的角度（256等分），第一行为速度，剩下的为该角度和速度时的损失百分比。
由上图可见，当速度很小V1<10，速度损失非常大，实际的移动速度只有75%-90%。因此，最小移动速度，应该在10点每帧之上，甚至20点每帧，方可忽略这一影响。
在FPS＝10时，要达到0.01m/s的最低移动速度，要求的PPM高达1000（过高的PPM会带来的影响见后文）。这时，我们有了区分最低移动速度和最小速度改变量的需求。实际设计中，我们并不需要那么低的移动速度，0.1m/s已经可以满足绝大多数要求了，但是对于增加1％移动速度的道具来说，就会需要更高的精度来区分。当我们将数值设定的需求细分成这两个方面时，就比较容易处理了。
|
|
发表于 2006-6-3 18:36:00
楼主