原文出处

前言

大概已经有差不多一年没写技术文章了，原因是今年投入了一些具体游戏项目的开发。这些新的游戏项目，比较接近独立游戏的开发方式。我觉得公司的“祖传”服务器框架技术不太适合，所以从头写了一个游戏服务器端的框架，以便获得更好的开发效率和灵活性。现在项目将近上线，有时间就想总结一下，这样一个游戏服务器框架的设计和实现过程。

这个框架的基本运行环境是 Linux ，采用 C++ 编写。为了能在各种环境上运行和使用，所以采用了 gcc 4.8 这个“古老”的编译器，以 C99 规范开发。

需求

由于“越通用的代码，就是越没用的代码”，所以在设计之初，我就认为应该使用分层的模式来构建整个系统。按照游戏服务器的一般需求划分，最基本的可以分为两层：

1. 底层基础功能：包括通信、持久化等非常通用的部分，关注的是性能、易用性、扩展性等指标。

2. 高层逻辑功能：包括具体的游戏逻辑，针对不同的游戏会有不同的设计。

我希望能有一个基本完整的“底层基础功能”的框架，可以被复用于多个不同的游戏。由于目标是开发一个 适合独立游戏开发 的游戏服务器框架。所以最基本的需求分析为：

功能性需求

1. 并发：所有的服务器程序，都会碰到这个基本的问题：如何处理并发任务。一般来说，会有多线程、异步两种技术。多线程编程在编码上比较符合人类的思维习惯，但带来了“锁”这个问题。而异步非阻塞的模型，其程序执行的情况是比较简单的，而且也能比较充分的利用硬件性能，但是问题是很多代码需要以“回调”的形式编写，对于复杂的业务逻辑来说，显得非常繁琐，可读性非常差。虽然这两种方案各有利弊，也有人结合这两种技术希望能各取所长，但是我更倾向于基础是使用异步、单线程、非阻塞的调度方式，因为这个方案是最清晰简单的。为了解决“回调”的问题，我们可以在其上再添加其他的抽象层，比如协程或者添加线程池之类的技术予以改善。

2. 通信：支持 请求响应 模式以及 通知 模式的通信（广播视为一种多目标的通知）。游戏有很多登录、买卖、打开背包之类的功能，都是明确的有请求和响应的。而大量的联机游戏中，多个客户端的位置、HP 等东西都需要经过网络同步，其实就是一种“主动通知”的通信方式。

3. 持久化：可以存取 对象 。游戏存档的格式非常复杂，但其索引的需求往往都是根据玩家 ID 来读写就可以。在很多游戏主机如 PlayStation 上，以前的存档都是可以以类似“文件”的方式存放在记忆卡里的。所以游戏持久化最基本的需求，就是一个 key-value 存取模型。当然，游戏中还会有更复杂的持久化需求，比如排行榜、拍卖行等，这些需求应该额外对待，不适合包含在一个最基本的通用底层中。

4. 缓存：支持远程、分布式的对象缓存。游戏服务基本上都是“带状态”的服务，因为游戏要求响应延迟非常苛刻，基本上都需要利用服务器进程的内存来存放过程数据。但是游戏的数据，往往是变化越快的，价值越低，比如经验值、金币、HP，而等级、装备等变化比较慢的，价值则越高，这种特征，非常适合用一个缓存模型来处理。

5. 协程：可以用 C++ 来编写协程代码，避免大量回调函数分割代码。这个是对于异步代码非常有用的特性，能大大提高代码的可读性和开发效率。特别是把很多底层涉及IO的功能，都提供了协程化 API，使用起来就会像同步的 API 一样轻松惬意。

6. 脚本：初步设想是支持可以用 Lua 来编写业务逻辑。游戏需求变化是出了名快的，用脚本语言编写业务逻辑正好能提供这方面的支持。实际上脚本在游戏行业里的使用非常广泛。所以支持脚本，也是一个游戏服务器框架很重要的能力。

7. 其他功能：包括定时器、服务器端的对象管理等等。这些功能很常用，所以也需要包含在框架中，但已经有很多成熟方案，所以只要选取常见易懂的模型即可。比如对象管理，我会采用类似 Unity 的组件模型来实现。

非功能性需求

