《网游服务器端寻路》PPT课件

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,网游服,务器端寻路,面向多核、分布式,2008-12,金山,软件,陈杰,NPC,寻路问题,很重要（,虽然也可以不要）,游,戏玩法与,NPC,的,寻路能力直接相关,计算量很大,数据,结构和算法的相对复杂,一台服,务器上数万个,NPC,一起,寻路有挑战,寻路与其它模块的关系,寻路在游戏中是一个相对底层的模块,NPC,的,AI,系,统依赖于一个可靠的寻路算法,寻路模块依赖于游戏对地图的描述,寻路模块基本上是一种服务模块，总是被调用，但是自己不需要主动去做什么事情,寻路的一种实现,在游,戏逻辑服务器内实现一个,A star,算法，在,逻辑地图描述数据上,(CELL),搜索。,效率很低,可能会阻塞主循,环,增加服,务器复杂度,目,标,Need for Speed,！将性能提升,100,倍！,在,单位时间内出更多的结果,不能影响游,戏逻辑的主循环,更好的利用多核，甚至多台,计算机的运算能力,如何在,逻辑很复杂，数据结构很复杂，为了提高效率而指针满天飞的情况下，让服务器跑稳定？,如何更方便的在游,戏运营过程中逐步改进巡逻模块？,改,进地图描述数据,Cell,结构适合描述逻辑数据,:Trap,Obstacle,但是,Cell,的数量太大，直接用来,A Star,效率很低,在,NPC,大多数,时候不需要跳跃、游泳、空中飞行的时候，可以是用,NavMesh,来描述,寻路所需要的地图障碍信息,NavMesh,使用凸多,边形来描述可以移动的区域，数量通常只有,CELL,的几十分之一到数百分之一,将,寻路模块独立为进程,为什么要独立出去？,不必担心阻塞游,戏服务器的主循环。,不,论是主服务器还是寻路模块，都变得更简单一些。,为什么是进程而不是线程？,寻路模块使用自己的地图描述数据，和其他逻辑模块没有太多需要共享的资源。,更健壮。,寻路模块本身没有状态，也没有不能丢失的动态数据。即使寻路模块挂了，也不会影响游戏的主服务器。直接重启就可以了。,寻路服务器,减少重复,计算,AI,的行,为会经常周期性的调用寻路。,附近有很多,NPC,，他,们的坐标很接近，寻路的计算是很相似，或者完全相同的。,如果将,寻路的计算结果缓存起来，就可以减少重复运算。,游,戏服务器组,每个,逻辑服务器独享寻路服务器,一份地,图的,NavMesh,数据需要加,载到多个寻路服务进程中，浪费宝贵的内存。,每个,寻路进程单独,Cache,寻路结果，使得寻路,Cache,中的数据重复，命中次数下降。,对于硬件需求过高。一般不可能做到每台寻路服务器都在独立的物理服务器上。,共享,寻路服务器的游戏服务器组,一台物理服,务器上共享数据,在不考,虑地形,(,障碍,),动态变化的情况下，,NavMesh,的数据是静,态的。所有寻路进程可以同时读取共享数据。,但是,Cache,是,动态刷新的。必须考虑进程间的同步问题。,考,虑加锁,对,Cache,进行加锁,寻路算法每搜索一块区域时都要获取锁，然后判断,Cache,里是否有可以利用的数据。,当,寻路出新的路径时也要获取锁，并将计算结果写入,Cache,中。,寻路过程中总是在获取锁，等于单进程跑。,读写锁,寻路过程中可以明确区分读写两个阶段,寻路过程中，获取读锁来获取,Cache,数据。,寻路结束后，获取写锁来更新,Cache,数据。,多个,进程可以同时读,Cache,，但是如果有,进程要写,Cache,的,话，所有进程都要等。,利用本地,Cache,提高并,发能力,为每个进程增加一个本地的私有,Cache,。,寻路进程算出结果后只将寻路结果更新到本地的,Cache,。而不是立刻去写共享的,Cache,。,等一段,时间之后，进程再一次性讲本地,Cache,的内容提交到共享,Cache,。,降低了,进程获取共享,Cache,写,锁的频率，从而提高并发能力。,带本地,Cache,的,寻路进程,锁的问题,锁的目的就是让程序变得不并行。,锁本身的代价很高，特别是进程之间的锁，往往需要使用操作系统内核对象来实现，获取和释放的开销通常在,1000 CPU Tick,左右。,锁很不安全，只有有一初代码没有按规矩来获取或者释放锁，整个系统都会出问题。,利用,调度算法避免锁,引入一个,调度进程。,所有,寻路进程的任务由调度进程分配。,所有,寻路进程完成寻路任务的时候向调度进程汇报。,调度进程没有分配任务的时候，寻路进程不能访问共享,Cache,（,读,/,写都不行）。,调度进程可以在没有进程访问共享,Cache,的,时候向一个进程分配更新共享,Cache,的任,务。,调度进程,通,过调度来实现互斥,调度进程会周期性的控制寻路进程向共享,Cache,中更新数据。,再此之前，,调度程序会保证所有的寻路进程都是等待状态。,再此期,间，调度程序不会向任何寻路进程发出新的寻路任务。,调度对寻路效率的影响,调度本身做的事情很简单，开销相对于寻路算法而言可以忽略不计。,由于每个,寻路进程有本地,Cache,，所以,调度算法应该将同一个地图并且坐标相近的寻路任务尽量分配给同一个寻路进程。,调度控制寻路进程将本地,Cache,提交到共享,Cache,的,频率会影响整个系统的效率。,频率太低的话，共享,Cache,中有效数据就少。,频率太高的话，不管用不用锁写操作是互斥的。,需要避免的,问题,如果,调度器分配一个任务给寻路进程，但是寻路进程出错，而一直没有给调度进程发任务完成的消息。那么实际上，调度器内部的状态会“卡”住，而导致调度器不能发出更新共享,Cache,的指令。,这个其实就和一个进程获取了锁，而一直没有释放这个锁，是一样的道理。,网,络游戏服务器架构发展趋势,相似的硬件架构,服,务器不停机升级,允,许一个模块可以有多份实例（进程）。,多个,实例要求接口（协议）兼容，不需要二进制匹配。,调度器可识别不同模块和版本。一旦发现新版本就停止向旧模块分配任务。,当旧模,块执行完当前的任务时可以卸载。,服,务器崩溃恢复,引入,备份模块（进程）,调度器默认不给备份模块分配任务。,当普通模,块崩溃时，调度器自动启用备份模块,重启普通模,块，调度器自动停用备用模块。,模,块的自动化测试,THANK YOU,！,Q&A,