月度归档:2014年02月

网络游戏的移动同步(四)帧锁定算法

引言

我一直想了解早期游戏的网络同步,特别是早期的很多对战平台,做了很多单机游戏的对战,而这些同步又可以达到很不可思议的效果。从网络上我得知这种方案叫帧锁定,即保证每帧都是一致的。否则就锁定。比如玩dota时出现的万恶的等待框,本篇文章就希望简单的从客户端代码层面模拟这个过程(实际上到最后,我觉得纯粹用客户端模拟还是不足),另外作为整个网络同步系列的最后一个章节。

基本原理

对于单机游戏或者可联网的局域网游戏来说,大部分是没有服务器的,所有的游戏逻辑都放在客户端中处理,这导致的,只要每个用户所给的输入一致,时间一致,就能达到同样的模拟效果,所以帧锁定的基本原理便是如此。

算法流程

1.客户端定时(比如每五帧)上传控制信息。

2.服务器收到所有控制信息后广播给所有客户。

3.客户端用服务器发来的更新消息中的控制信息进行游戏。

4.如果客户端进行到下一个关键帧(5帧后)时没有收到服务器的更新消息则等待。

5.如果客户端进行到下一个关键帧时已经接收到了服务器的更新消息,则将上面的数据用于游戏,并采集当前鼠标键盘输入发送给服务器,同时继续进行下去。

6.服务端采集到所有数据后再次发送下一个关键帧更新消息。

C/S逻辑

客户端逻辑:

1. 判断当前帧F是否关键帧K1:如果不是跳转(7)。

2. 如果是关键帧,则察看有没有K1的UPDATE数据,如果没有的话重复2等待。

3. 采集当前K1的输入作为CTRL数据与K1编号一起发送给服务器

4. 从UPDATE K1中得到下一个关键帧的号码K2以及到下一个关键帧之间的输入数据I。

5. 从这个关键帧到下 一个关键帧K2之间的虚拟输入都用I。

6. 令K1 = K2。

7. 执行该帧逻辑

8. 跳转(1)

服务端逻辑:

1. 收集所有客户端本关键帧K1的CTRL数据(Ctrl-K)等待知道收集完成所有的CTRL-K。

2. 根据所有CTRL-K,计算下一个关键帧K2的Update,计算再下一个关键帧的编号K3。

3. 将Update发送给所有客户端

4. 令K1=K2

5. 跳转(1)

客户端模拟代码

// 如果当前是关键帧
if (Global.frame == keyFrame) {
    // 查看是否有服务器的更新包,当前关键帧编号,下一关键帧编号,所有玩家的控制信息
    // 获取更新包
    var rp:PlayerInputPack;
    while (client.packets.length > 0) {
        rp = client.packets.shift();
        if (rp.frame == keyFrame) {
            break;
        }
    }
    // 如果等不到当前帧的控制数据,则返回
    if (rp && rp.frame == keyFrame) {
        var nextFrame:int = keyFrame + 5;
        // 采集当前的输入作为包发送
        var p:PlayerInputPack = new PlayerInputPack();
        p.frame = nextFrame;
        p.input = InputManager.instance.keyStatus;
        client.send(p);

        // 以rp.input做输入数据
        // 模拟移动本地及网络客户端
        // 每个客户端的逻辑一致
        var players:Array = [localPlayer, netPlayer];
        for each (var player:Player in players) {
            player.velocity.x = 0;
            player.velocity.y = 0;

            if (rp.input[Keyboard.LEFT]) {
                player.velocity.x = -player.speed;
            }
            if (rp.input[Keyboard.RIGHT]) {
                player.velocity.x = player.speed;
            }
            if (rp.input[Keyboard.UP]) {
                player.velocity.y = -player.speed;
            }
            if (rp.input[Keyboard.DOWN]) {
                player.velocity.y = player.speed;
            }
        }

        // 下一个关键帧
        keyFrame = nextFrame;
        waitTime = 0;
    } else {
        waitTime += Global.elapse;

        // 等待太久了,类似魔兽争霸的那个超时面板
        if (waitTime > 1000) {
            trace('等待不到控制包信息', keyFrame);
        }
    }
} else {
    // 当前帧步进
    Global.frame++;
}

