标签：design

We性质b和网游最大的不同也许就在于数据同步。

Web的工作流程（这里不包括页游）虽然也有很多变化，但是一般都大致分为三步。

1. 在浏览器输入网址， 浏览器通过HTTP协议请求服务器加载数据，服务器在收到HTTP请求之后，从数据库加载相应的数据（有可能是HTML,JS等一些用于浏览器渲染的数据）并返回给客户端。这一步我称之为查询。

2. 浏览器收到服务器返回的数据之后，将数据渲染并呈现给用户。这一步我称之为渲染。

3. 用户在看到浏览器呈现的内容之后，根据需要去执行不同的操作，这些操作为导致浏览器将一些数据发往服务器进行处理，这一步我称为提交。

大部分Web逻辑除了在这三步之间循环之外，还有一个很重要的特点，那就是几乎很少与旁人进行实时交互。比如你在某论坛改了名字，也需要对方手动刷新才能看到。当然也有可以实现显示的，但那是极少功能才有的待遇（并且一般都是通过Hang住HTTP请求来实现的），这里不考虑这种情况。

因此，市面上对Web的高可伸缩性的研究，大都维绕着数据库来做。因为HTTP的数据同步量真的没有什么好研究的，这种模式几乎已经把数据同步量压缩到最低了。只有用户操作才会加载数据，这是多么节省的一种数据同步方式啊。

网游本身就是一个强交互的模式，玩家A做了一个操作，所有应该能看到玩家A的其他玩家都必须能看到玩家A做了什么操作（只是理论上，也许由于某种技能别人看不到）。

这样数据的同步量就会非常大，而且这种数据量，会随着同时在线的玩家的数量成指数性增加。

于是人们研究了各种减少数据同步量的算法，比如AOI、帧同步等。

这里我先私自把游戏分为开房间和大地图两种模式。

开房间模式的游戏,一般同一个房间的人数不会过多。所以最简单的做法就是，直接同步位置和状态。

每个人客户端移动过程中定时（比如10ms)广播坐标给房间内所有玩家，然后客户端根据收到的新坐标，做插值补偿。这又被称作影子跟随算法，即客户端实际表现的位置永远落后于其真正的位置。

如果客户端放了一个技能，就把这个技能效果广播给房间内的所有玩家。

但是这里会存在一个问题，如果这是一个延时类技能，比如几秒后生效，那么服务器在收到释放技能时就需要广播一次，当技能真正生效时，还需要再次广播一次。如果是一个每隔几秒就生效一次的buff就会更麻烦，每次buff生效，都要进行消息广播。数据量会远超于玩家的操作频次。

即然大部分数据量都是状态同步引起的，那么就把所有状态全部交给客户端自己运算，这就是帧同步的本质。客户端拥有整个游戏的全部运算逻辑，将整个游戏进程人为划分为逻辑帧，每个逻辑帧玩家上报自己的操作，由服务器进行房间内广播。客户端收到操作为自己还原各种状态。如果房间内有N个人，每个人操作M次，数据同步量只有M*N条消息，远低于之前的状态同步的数据量。这对于流量并不富裕的手机来说尤其是个好消息。

如何保证所有客户端逻辑和表现都一致，除了要做正确一逻辑帧操作还原外，还有一点很重要，就是复原随机逻辑（战斗中经常会有各种概率判断)。这一点可以通过伪随机序列来保证。

下面来看看大地图模式（这里的大地图模式，是指所有玩家在一张地图上，并且战斗过程中不切换场景）。

在大地图模式，所有玩家都在一张地图上行动，因此玩家数量与房间内的数量根本不是一个数据级（虽然有可能为了增加同时在线人数，会将地图进行分块处理。但即使如此，单块地图上的玩家也远大于房间内玩家数量)。

这也就意味着将数据（操作数据或状态数据）广播给地图上的所有玩家，是不现实的。所以必须要采用AOI算法，来选取需要收到这些数据的玩家。然后将这些数据组播给选取到的玩家。

在使用了AOI算法之后，一般来讲人数的量级与上面开房间模式需要同步的人数量级就差不多了。

那么是否使用了AOI之后，同样可以采用帧同步算法优化掉状态同步呢。

答案显然是否定的，上面也提到，所有的战斗系统一般都会有概率的存在，而一张大地图上必须也只可能有一个伪随机序列（因为玩家之间的视野是交错的）。这也就意味着所有的客户端不可能事先知道这个伪随机序列走到哪一步了（每场战斗都会使伪随机序列前进一步，如果要所有客户端都实时知道当前伪随机序列的进度，就必须在每一场战斗之后，将当前随机数广播给地图内所有玩家，这显然是不是现实的)。

从上面的分析可以得出一个结论，制约大地图模式使用帧同步算法的惟一因素，就是无法复原随机逻辑。那么如果我们游戏地图内没有随机因素（暂且不论是不是有可能），是否可以在AOI的基础上再使用帧同步算法的变种呢。