1. 灵活性：支持可替换的通信协议；可替换的持久化设备（如数据库）；可替换的缓存设备（如 memcached/redis）；以静态库和头文件的方式发布，不对使用者代码做过多的要求。游戏的运营环境比较复杂，特别是在不同的项目之间，可能会使用不同的数据库、不同的通信协议。但是游戏本身业务逻辑很多都是基于对象模型去设计的，所以应该有一层能够基于“对象”来抽象所有这些底层功能的模型。这样才能让多个不同的游戏，都基于一套底层进行开发。

2. 部署便利性：支持灵活的配置文件、命令行参数、环境变量的引用；支持单独进程启动，而无须依赖数据库、消息队列中间件等设施。一般游戏都会有至少三套运行环境，包括一个开发环境、一个内测环境、一个外测或运营环境。一个游戏的版本更新，往往需要更新多个环境。所以如何能尽量简化部署就成为一个很重要的问题。我认为一个好的服务器端框架，应该能让这个服务器端程序，在无配置、无依赖的情况下独立启动，以符合在开发、测试、演示环境下快速部署。并且能很简单的通过配置文件、或者命令行参数的不同，在集群化下的外部测试或者运营环境下启动。

3. 性能：很多游戏服务器，都会使用异步非阻塞的方式来编程。因为异步非阻塞可以很好的提高服务器的吞吐量，而且可以很明确的控制多个用户任务并发下的代码执行顺序，从而避免多线程锁之类的复杂问题。所以这个框架我也希望是以异步非阻塞作为基本的并发模型。这样做还有另外一个好处，就是可以手工的控制具体的进程，充分利用多核 CPU 服务器的性能。当然异步代码可读性因为大量的回调函数，会变得很难阅读，幸好我们还可以用“协程”来改善这个问题。

4. 扩展性：支持服务器之间的通信，进程状态管理，类似 SOA 的集群管理。自动容灾和自动扩容，其实关键点是服务进程的状态同步和管理。我希望一个通用的底层，可以把所有的服务器间调用，都通过一个统一的集权管理模型管理起来，这样就可以不再每个项目去关心集群间通信、寻址等问题。

原文

原文出处

方法一：

没有把参数t从系数中分离开来，直接混在一起计算系数a，b，c，d。这样看算法比较直观，但是不是最优化的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

float Evaluate(float t, Keyframe keyframe0, Keyframe keyframe1)
{
    float dt = keyframe1.time - keyframe0.time;

    float m0 = keyframe0.outTangent * dt;
    float m1 = keyframe1.inTangent * dt;

    float t2 = t * t;
    float t3 = t2 * t;

    float a = 2 * t3 - 3 * t2 + 1;
    float b = t3 - 2 * t2 + t;
    float c = t3 - t2;
    float d = -2 * t3 + 3 * t2;

    return a * keyframe0.value + b * m0 + c * m1 + d * keyframe1.value;
}

主要内容：该视频由Paragon游戏制作者Laurent Delayen(Senior Programmer, Gameplay)和RayArnett(Senior Artist, Animation)讲述制作过程中使用到的动画技术。

包括：Transitions（动画过渡），Synchronize marker（同步标记），Turn（转向动作），Speed Warping（使用IK根据速度调整步幅），Slope Warping（使用IK根据斜坡斜率调整脚步位置），Jump动作的制作，以及AnimGraph。

声明：以下英文部分为个人听力记录，视频无字幕，不保证准确性，其中带问号的为听不清的单词。中文翻译部分更不保证准确性，建议结合视频看英文部分。

24’50’’ Transitions.Our idea is to do motion prediction. Predict where the character is going to stop. Gives a few frame to do the anticipation for the stop. When we do the starts, we drop the marker and look backwards. Drop the marker location in the world, and we are using them to synchronizing our animations. We translate the physical movement to a curve, a distance curve.

In the case of start transition, look backing time and where the marker was, that curve describes the distance of the actor to that marker.

我们的想法是做动作预测。预测角色将要停止的位置。用一些动作帧来做停止动作。当做起步动作时，在起点放标记然后往回看。在世界中放下标记位置，用他们来同步我们的动作。我们把物理移动转换成一个距离曲线。

在起步的过渡时，往回看标记所在的位置，曲线描述actor到标记的距离。

26’46’’ 使用DistanceCurve保存Actor to Marker的位置。

28’21’’ Backward动作的Transition.

28’50’’ Pivoting。两个动作的结合。Reach the pivot and leave that pivot.

