MMORPG负载均衡机制以及动态负载机制实现方式

    平均分配玩家给每个Server，使每个Server有相同数量的玩家。这种方法的优点是算法简单，但玩家在地图上移动，因此过一段时间，最差的情况下，Server之间可能有大量的网络流量，因为当玩家在完成一个动作后，所有的Server必须获得另一个Server的玩家数据，而其附近的玩家皆在不同的Server上，如此依赖，每个玩家的一个动作需要传送消息到不同的Server上，将造成communication的极大负担。

    利用空间切割的方式将虚拟世界切割成和Server同等数量的地图片段，再将这些地图片段分配给每一个Server负责，然后再有一个Dispacher Server负责将每一个玩家分配到所对应的Server上去，但由于玩家会在地图上移动，因此时间一久，在最差情况下，玩家可能都到同一个Server的地图片段上，这样当初的负载平衡就完全被破坏了。

    静态分配地图片段至每个Server虽然可霞跎賁erver间网络的频宽和负载，但必须使玩家在正确的分布地图上，玩家的位置是由玩家所操作的，因此会发生不可预料的问题，为了克服这类问题，将地图分切成更小的片段，然后动态的分配地图片段至Server上是需要的。然而这种方法要有效率，其关键在于如何切割地图片段，要切虾沃旨负涡巫吹模该切成多少片段？传统的方法大都是切成正方形方块，切割数根据实际情况或模拟后作适当的处理。

    在上一片段中我们讨论了目前MMORPG所采用的负载平衡机制的架构，这里我们将提出我们的负载平衡方法，并且讨论如何动态以动态负载机制来调整线上游戏Server负载不平衡的现象。

多人在线游戏中Server端必须完成一下三个工作：

A.接受Client端玩家的状态、移动及交谈的讯息

B.处理玩家和NPC（Server控制的角色，如怪物，任务角色等）间的互动。

C.更新虚拟世界状态

D.将虚拟世界更新后的信息传送回Client端

    以上工作当玩家越来越多的时候将话费更多的时间处理，因此Server上玩家暴增时，可能无法将信息及时的传送给每一个玩家，在这里我们把这四个工作所需要的时间定义成一个Server的负载；很明显的，在一个Multi-Server的MMORPG系统中，每一个Server的负载和它所负责的玩家个数成正比，因此，我们将每一个Server所负责的玩家的个数当成其负载的重要指标。

    在虚拟世界中，在非常多玩家的情况下，单i的Server必定会导致负载过重的现象，因此Multi-Server的架构无疑是必须采用的解决方式，但是前面我们已经讨论了Multi-Server负载平衡机制的优缺点，其中较为有效的是动态的分配地图至服务器，下面我们讨论如何实现这种机制。

    首先我们必须解决如何切割游戏地图的问题，以及切成多少等分，因为这些将影响到在此机制下实现整个系统的效率。

我们考虑的原则有一下几点：

1.尽量分散玩家到各个Server上。

2.尽量较少玩家间的跨Server的信息传送。

3.尽量避免玩家因为在地图蔚奈恢靡贫而必须更换Server。

    其中第一点是为了平均分摊Server的负载，第二点是为了减少Client间通讯的时间成本，第三点是为了减少Server间玩家资料的转移次数。

    首先我们必须将地图切成跟Server个数相等的分数，使得每个Server至少有一份地图，然而因为玩家会在地图上移动，因此若每个Server负责一份地图，那么时间一久，必会导致负载开始不平衡。另一种方式是将地图切成若干个小等分，然后透过合理的方式将每个小等分分散到各个Server上。当然，和上述情况一样，时间r久仍会产生负载不平衡，然而这时候我们可以将负载太重的Server上的一部分地图片段再转移给其他负载较轻的Server上去，以达到负载平衡的目的。转移的时机是以Server的负载是否超过某一临界值，而转移的对象是可采用random polling的方式，也就是询问相邻的Server负载情况如何r是否可以接受额外的负载。

    其次目前Multi-Server MMORPG大多采用将地图切割成正方形，然而应为正方形区域共有东、西、南、北、东南、东北、西北、西南等八个相邻的区域，如此会正佳玩家因为移动而转换区域的机会，因此另有系统采用正六角形切割，然而这种切割虽然相邻的区域减少到六个，但是其切割方式较为复杂，并且判断玩家位于哪个区域也较为耗时。另一可行方式是采用正三角形的切割，此方式的优点是切割方法和判断位置区域的演算法均较正六角形简单。

    但是以上切割方式都有一共同的缺点，就是他们都为考虑到游戏地图的内容，也就是说不论地图的任何角落皆采用同样的切割方式，因此会很容易造成某个区域内没有任何的NPC，而另外一个区域内却包含数个NPC，而拥有NPC的区域通常是玩家驻足停留的地方，因此包含数个NPC的区域意味这其高负载的可能性较高，未包含任何NPC的区域意味着玩家不会长时间停留，大多属于路过性质，因此玩家转换Server的可能性便会较高。

    为了解决上述切割的缺点，我们试图使用与地图内容相关的切割方式，我们以每个NPC为心来切割地图区域，是的每个区域仅含有一个NPC，并且为避免玩家因暂时移动而跨出区域，我们希望每个区域中的NPC和其他的NPC要有适当的距离。

    这里提供参考的分割方式如下:首先定出所有NPC的所在位置，然后对于每一个NPC和其各个NPC间各画出一条垂直平分线，最后整理这些分割线而成的一个包围一个NPC的区域。该区域所形成的多边形中的一个边，即是该NPC和他的临近NPC间的等距离分割线。事实上，这些多边形区域的所有形成的图形是计算几何中的所有的Voronoi diagram，而各个区域称为Voronoi polygon鳹oronoi diagram的正式定义如下：

    我们给定一个N个点的集合S ，对所有属于S中的任意连个点Pi和Pj，PiPj线段的中央垂直分割线将平面分割成连个半平面，包含Pi的半平面我们以H（Pi,Pj）表示之，则所有在平面上靠经Pi的所有点所形成的区域V(i) = ∩i≠jH(pi,pj)，我们称V(i)为关于Pi的Voronoi 

    利用Voronoi diagram来分割游戏地图可以使得定义一个NPC区域的边界与其相邻的NPC间为相等距离，因而令玩家与该NPC互动时不会不经意的离开边界而到了另一个地图区域中，因此答复的降低了玩家在Server间转换的可能次数。

    Voronoi diagram的建立并不如想象中的那么复杂费时，利用以上提供的演算法可以建立出Voronoi diagram，利用该演算法我们可以在给定N个借点的图形中以O（NlogN）的时间复杂度求的包含该节点的Voronoi diagram。在下一段中我们将模拟我们的负载分配方法，并且规划如何与其他传统的方法作效能的分析比较，最后将其实现在open source的Arriane server game server上。