我们来分析几种情况来看看是否可行，这里需要强调一点，我们假设整个通信采用TCP（TCP具有FIFO性质）传输，服务器采用的是单线程模式。

1. 玩家B先看到了玩家A，然后玩家A被打了掉了5滴血，最终玩家A还有75滴血。

玩家B首先在视野内看到了玩家A，这时会同步到玩家A的血量为80.

然后B收到了玩家A被打的操作（这个操作固定伤5滴血）,玩家B将80减去5得出玩家A还有75滴血的结果。显然这是正确的。

虽然可能buff之类带时间的逻辑不好控制，但是相信经过合理的设计，逻辑上应该不会有太大问题。

2. 玩家B还没收看到玩家A，然后玩家A被打掉了5滴血。

玩家B收到玩家A被打的操作消息后，发现自己视野内还没有加载出玩家A的数据（注意是从服务器加载到的数据，不是客户端还没有把模型之类的数据加载完), 于是将消息抛弃。

之后，玩家B收到的从服务器请求来的数据，A的血量为75。显然这也没有错。

所以在没有伪随机存在的情况下，完全可以使用帧同步算法的理论，进一步优化状态同步。

很巧我们最近开发的游戏，大地图上的表现确实不需要伪随机序列。

这次分析再次告诉我，一定要认清算法的局限在哪里，这样才能根据实际情况灵活组合运用。别人不能用，并不是你就一定不能用。

在场景服务中，如果有一个人A的行为想要被其他人看得到，就必须将A的数据包进行转发给其他人。

最KISS的办法，就是直接把A的数据包直接在场景服务内组播。

但是在一个场景服务中可能有成百上千个人，如果直接在服务进程内进行广播，数据流量会大到一个很夸张的地步，至少以目前的网速来讲是不现实的。

因此，往往场景服务都为人物设计一个视野半径，即只将数据包转发给在我视野内的人，这样可以极大的降低数据的转发流量。

而AOI(Area Of Interest)正这样一个可以帮我们快速确定视野内有多少人的模块。

研究了一下，AOI最普遍的实现方式一般有两种。一种是十字链表法，一种是9宫格来实现的。

两种方式各有优缺点：十字连表在插入时，时间复杂度是O(n), 而9宫格的空间复杂的相对地图来讲空间复杂度是O(n)。

为了尽可能的高效，我最终使用9宫格的方式来实现。

为了简化实现复杂度，在整个AOI空间中的人具有相同的视野（不存在近视眼:D), 这样我们就可以依赖一个事实，A能看到B，B就能看到A。

API设计如下：

struct aoi;
typedef void *(* aoi_alloc_t)(void *ud, size_t sz);
struct aoi *aoi_create(float region[2], aoi_alloc_t alloc, void *ud);
void aoi_free(struct aoi *aoi);
void aoi_leave(struct aoi *aoi, int id);
void aoi_move(struct aoi *aoi, int id, float coord[2]);
int aoi_detect(struct aoi *aoi, struct aoi_event **event);

aoi_create用于创建一个AOI空间，在创建时，你可以传入自定义的内存分配器来帮你实现一些特殊的需求。

aoi_free用于释放一个AOI空间，但是aoi_free并不负责释放struct aoi结构所占用的内存，需要由上层应用根据具体情况去释放struct aoi所占用的内存。

之所以这样设计，是因为考虑到将AOI库嵌入到一门含GC的语言中(比如lua），alloc所创建的内存是不需要显式释放的。

我们可以在手动管理内存语言（比如C）中创建和释放可能是这样的:

void *alloc(void *ud, size_t sz)
{
        (void)ud;
        return malloc(sz);
}
struct aoi *aoi = aoi_create(region, alloc, NULL);
aoi_free(aoi);
free(aoi);

而如果在自动内存管理的语言（比如lua)中可能是这样的:

struct aoi *aoi = aoi_create(region, (aoi_alloc_t)lua_newuserdata, L);
aoi_free(aoi);

因为lua_newuserdata创建的内存是由luaVM自己释放的，并不需要aoi_free来显式释放。

上层应用为每一个人(实体)分配一个惟一ID，在人物移动时调用aoi_move来更改坐标。

在调用aoi_move之后，aoi模块会将产生的事件，压入事件队列。

而aoi_detect函数则用来从事件队列中取出一个事件。返回1就代表返回了一个有效事件，如果返回0就代表没有事件返回。

所以一种典型使用方式是：

struct aoi_event *e;
aoi_move(aoi, id, coord);
while (aoi_detect(aoi, &e)) {
        //do anything you what
}

如果在调用aoi_move之后没有及时调用aoi_detect来取出事件，事件会被缓存直到下一次调用aoi_detect。