// 更新场景
localScene.update();
netScene.update();

演示

Get Adobe Flash player

总结

可以从flash演示中看到,两个场景在低延迟的情况下同步效果非常理想,甚至远远超过之前的客户端预测例子,不过这种做法的缺点就是当延迟过大时会极大的影响控制手感,另外延迟受最慢的客户端影响。

当服务器迟迟没有收到每五帧的所有控制输入时,就会发送通知给所有客户端,出现dota或者war3联网时的那个网络延迟框。在war3中,因为没有专门服务器,所以这个责任是由主机承担的。

对于游戏中的随机元素,则可以在游戏初始化时,由主机同步随机种子到所有客户端中。

参考文献

网络游戏的移动同步(三)平滑算法

引文

本篇文章想解决的是引入航位预测后,预测位置与当前位置出现偏差的平滑处理算法,如第一篇所做的简单跳跃的话,会出现很不舒服的跳跃,这里用一些常用的插值方法解决那些生硬的跳跃。

一些问题

插值平滑就是处理p0插值到p1的问题,但是在游戏中,这难免会出现一些问题,比如我们在处理位置插值时,如何处理p0到p1与碰撞检测系统的冲突?如何选择更为合适的插值方法?

线性插值

我们先选择简单的线性插值,在代码中做如下更改,记录下目标位置,初始位置及时间。

var delta:Number = (getTimer() - rp.time) / 1000;

netPlayer.targetPos = new Vector2().addVectors(rp.position, rp.velocity.clone().multiply(delta).add(rp.acceleration.clone().divide(2).multiply(delta * delta)));
netPlayer.startPos = netPlayer.position.clone();
netPlayer.velocity = rp.velocity.clone();
netPlayer.acceleration = rp.acceleration.clone();
netPlayer.method = 2;
netPlayer.smoothTick = netPlayer.smoothTime = delta;

这里我做了一下比较特别的处理,首先目标位置并不是发来的位置,而是发来的位置加上延迟时间内又移动的距离,所以目标位置稍微远一些,另外平滑时间我设置成于延迟时间相关,所以延迟越大平滑时间越长。

在玩家类中,需要通过平滑计时来判断当前在平滑阶段,还是普通的预测阶段,代码如下。

if (smoothTick > 0) {
    smoothTick -= Global.elapse / 1000;
    var dt:Number = 1 - smoothTick / smoothTime;
    position.x = startPos.x + (targetPos.x - startPos.x) * dt;
    position.y = startPos.y + (targetPos.y - startPos.y) * dt;
} else {
    if (! acceleration.isZero()) {
        velocity.x += acceleration.x * Global.elapse / 1000;
        velocity.y += acceleration.y * Global.elapse / 1000;
    }
    if (! velocity.isZero()) {
        position.x += velocity.x * Global.elapse / 1000;
        position.y += velocity.y * Global.elapse / 1000;
    }
}

从代码中可以看到,位置可以从两个阶段得到,当在插值阶段时,使用的是插值计算出的值,如果不在插值阶段,则为状态计算出的值。最终效果如下。

Get Adobe Flash player

可以看到有了平滑的算法后,网络场景的物体看起来不那么生硬了,不过平滑的时候,你会发现平滑的方向跟速度方向不一致,看起来很不自然。下面的平滑算法会做得更好一些。

立方样条插值

选择使用这种插值方式的原因是,这种插值使得插值路径更加真实,自然,可参加如下图

cube_splines

这里可以看到当前速度,期望最终速度都位移插值路径的最终切线上,与期望值一致。

实现这个插值需要4个坐标值。

坐标1:开始位置(即本地当前位置)

坐标2:坐标1经过一定时间后的位置(速度为当前速度)

坐标4:最终位置(即网络协议发送的最新位置加上一定的延迟时间后的位置)