29’39’’ when we call the actor in the studio, remap the recorded motion to the map. Using the distance, we get really precise foot placement, no foot sliding at all.

30’15’’ For people who are familiar with root motion, like the animation tells the capsule whereto go. If I cross the room in the animation, the capsule will follow the animation along. With this kind of foot slide ahead(?) basically the capsule is gonna cross the room, and looks that curve it say, it walks? across the room,am I in this animation, and plays that for aim. so uses the motion of the capsule to pick which frame to play in the animation. the animation stay is locked. to the capsule is doing movement. If the capsule is sitting still and starts moving forwards , the animation says OK, 2 units from where I started,I’ll find that on this curve and play that for aim.

对熟悉RootMotion的人来说，动画告诉胶囊该移动到哪里。如果人物在动画中穿过房间，胶囊会跟随动画。所以用胶囊的运动来选取哪一帧来在动画中播放。在胶囊运动的过程中，动画所在位置是锁定的。如果胶囊还在原地准备向前移动，动画说距离出发的位置有2个单位距离，会在曲线上找到那帧来播放。

33’ synchronize marker? 从start到loop动作。当toe和root交叉时，有标记。

33’47’’ The reason for doing that way is, they sort of tells us, spash? you where the foot is and we can synchronize animation that way. We thought about this, other people seem to describe the movement when the foot touch the ground and leave the ground,sort of like the anpitute? of the step. and we decided to go instead with the spash? where it was around the player to minimize foot sliding. So when you transition between animations, we sort of try to get the closest position. to where the capsule is basically to minimize sliding. So we sacrifice bits the where the foot is, we try to keep the position.

35’10’’ 以脚的动作为标准，可以保证不会滑步。

37’50’’ 转向。

38’50’’ 角度Curve。

41’02’’ 动画蓝图。

42’40’’Backward-Forward转换。DistanceCurve标记Turn角度。

43’40’’ .速度低会导致动作慢，用Speed Warping可以小步移动。

45’55’’ 显示Speed Warping和无Speed Warping的区别。

51’ 原理：根据SpeedScale移动IKBone。

53’24’’ 比如2X速率移动，IKBone在2X距离位置

54’50’’ 后退动作的有无SpeedWarping比较

58’ BlendSpace。JogForwardSlopeLean。slope斜率。左右倾斜角度。速度

60’ Jogging状态机节点。Blend->AimOffset->RotateRoot

60’50’’ 移动效果。

62’40’’ Slope移动效果。

64’43’’ SlopeWarping开关的区别。

66’41’’ 斜坡上开启网格模式的效果。能看到地板位置，Normal，IKBone的位置

68’14’’ TwoBoneIK for legs蓝图节点

68’47’’ 改变角度观察BlendSpace

70’50’’ 脚悬空不可避免。

73’30’’ Jump动作。Jumping分解为3个部分。InAir，Apex，Landing。用DistanceCurve标记到地面的距离。We use it here to get a few extra frames of compression. Because animation runs after physics. So when we note that you are jumping, it’s already too late you are already in jumping. So this allows it to compensate and have a few extra frames that feet on the ground.

Because the capsule is moving.

74’53’’ Jump动作演示。

75’43’’DistanceCurveForLanding. Put a marker on where you are gonna lands. Use that to synchronize the feet getting close to the ground. The arc is synchronizing with the apex?

76’06’’ Apex。DistanceCurve. How far before it and go past it.

76’30’’ Recovery Additive.Play on top of anything in the game. 为了nice landing compression.如果不用additive。会Blending Jogforward, backward。Maybe the result is not what would be blended exactly, you still get a nice feel without making a time to time content.

77’38’’ when we do blend between animations, it have difference. Blend feet quickly, Upperbody lowly.

78’50’’ AnimDynamics. Not show. 可以在另一个视频中看到专门讲这个节点。AnimDynamic features used in Paragon.https://www.youtube.com/watch?v=5h5CvZEBBWo

79’36’’ AnimGraph.

总结：

一、曲线的使用。

根据曲线同步动作。如起步过渡动作中，进入过渡状态时在起点放置标记marker，actor移动时根据当前actor和marker的距离distance，在DistanceCurve上查找该Distance应该对应的帧进行播放。

如原地转身动作（Rotate）中，根据当前actor的旋转角度angle，在Curve上查找该Angle对应的帧进行播放。

