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