坐标3:坐标4反向移动一定时间后的位置(速度为网络最新速度)

插值坐标公式为:

x = At3 + Bt2 + Ct + D

y = Et3 + Ft3 + Gt + H

其中

A = x3 – 3x2 +3x1 – x0

B = 3x2 – 6x1 + 3x0

C = 3x1 – 3x0 D = x0

E = y3 – 3y2 +3y1 – y0

F = 3y2 – 6y1 + 3y0

G = 3y1 – 3y0

H = y0

cube_spline2

代码修改

var delta:Number = (getTimer() - rp.time) / 1000;
// 预测点,在延迟时间5倍以后
// 延迟越严重,预测越远
var scheduled:Number = delta * 5;
scheduled = Math.min(scheduled, 0.8);

var pos1:Vector2 = netPlayer.position.clone();
var pos2:Vector2 = new Vector2().addVectors(pos1, netPlayer.velocity.clone().multiply(0.1));
var pos4:Vector2 = new Vector2().addVectors(rp.position, rp.velocity.clone().multiply(scheduled).add(rp.acceleration.clone().divide(2).multiply(scheduled * scheduled)));
var pos3:Vector2 = new Vector2().subVectors(pos4, rp.velocity.clone().add(rp.acceleration.clone().multiply(scheduled)).multiply(0.1));

netPlayer.smoothTick = netPlayer.smoothTime = scheduled;
netPlayer.A = pos4.x - 3 * pos3.x + 3 * pos2.x - pos1.x;
netPlayer.B = 3 * pos3.x - 6 * pos2.x + 3 * pos1.x;
netPlayer.C = 3 * pos2.x -  3 * pos1.x;
netPlayer.D = pos1.x;

netPlayer.E = pos4.y - 3 * pos3.y + 3 * pos2.y - pos1.y;
netPlayer.F = 3 * pos3.y - 6 * pos2.y + 3 * pos1.y;
netPlayer.G = 3 * pos2.y -  3 * pos1.y;
netPlayer.H = pos1.y;

// 插值位置
position.x = A * dt * dt * dt + B * dt * dt + C * dt + D;
position.y = E * dt * dt * dt + F * dt * dt + G * dt + H;

示例

Get Adobe Flash player

加权平均插值

这个在之前的插值介绍中提过,这种插值方式最简单,不需要记录dt,只需要记录期望位置即可。至于具体实现及方案,我将与下面的碰撞检测检测冲突一起给出。

碰撞检测冲突

目前插值的目标都是position,但是如果仅仅是对此值进行插值会存在一些问题,比如position.x = 1,期望位置为position.x = 3,而恰巧position.x = 2的位置是一个障碍点,那插值会导致与碰撞检测代码冲突,这种情况非常容易出现。

我处理这个问题的方案是,插值对象更改,更改为一个修正值modify。而在最终位置的选取上position要加上这个modify,这样插值可以跟碰撞检测规避开。

具体的实现如下

// 设置修正只
netPlayer.modify.x = netPlayer.x - rp.position.x;
netPlayer.modify.y = netPlayer.y - rp.position.y;
//如果位置偏差实在过大,直接跳跃
if (netPlayer.modify.lengthSQ > 50 * 50) {
    netPlayer.modify.set(0, 0);
}
// 注意这里直接设置到了期望位置
netPlayer.position.x = rp.position.x;
netPlayer.position.y = rp.position.y;
netPlayer.velocity = rp.velocity.clone();
netPlayer.acceleration = rp.acceleration.clone();

// 玩家更新代码
var smoothFactor:Number = 0.075;
// 修正值平滑
modify.x *= (1 - smoothFactor);
modify.y *= (1 - smoothFactor);

// 显示位置
x = position.x + modify.x;
y = position.y + modify.y;

这个很酷的方案最终效果如下

Get Adobe Flash player

这种方案的好处是更新过程不需要区分插值过程与预测计算过程,也不需要记录dt,代码显得比较间接,过渡相对比较平滑,不会与游戏其他系统相互冲突。

停止的不自然