二、Synchronize Marker 左右脚同步标记

在动画中，当toe和root重合时，添加Notify记录当前是左脚还是右脚。动画过渡时，以脚为基础，避免了滑步的出现。

三、IK的使用

SpeedWarping和SlopeWarping，使用IK使脚在动画中处于正确的位置。

四、Jump动作

由于胶囊运动，动画制作原地起跳时需要考虑胶囊的移动。Curve标记当前和地面的距离。通过Curve同步动画。

在浏览器中玩

• 移动蓝球 ：受 Player1 控制, 用左右箭头键
• 移动红球 ：受 Player2 控制, 用A和D键

原文出处

Fast-Paced Multiplayer (Part IV): Lag Compensation

Introduction

The previous three articles explained a client-server game architecture which can be summarized as follows:

• Server gets inputs from all the clients, with timestamps

• Server processes inputs and updates world status

• Server sends regular world snapshots to all clients

• Client sends input and simulates their effects locally

• Client get world updates and
  • Syncs predicted state to authoritative state
  • Interpolates known past states for other entities

From a player’s point of view, this has two important consequences:

• Player sees himself in the present

• Player sees other entities in the past

This situation is generally fine, but it’s quite problematic for very time- and space-sensitive events; for example, shooting your enemy in the head!

原文出处

Fast-Paced Multiplayer (Part III): Entity Interpolation

Introduction

In the first article of the series, we introduced the concept of an authoritative server and its usefulness to prevent client cheats. However, using this technique naively can lead to potentially showstopper issues regarding playability and responsiveness. In the second article, we proposed client-side prediction as a way to overcome these limitations.

The net result of these two articles is a set of concepts and techniques that allow a player to control an in-game character in a way that feels exactly like a single-player game, even when connected to an authoritative server through an internet connection with transmission delays.

In this article, we’ll explore the consequences of having other player-controled characters connected to the same server.

Server time step

In the previous article, the behavior of the server we described was pretty simple – it read client inputs, updated the game state, and sent it back to the client. When more than one client is connected, though, the main server loop is somewhat different.

In this scenario, several clients may be sending inputs simultaneously, and at a fast pace (as fast as the player can issue commands, be it pressing arrow keys, moving the mouse or clicking the screen). Updating the game world every time inputs are received from each client and then broadcasting the game state would consume too much CPU and bandwidth.

A better approach is to queue the client inputs as they are received, without any processing. Instead, the game world is updated periodically at low frequency, for example 10 times per second. The delay between every update, 100ms in this case, is called the time step. In every update loop iteration, all the unprocessed client input is applied (possibly in smaller time increments than the time step, to make physics more predictable), and the new game state is broadcast to the clients.

In summary, the game world updates independent of the presence and amount of client input, at a predictable rate.

原文出处

Fast-Paced Multiplayer (Part II): Client-Side Prediction and Server Reconciliation

Introduction

In the first article of this series, we explored a client-server model with an authoritative server and dumb clients that just send inputs to the server and then render the updated game state when the server sends it.

A naive implementation of this scheme leads to a delay between user commands and changes on the screen; for example, the player presses the right arrow key, and the character takes half a second before it starts moving. This is because the client input must first travel to the server, the server must process the input and calculate a new game state, and the updated game state must reach the client again.

Effect of network delays.

In a networked environment such as the internet, where delays can be in the orders of tenths of a second, a game may feel unresponsive at best, or in the worst case, be rendered unplayable. In this article, we’ll find ways to minimize or even eliminate that problem.

原文出处

Fast-Paced Multiplayer (Part I): Client-Server Game Architecture

Introduction

This is the first in a series of articles exploring the techniques and algorithms that make fast-paced multiplayer games possible. If you’re familiar with the concepts behind multiplayer games, you can safely skip to the next article – what follows is an introductory discussion.

Developing any kind of game is itself challenging; multiplayer games, however, add a completely new set of problems to be dealt with. Interestingly enough, the core problems are human nature and physics!

The problem of cheating

It all starts with cheating.

As a game developer, you usually don’t care whether a player cheats in your single-player game – his actions don’t affect anyone but him. A cheating player may not experience the game exactly as you planned, but since it’s their game, they have the right to play it in any way they please.