为了方便AOI模块嵌入其他语言或做成一个独立的服务存在，就必须要尽可能的减少aoi模块与上层模块的数据交互量。

AOI模块只向上返回‘进入’和‘离开’人物视野事件。

每次调用aoi_move只产生与上次结果相比的差集。即只返回此次移动新‘进入/退出’视野事件。

至于视野内的坐标移动，上层应用可以采用任意的处理方式，可以不需要AOI模块的参与，比如，为每一个人建立一个周围人列表，视野内移动直接转按周围人列表组播即可”。

实现细节很简单：

将整个地图空间打成一个一个小格子，格子的精度需要根据具体情况来做权衡。格子过大，会导致视野内人数过多，组播时流量会增大，格子过小会导致人物频繁发生‘进入/离开’视野，同样增加数据通信流量。

每次移动时，根据当前所在坐标，半径三个元素，找到旧的视野范围A的格子。再根据新的坐标和半径找到新的视野范围B格子。然后求出A和B的差集。

再根据A和B的差集就可以产生，此次移动所产生的新的事件。

自从看了设计模式了解到open-close原则后， 我在写代码时都是尽量遵循着open-close原则来进行编码。

而面向对象中的多态在做到open-close原则中起到不可忽略的作用。

一般在设计之初会先抽象出一个interface(也就是C++中的纯虚类), 这个interface中的函数接口一定是要仔细考量的，因为这关系到所有子类的实现。

然后根据具体情况去继承并实现interface，当我们新增功能时，仅仅重新继承一下interface生成一个新的类即可， 在一般情况下并不需要动到之前运行良好的类。当然不论你interface定义的有多么好， 在最后新增需求时都可能不会完全满足，然而这种情况下一般只需对interface增加函数即可， 对之前运行良好的代码也并不需要做出大的修改。

举个例子：
一个游戏有三个模式ModeA, ModeB, ModeC。我觉得这是一种最天然的抽象了，几乎就不用思考就可以肯定，多态一定是优于if else方式的。

使用多态的方式, 首先抽象出一个interface类似如下：

class IMode {
virtual doSomeThingA() = 0;
virtual doSomeThingB() = 0;
...
};


然后根据ModeA/ModeB/ModeC的实际玩法去实现IMode类开中函数。

这样只需要在游戏切换模式时使用如下类似代码散转一下即可：

IMode *mode;
switch (game_mode) {
case ModeA:
mode = new ModeA();
break;
...
default:
assert(!"unkonwn game mode");
break;
}

在代码主体逻辑中，仅仅使用mode指针即可，即主体逻辑并不关心当前mode是ModeA/ModeB/Modec中的哪个， 他仅仅去调用相关的IMode中的函数即可。

这样当去看主体逻辑代码时，暴露出来几乎全部是主体逻辑，而不会被模式相关的东西弄晕了头脑。

当新加一个ModeD模式时， 仅需要修改上面的Switch语句加一个case另外再实现一个class ModeD类即可， 并不需要修改之前运行良好的主体代码。也就符合了open-close原则。

再看if else的实现，假设如上IMode函数有50个函数DoSomething1~50, 如果使用if else的方式实现，则需要在调用DoSomething1~50的地方全写上类似如上switch的语句，需要搞清楚的是IMode有50个函数并不意味着这50个函数仅仅调用50次（甚至说是150次都不算多), 那么就会出现代码量暴增。

而且这样会导至所有的模式代码是以函数分开的，在增加每一个模式时主体代码都要增加50个函数并修改150处switch-case语句，如果改漏一处就会出现难以预料的bug, 这样大大增加了代码的维护难度。

当然这种还算是好的情况，如果在IMode类中的函数非常短，那么在使用if else方式实现时有些人偷懒就可能会直接用case一段代码语句直接搞定，甚至在后续开发中都可能出现这样的代码：

switch (game_mode) {
case ModeA:
case ModeB:
do_something();
if (game_mode == ModeA)
do_sometingA();
else
do_somethingB();
break;
...
};

如果有4个模式这样纠缠到一块，我打赌你看到这段代码时一定会想知道他家在哪里。

这样修改还有一个坏处就是并不符合open-close原则，因为你在改ModeB时可能会把ModeA改坏，而且有时后会很难测出来。

通过比较很容易就可以看出，多态和open-close的好处，在这里我并不想听到if-else/switch-case比使用多态效率高这种鬼话，我认为损失一点点性能能获得这么清晰的代码结构是非常值得的。

在《Unix编程艺术》P14中说过这样一句话，计算机编程的本质就是控制复杂度，比较两种实现方式可以看出第一种方式，不论增加多了种模式其复杂度几乎都不会增加，而第二种方式每增加一种模式都会使得代码变得更糟糕一些，而且永不停止直到他再也无法被维护。