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

引言

我一直想了解早期游戏的网络同步,特别是早期的很多对战平台,做了很多单机游戏的对战,而这些同步又可以达到很不可思议的效果。从网络上我得知这种方案叫帧锁定,即保证每帧都是一致的。否则就锁定。比如玩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

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

插值那些事——译Interpolation Tricks

引言

插值这个概念是在几年前看到的,当时不是很理解,以为是一个数学概念就忽略了,实际上这个东西应用很多,特别是在游戏开发中,我们要做实时渲染,如果说只有0和1,中间没有过渡的话,一切都会显得很生硬,下面这篇文章是我看到的最好的解释这个概念及其应用的文章,传送门地址

插值技巧

或者说我如何做到停止烦恼并爱上0~1区间的

  1. 为什么是0…1这个范围

当在做游戏原型时我发现了许多不同的插值技巧,这些非常有价值,比如在各种移动中增加一些平滑,这些移动可以是摄像机,物体,灯光渐隐渐现等等,你会发现增加这些技巧之后会更加的令人享受。生硬的移动会让人觉得不舒服,应该极力避免。

一般说来,当做一些动画时,我们都会知道一个起始位置和终止位置,然后在他们中间可以进行一些过渡,所有的这些都可以转化为0到1的问题。(其实随机数也是类似的道理)

0值还有1值有很多有趣的属性,基于这些属性你可以拼接出任意开始和结束的值,正因为如此,所以我们只要把0到1的过程处理掉即可。

2. 开始进入0到1区间

如果我们希望将一个变量X从A移动到B点,通过N步,那我们应该写如下代码

for (i = 0; i < N; i++)
{
    X = ((B * i) + (A * (N - i))) / N;
}

或者我们重新写一下

for (i = 0; i < N; i++)
{
    t = i / N;
    X = (B * t) + (A * (1 - t));
}

这样看起来清楚多了吧?此时t的范围从0到1。

3. 线性插值(Linear Interpolation)

用N个离散步数从0移动到1被称为线性插值,或者叫“lerp”,见下图

linear

Get Adobe Flash player

依靠线性插值可以解决很多从A到B的基本问题,但是如果从B点重新运动回A点,也是通过同样的线性插值,你就会发现有明显的不和谐。幸运的是,这里不仅仅有一种方案能够解决从A到B的问题(实际上有无数种,但我们将只关注一部分)。

4. 更平滑的步骤(smoothstep)

如果你从这个小教程中带不走其他的,那就带走它

#define SMOOTHSTEP(x) ((x) * (x) * (3 - 2 * (x)))

smoothsetp就好像一种神奇的盐,你可以把它洒在任何你想变得更好的地方,你可以很简单的替换大多数的线性插值,如下

for (i = 0; i < N; i++)
{
    t = i / N;
    t = SMOOTHSTEP(t);
    X = (B * t) + (A * (1 - t));
}

smoothstep看起来是这样的

smoothstep

Get Adobe Flash player

通过对比,你可以很明显的看到他刚开始会加速,当快要接触目标的时候会慢慢减速。

5. 高次幂(higher powers)
如果你只想要有缓慢的加速时间,简单的加个N次幂可以解决问题,如下

for (i = 0; i < N; i++)
{
    t = i / N;
    t = t * t;
    X = (B * t) + (A * (1 - t));
}

如果你更想要的是缓慢减速,上面的式子做下反相就行了

for (i = 0; i < N; i++)
{
    t = i / N;
    t = 1 - (1 - t) * (1 - t);
    X = (B * t) + (A * (1 - t));
}

两个式子看起来是这个样子的

squared

Get Adobe Flash player

如果我们把次幂再调高到立方次,这个曲线看起来是这样的

squared

Get Adobe Flash player

同样的道理,这个还可以再次应用smoothstep,应用smoothstep到已经被平滑过的值可以让曲线更进一步(真不知道怎么翻),这个结果不是很容易应用到所有东西上,正如你所见,他会在原地待一段时间,但是有时候又很有用(也不说什么时候有用)。

squared

Get Adobe Flash player

6. 正弦