Multiplayer games are different, though. In any competitive game, a cheating player isn’t just making the experience better for himself, he’s also making the experience worse for the other players. As the developer, you probably want to avoid that, since it tends to drive players away from your game.

There are many things that can be done to prevent cheating, but the most important one (and probably the only really meaningful one) is simple : don’t trust the player. Always assume the worst – that players will try to cheat.

1. NAT类型
   1. 锥NAT
   2. 对称NAT
2. NAT作用
3. 穿透锥NAT
   1. 网络拓扑结构
   2. 使用UDP穿透NAT
   3. 使用TCP穿透NAT
4. 穿透对称NAT
   1. 同时开放TCP（ Simultaneous TCP open ）策略
   2. UDP端口猜测策略
5. 问题总结
6. 参考

NAT类型

注 : 我们本文主要讨论穿越锥NAT

锥NAT

• 全锥NAT ：全锥NAT 把所有来自相同内部IP 地址和端口的请求映射到相同的外部IP 地址和端口。任何一个外部主机均可通过该映射发送数据包到该内部主机。
• 限制性锥NAT ：限制性锥NAT 把所有来自相同内部IP 地址和端口的请求映射到相同的外部IP 地址和端口。但是, 和全锥NAT 不同的是：只有当内部主机先给外部主机发送数据包, 该外部主机才能向该内部主机发送数据包。
• 端口限制性锥NAT ：端口限制性锥NAT 与限制性锥NAT 类似, 只是多了端口号的限制, 即只有内部主机先向外部地址：端口号对发送数据包, 该外部主机才能使用特定的端口号向内部主机发送数据包。

对称NAT

对称NAT 与上述3 种类型都不同, 不管是全锥NAT ，限制性锥NAT 还是端口限制性锥NAT ，它们都属于锥NAT （Cone NAT ）。当同一内部主机使用相同的端口与不同地址的外部主机进行通信时, 对称NAT 会重新建立一个Session ，为这个Session 分配不同的端口号，或许还会改变IP 地址。

本篇自我总结

这篇文章网上找不到翻译, 我也没时间详细翻译, 大概总结一下吧.
本篇主要讲了把本系列之前五篇文章的技术应用到实战中处理客户端与服务器的的连接.
请看总结, 不明之处再看文中具体讲解.

简单的连接协议

First up we have the client state machine.
The client is in one of three states:

• Disconnected
• Connecting
• Connected

The goal is to create an abstraction on top of a UDP socket where our server presents a number of virtual slots for clients to connect to.

When a client requests a connection, it gets assigned to one of these slots.

If a client requests connection, but no slots are available, the server is full and the connection request is denied.

On the server, we have the following data structure:

1
2
3
4
5
6
7
8
9

const int MaxClients = 64;

class Server
{
    int m_maxClients;
    int m_numConnectedClients;
    bool m_clientConnected[MaxClients];
    Address m_clientAddress[MaxClients];
};

这个简单协议存在的问题

• 易被攻击者利用我们的服务器当做DDos放大攻击的工具
• 攻击者可以很轻松的占满我们的client slots
• Traffic between the client and server can be read and modified in transit by a third party.
• 一旦被攻击者知道了客户端或者服务器的地址, 他就可以伪装服务器或客户端来欺骗对方获取利益
• 没有一个明确的断开连接的方式, 只能等time out

这些问题需要用授权系统和加密系统来解决.

如何改进这个连接协议

• we no longer accept client connections immediately on connection request, instead we send back a challenge packet, and only complete connection when a client replies with information that can only be obtained by receiving the challenge packet.

• 为了防止攻击者利用我们的服务器当做DDos放大攻击的工具, 我们让客户端发的包比服务器发的包要大些.

• We’ll add some unique random identifiers, or ‘salts’, to make each client connection unique from previous ones coming from the same IP address and port.

• 一旦彼此连接上之后, 就用 client salt 和 server salt 的异或值来标识彼此.

• 以上的防御措施让我们的服务器做到了 no longer able to be used as port of DDoS amplification attacks, and with a trivial xor based authentication, 但对于一个经验丰富的会抓包分析的攻击者来说, 还存在以下问题 :

  • This attacker can read and modify packets in flight.
  • This breaks the trivial identification based around salt values…
  • giving an attacker the power to disconnect any client at will.

To solve this, we need to get serious with cryptography to encrypt and sign packets so they can’t be read or modified by a third party.