之前的例子因为都有延迟波动的影响,所以停止过程经常出现不舒服的回拉,这个解决方案比较简单,如果停止时位置波动在某个阈值内,则不进行插值平滑即可。

最终效果全集

Get Adobe Flash player

参考

网络游戏的移动同步(二)状态更新及航位预测法

引言

前一篇文章将基本的网络同步例子制作出来,虽然还有很多问题,但是我们已经在网络问题很简易的摆放在我们面前,不需要经过服务器,就可以简单的模拟经常出现的网络延迟现象,那对于之前演示的问题,如何解决呢?今天就解决第一步,发包的问题。如果能够节省发包量?

状态更新

因为每个客户端都有自己的逻辑运算,所以我们很明显的就可以想到,只需要在状态更新时发送即可,对于一般的游戏这个方案都可以解决,比如我们修改速度的时候,游戏点击目标点的时候,这些时间点发送即可,对于之前的例子,我们只需要做如下判断就可以节省大量的通讯量。

// 获取输入
// 在通过键盘获取输入更新最新速度前
var lastVelocity:Vector2 = localPlayer.velocity.clone();
var lastAcceleration:Vector2 = localPlayer.acceleration.clone();

if (lastVelocity.x != localPlayer.velocity.x ||
    lastVelocity.y != localPlayer.velocity.y ||
    lastAcceleration.x != localPlayer.acceleration.x ||
    lastAcceleration.y != localPlayer.acceleration.y) {
    update = true;
}

if (update) {
    var p:PlayerStatePack = new PlayerStatePack();
    p.velocity = localPlayer.velocity.clone();
    p.position = localPlayer.position.clone();
    p.acceleration = localPlayer.acceleration.clone();
    p.time = getTimer();
    client.send(p);
}

我们再看现在的demo,通讯量明显下来了,而且网络场景走得也不差。

Get Adobe Flash player

当然,这个方案也是有其局限性的,比如如果加速度存在的话,那速度每时每刻是不一样的,所以发包频率还是非常频繁,还有一种更极端的情况,如果你加入了物理引擎,或者使用了自治智能体,此时连加速度都每时每刻在变化的,有没什么更好的方式来优化通讯量呢?下面引出下一个优化方案,航位预测法(DeadReckoning)。

航位预测法(DeadReckoning)

这种算法比较的主要是位置,而非上面的速度以及加速度,所以从通用性上来说,会好很多。具体的细节为,当本地个体与记录的上次本地个体(即其他网络场景看到的自己)的位置超过某个阈值,则发送更新状态包,当此阈值越小,则发送包频率越快,此阈值越大,则发送包频率越慢,也越节省。

基本的原理可参考如下图(从网络获取)

dr

基本实现代码如下

// dr位置
var drPosition:Vector2 = new Vector2();
if (lastState) {
    var e:Number = (getTimer() - lastStateTime) / 1000;
    // s = v0t + 0.5 * a * t^2;
    drPosition.addVectors(lastState.position, lastState.velocity.clone().multiply(e).add(lastState.acceleration.clone().divide(2).multiply(e * e)));
}
// 阈值
var threshold:Number = 5 * 5;
if (localPlayer.position.distSQ(drPosition) > threshold) {
    update = true;
}

代码很简单,就是牛顿力学的内容,位移,加速度,速度的公式,然后算出dr位置(即网络位置),如果超过阀值,则发送更新包,另外记录上次发送状态(为了计算下一次dr位置)。

演示如下

Get Adobe Flash player

应用

在游戏中,状态更新及航位预测可混合使用,如在键盘更新时,即可将状态更新包发出,而非一定要等到位置偏移超过一定值,这样网络网络场景看到的会更即时些。本章将发包的问题解决了,但是你可以在演示中看出,当网络延迟波动较大时,网络场景的物体拖拉很生硬,因为我们直接设置了网络场景的位置到了当前位置,下一部分介绍如何用插值平滑将网络延迟做进一步的遮掩。

参考文献

网络游戏的移动同步(一)网络同步演示

引言