另外一个方便的曲线就是正弦,正弦可以像幂函数一样应用,结果也是十分相似的。

for (i = 0; i < N; i++)
{
    t = i / N;
    t = sin(t * Pi / 2);
    X = (B * t) + (A * (1 - t));
}

这个曲线同样可以像幂函数一样反相,结果如下

squared

Get Adobe Flash player

如果我们使用了整条三角函数,我们可以可以将曲线做得很近似于smoothstep

squared

Get Adobe Flash player

for (i = 0; i < N; i++)
{
    t = i / N;
    t = 0.5 - cos(-t * Pi) * 0.5;
    X = (B * t) + (A * (1 - t));
}

不过,使用三角函数会比刚才的方法有更大的开销。

7. 加权平均(weighted average)

一个相当方便的算法,特别是当你没办法知道未来的目标行为时(比如摄像机跟随者角色,目标点点一直在改变)。注,这种算法应用很多,你甚至都不需要记录当前时间t,所以特别方便。

t = ((t * (N - 1)) + w) / N;

其实我更喜欢这么写(这段是我自己拼的)

t += ((w - t) / N;

是的,当t越靠近w,则累加量越少。
t代表当前值,w代表目标点,N是缓动因子,N值越大,t接近w就越慢。

squared

Get Adobe Flash player

t越靠近w,则他运动得就越慢,越远离,他就越快,在理想的世界中,t实际上将永远到不了w,只是他们之间的距离越来越小越来越小,再说,计算机是不理想的。

8. 样条

最后,如果你需要更多的控制,你可以使用样条,Catmull-Rom样条是一个非常方便的方法,他总是会经过控制点,所以他可以更容易的应用到插值计算中,而其他的样条函数可以得到更自然的曲线,但是也有更少的可预知性,这里有份实现Catmull-Rom函数的代码。

float catmullrom(float t, float p0, float p1, float p2, float p3)
{
    return 0.5f * (
        (2 * p1) +
        (-p0 + p2) * t +
        (2 * p0 - 5 * p1 + 4 * p2 - p3) * t * t +
        (-p0 + 3 * p1 - 3 * p2 + p3) * t * t * t
    );
}

for (i = 0; i < N; i++)
{
    t = i / N;
    t = catmullrom(t, Q, 0, 1, T);
    X = (B * t) + (A * (1 - t));
}

在正常使用中,你可以给他很多的控制点,比如,5, 6, 比如4, 7,你能做出很多不一样的效果,下面就是一些例子。

squared 

Get Adobe Flash player

上面的参数值是Q和T的值,即p0, p3。
注意:这个值必须经过0和1,但是并不意味着要在0和1之间。

9. 结论

我希望这个简短的技术概览教程可以帮助你从你的移动行为中去掉那些尖锐的角落。

更多的阅读

使用perlin噪音生成随机地图

引言

还是随机地图的问题,除了细胞自动机的生成方式以外,一般3D游戏中的地形大部分是使用某个噪音原图,这个原图大部分是由perlin噪音产生的(perlin noise),perlin噪音的主要作用可参考Perlin噪音

Perlin噪音的实现方式有点复杂,一时间不是很好看懂,我个人理解的是,噪音不太可能是完全随机的,自然界的很多东西虽然看起来是随机的,但是随机中间又蕴藏着很多规则,这些规则导致出现随机实际上是有些规则的,不可能出现类似电视雪花点的噪音。

所以为了用计算机图形来更好的描述自然界的这一随机现象,perlin创造了perlin噪音这么个自然随机算法。perlin噪音包含了平滑差值及八阶分形的内容,有点复杂,不好在这里展开。

实现思路

通过perlin噪音生成随机的灰度(即只有黑白的)噪音图,然后一定比率的颜色变成可通行区域颜色,一定比例的成为障碍物颜色。如0~100为陆地,101~255为障碍物。然后,神奇的一幕发生了。

效果

Get Adobe Flash player

高清无码

Get Adobe Flash player

像不像地球呢?

源码

package {
	import flash.display.BitmapData;
	import flash.display.Bitmap;
	import flash.geom.Rectangle;
	import flash.geom.Point;
	import flash.events.Event;
	import flash.display.Sprite;
	import flash.events.MouseEvent;

	public class PerlinNoiseRandomMap extends Sprite {
		protected var bmTerrain:Bitmap;
		protected var bmpTerrain:BitmapData;
		protected var freq:Number = 0.5;
		protected var octs:Number = 8;
		protected var seed:Number = 12;
		protected var stitch:Boolean = true;
		protected var fractal:Boolean = true;
		protected var channels:Number = 7;
		protected var gray:Boolean = true;
		protected var red:Array = new Array(256);
		protected var green:Array = new Array(256);
		protected var blue:Array = new Array(256);
		protected var land:Number = 0xff00ff00;
		protected var water:Number = 0xff0000ff;

		public function PerlinNoiseRandomMap() {
			init();
			stage.addEventListener(MouseEvent.CLICK, reset);
		}

		public function init():void {
			for (var i:Number = 0; i < 128; i++) {
				red[i]=green[i]=blue[i]=land;
			}
			for (i = 128; i < 256; i++) {
				red[i]=green[i]=blue[i]=water;
			}
			bmpTerrain = new BitmapData(800,600);
            // perlin噪音
			bmpTerrain.perlinNoise(bmpTerrain.width * freq,bmpTerrain.height * freq, octs, seed, stitch, fractal, channels, gray);
            // 以红色通道举例,0-128的红色值重新映射到red[0]到red[128]的数组值
			bmpTerrain.paletteMap(bmpTerrain,new Rectangle(0,0,bmpTerrain.width,bmpTerrain.height),new Point(0,0),red,green,blue);
			bmTerrain = new Bitmap(bmpTerrain);
			bmTerrain.width = stage.stageWidth;
			bmTerrain.height = stage.stageHeight;
			addChild(bmTerrain);
		}

		public function destroy():void {
			removeChild(bmTerrain);
			bmTerrain = null;
			bmpTerrain = null;
		}

		public function reset(e:MouseEvent):void {
			destroy();
			seed = Math.random();
			init();
		}

	}
}

参考文献

自然连通图

引言

接上一文章,当每个随机区块完成后,需要对每个区块进行连接,如果更好的进行连接,随机乱连肯定是不行的,会出现如下情况

图片1

直觉上告诉我们,我们希望得到的是类似下面的图

QQ截图20140122111343

这种连接方式看上去很“自然”,那如何得到这种比较自然的连线方式呢?我们从结果出发可以得到几点规则:

  1. 连线不能交叉
  2. 连线不要经过其他点
  3. 最好不好一个点有多条连线

通过上面的约束,我们可以得到一个算法

  1. 初始时所有点都处在自己的独立集合中
  2. 从第一个集合出发,找到一个离开最近的集合
  3. 与最近的集合做连线,并将那个集合取消,将连线后的点增加到当前集合
  4. 重复第2步,直到所有点都在一个集合

代码

package
{
	import flash.display.Sprite;
	import flash.events.MouseEvent;
	import flash.geom.Point;

	[SWF(frameRate="60", width="800", height="600")]
	public class LineMap extends Sprite
	{
		private var points:Array;
		private var lines:Vector.;
		private var units:Vector.;
		private var step:int = 0;
		private var currentPoint:Point;

		public function LineMap()
		{
			stage.addEventListener(MouseEvent.CLICK, onClick);
		}

		public function initUnit():void {
			units = new Vector.();
			// 初始时每个球一个单元
			for each (var p:Point in points) {
				var u:Unit = new Unit();
				u.points.push(p);
				units.push(u);
			}
		}

		protected function onClick(event:MouseEvent):void
		{
			init();
			initUnit();
			line();
			draw();
		}

		private function line():void
		{
			lines = new Vector.();
			// 遍历所有单元,选择出最近连线,且不相交
			while (units.length > 1) {
				var u:Unit = units[0];

				// 遍历其余单元,找出距离最短的那个单元
				var minDist:Number = Number.MAX_VALUE;
				var minIndex:int = -1, minP1:Point, minP2:Point;
				for (var j:int = 1; j < units.length; ++j) {
					var o:Unit = units[j];
					assert(o.points.length <= 1);
					var dist:Array = u.dist(o);
					if (dist[0] < minDist) {
						minDist = dist[0];
						minIndex = j;
						minP1 = dist[1];
						minP2 = dist[2];
					}
				}

				var l:Line = new Line();
				l.p1 = minP1;
				l.p2 = minP2;
				lines.push(l);

				// 将最短距离的那个单元加入当前单元
				u.points.push(units[minIndex].points[0]);
				units.splice(minIndex, 1);

//				currentPoint = minP1;

//				step++;
//				break;
			}
		}

		public function init():void {
			var count:int = 30;
			var padding:int = 10;
			points = [];
			for (var i:int = 0; i < count; ++i) {
				var p:Point = new Point(rand(padding, stage.stageWidth - padding), rand(padding, stage.stageHeight - padding));
				points.push(p);
			}
		}

		public function rand(x:Number, y:Number):Number {
			return x + Math.random() * (y - x);
		}

		public function draw():void {
			graphics.clear()
			for each (var p:Point in points) {
				graphics.beginFill(0x0);
				if (currentPoint == p) {
					graphics.beginFill(0xFF0000);
				}
				graphics.drawCircle(p.x, p.y, 10);
				graphics.endFill();
			}
			for each (var l:Line in lines) {
				graphics.lineStyle(1, 0x0);
				graphics.moveTo(l.p1.x, l.p1.y);
				graphics.lineTo(l.p2.x, l.p2.y);
			}
		}

		public function assert(b:Boolean):void {
			if (! b) {
				throw new Error("断言错误");
			}
		}
	}
}
import flash.geom.Point;

class Unit {
	public var points:Array = [];

	public function dist(u:Unit):Array {
		var minDist:Number = Number.MAX_VALUE;
		var minP1:Point, minP2:Point;
		for each (var p1:Point in points) {
			for each (var p2:Point in u.points) {
				var dist:Number = p1.subtract(p2).length;
				if (dist < minDist) {
					minDist = dist;
					minP1 = p1;
					minP2 = p2;
				}
			}
		}
		return [minDist, minP1, minP2];
	}
}

class Line {
	public var p1:Point;
	public var p2:Point;
}

效果

Get Adobe Flash player

基于细胞自动机的随机地图生成方案

引入

前天拜读了林伟的一篇GDC的ppt,名字叫《游戏地图自动生成》,这个ppt的前半部分说的是原地图的生成,因为这个地图一般是给3d游戏用的,通过这个灰度图取得具体的高度。这个具体还可以参见《Focus.on.3D.Terrain》。本篇文章关注的是那个灰度图的生成。

最终效果

QQ截图20140122102256

黑色代表障碍物,白色代表可通行区域。

做法

  1. 创建随机噪点,可通行区域与障碍点保持一定比率
  2. 根据细胞自动机算法,通过当前节点的周边8个节点得到新的通行状态,比如5个以上的障碍点,则当前点是障碍点,5个以下障碍点,则当前点是可通行点。

randomMap

“饥荒”游戏动画格式分析

动画流水线(从美术到程序)

  1. 美术通过flash cs设计人物
  2. 人物由多个部位组成(骨骼),每个部位可能有不同的表现形式,比如头部在人物朝上,朝下的时候肯定是不同的显示状态,这个显示状态肯定是无法通过变换矩阵完成的。
  3. 通过jsfl将美术设计的动画转为两种不同的文件,build.xml与anim.xml及散列的部位图片。

build.xml的主要作用是描述人物的整体组成结构,比如

1

 

anim.xml的主要作用是动画构成,比如

2

4. 通过python脚本打包xml为bin(二进制格式),打包build的过程中额外生成纹理集(大位图,mipmap)及定点信息。

这种动画的做法整合了帧帧位图动画以及骨骼动画的优点,首先由于每帧信息大部分更改的是转换矩阵,所有整体动画不会特别大,另外可以通过同一个部位信息做出很多动画,另外由于每个部位状态的存在,也让动画有一定的扩展性,当然对于美术来说,肯定是什么限制都没有最合适了。

 

下面是我写的一个简单的“饥荒”动画读取器

3