网络游戏的同步处理是在制作网络游戏中独有的处理方案,现在网络游戏几乎都是C/S架构,也就是说需要同步其他主机发送给服务器,并转发回本机的包,这里就涉及到如何发包给服务器,发哪些包,另外就是接收到这些包之后,客户端如何处理这些包的问题。

在不进行示例之前,如果简单的思考一下这些问题,一般人都会想到的是,其实只需要发布初始状态,然后每次变更发送更新状态即可。为了使这个问题简单化,本文的处理主要是移动同步,这个也是最常见,并且包量最大的一个协议,下面我们先创建这个更新包。

简单的更新协议

public class PlayerStatePack
{
	public var velocity:Vector2;
	public var position:Vector2;
	public var acceleration:Vector2;
	public var time:uint;
}

3个2维向量分别是位置,速度,加速度,此示例以2维为主,一般游戏可能用加速度比较少一些,但是为了更好的模拟更多的游戏,比如一些赛车或者炮弹之类的,这里的更新包中还有加速度。时间是发送包的时间,加这个主要是为了接收方能预知此时的真实位置。因为接收到的时候,发送方实际已经不在那个位置。

虚拟服务器

为了在客户端中直接模拟服务器延迟,可以直接做个简单的类模拟延迟。

public class Client
{
	// 模拟收到的网络包
	public var packets:Vector.;

	public function Client()
	{
		packets = new Vector.();
	}

	public function send(p:PlayerStatePack):void {
		// 延迟加入队列
		var delayTime:int = MathUtil.rand(Global.delay - Global.range, Global.delay + Global.range);

		setTimeout(sendNow(p), delayTime);
	}

	private function sendNow(p:PlayerStatePack):Function
	{
		return function():void {
			packets.push(p);
		}
	}
}

类的功能很简单,就是发送的时候增加setTimeout,另外这里有两个配置量,延迟量以及延迟波动量,这两个即可比较好的模拟出真实的网络环境,接收方处理的时候,直接从packets数组中获取包处理即可。

第一次尝试

假设这是一个简单的键盘移动游戏,因为鼠标移动同步相对比较简单,甚至于包都可以不需要那么复杂,只需要目标点就可以。
我们开始写发送及接收处理的代码。主循环代码如下

// 一般的线性移动
localPlayer.velocity.x = 0;
localPlayer.velocity.y = 0;
if (InputManager.instance.keyDown(Keyboard.LEFT)) {
	localPlayer.velocity.x = -localPlayer.speed;
}
if (InputManager.instance.keyDown(Keyboard.RIGHT)) {
	localPlayer.velocity.x = localPlayer.speed;
}
if (InputManager.instance.keyDown(Keyboard.UP)) {
	localPlayer.velocity.y = -localPlayer.speed;
}
if (InputManager.instance.keyDown(Keyboard.DOWN)) {
	localPlayer.velocity.y = localPlayer.speed;
}
// 发送协议
var p:PlayerStatePack = new PlayerStatePack();
p.velocity = localPlayer.velocity.clone();
p.position = localPlayer.position.clone();
p.acceleration = localPlayer.acceleration.clone();
p.time = getTimer();
client.send(p);

while (client.packets.length > 0) {
	var rp:PlayerStatePack = client.packets.shift();
	// 直接拉扯
	if (smoothMethodCb.selectedIndex == 0) {
		netPlayer.position.x = rp.position.x;
		netPlayer.position.y = rp.position.y;
		netPlayer.velocity = rp.velocity;
	}
}

// 更新场景
localScene.update();
netScene.update();

看这个简单的游戏主循环,主要的流程是获取输入->本地玩家更新->发送更新包->接收更新包->处理游戏逻辑。为了使整个游戏代码清晰,我清理了不太需要的细节代码。

这个简单的网络同步演示如下

Get Adobe Flash player

这个演示明显有几个问题,比如发送包太频繁(停止也在发送,因为是每帧发送),另外接受包的处理也很生硬,当网络延迟波动过大,拉扯现象非常明显。