地图管理

概述

1. 哪些模块会用到地图模块
   1. 移动（movements）
   2. 副本
   3. 寻路
   4. 。。。
2. 地图模块要实现哪些功能
   1. AOI
      1. 管理地图地理信息
      2. 管理地图对象信息
   2. 功能
      1. 视野
      2. 数据同步
      3. 碰撞检测
      4. 寻路算法
3. 如何驱动地图数据？
   1. 网络数据（玩家的活动）
   2. 定时的更新（地图中怪物活动等）

如何驱动地图数据

网络数据

• 数据流程图
  
• 红色，adapter到network thread
• 黄色，network thread到msg queue（解出具体的消息packet）
• 蓝色，main线程和mapUpdater线程交换map数据包
• 绿色，对外发送数据

1. adapter接受连接，然后分配到负载均衡的network thread中
2. network thread解包放入到msg queue中
3. main线程不断轮询取出数据包，处理一部分网络数据（这里存在一个filter筛选需要直接在主线程处理的数据包，player在map中的就不处理，不在map中的，例如登录、查询数据等就直接处理），另一部分放入到map queue中。
4. map线程不断从map queue中取数据进行处理。

定时更新

1. dynamicTree.Update
   • 一个组织对象（包围盒）的树状结构，方便我们快速检测对象碰撞
2. 处理网络数据包
3. 处理重生相关
4. 处理玩家更新
5. 处理视野

整体更新流程（***流程复述）

0. main.cpp中使用threadpool中的thread创建多个共享io_context的工作线程，用来接收连接（然后进行负载均衡）
1. sWorld->SetInitialWorldSettings()（主线程从配置中初始化map updater线程池(这里是另一个线程池)中的线程数量）
2. sWorld->Update(在WorldUpdateLoop函数中，main.cpp中这里是死循环，1ms更新一下，也就是主线程中不断定时循环。这个函数结束后，就要释放线程池，reset context等相关释放清理工作了。)
   1. 通过fliter去筛选出在主线程中处理的网络packet（通过协议号，从NetWorkThread[]处理过后放入的msg queue中取出包，然后处理）
   2. sMapMgr->Update(这里主线程将包放到map queue中，以MapUpdateRequest这个类的形式，这也是在主线程中的)
   3. 此时主线程进入m_updater.wait状态，也就是说除非map queue中的updater都进行完，否则主线程就停止了
   4. 循环调用sWorld->Update
3. m_map.Update（这里会另外有一个线程池，即map updater线程池，不断从queue中取出包去调用m_map.update，mapUpdter中的work thread不断从queue中取出数据操作。存在于map.h与map.cpp文件，也是地图管理的核心代码。）
   0. _dynamicTree.update(地图中的动态树包围盒更新，balance)
   1. 取出所有的用户的worldSession进行更新（这个worldSession是处理业务数据包的）
      
   2. player->update
   3. visitNearByCellsOf()(在当前地图，让我被其他用户看到)
   4. SendObjectUpdate()
   5. ScriptProcess()(处理额外脚本)

流程总结

• 主线程会等待所有map线程执行完，这是一个设计错误
  1. 如何修正此设计弊端：主线程可以作为map线程的一部分，不必等待map线程都执行完，参考redis io多线程设计
• 线程是不安全的，之所以这么设计是因为不同的map之间是不会有交集的
  • 但是代价是假如有一个map线程宕机了，整个程序都会宕机，可以设计成多进程

AOI

• 概念：Area of interest是一种游戏中用于管理空间对象的算法，用于减少计算量
• 数据
  1. 静态数据
  2. 动态数据

静态数据

1. 工具生成
   1. mapextractor
      • *.map文件
      • 游戏中地图数据（地形数据）
      • 数据包括：area data；height data；liquid data；hole data等
   2. mmaps_generator
      • .mmap文件、.mmtile文件
      • 游戏中地图移动数据
      • 主要是navmesh，导航数据
   3. vmap4extractor
      • .vmo文件（建筑），.m2文件（3.5以后的版本）
      • 场景信息（建筑物、山脉、水体等）
      • *.mdx(物体包围盒信息)
      • 3d模型信息（角色、怪物、装备等）
      • 用于未来进行碰撞检测
      • 目录：Buildings
   4. vmap4assenbler
      • *.vmtile
      • 生成vmap4数据库（将mmaps_generator和vmap4extractor生成的数据合并到vmap4文件夹中，未来只需要读取vmap4这个文件夹）
2. 数据划分
   1. map对应64X64个grid
   2. 一个grid对应8X8个cell
   3. grid和cell都有自己的坐标系
   4. 以后的角色和怪物都会落到具体的cell中
3. 数据组织
   1. 静态数据：GridMap GridMaps[MAX_NUMBER_OF_GRIDS][MAX_NUMBER_OF_GRIDS]; // 6464，他是从前面生成的那些静态数据读取出来写入的
   2. 动态数据：NGridType* i_grids[MAX_NUMBER_OF_GRIDS][MAX_NUMBER_OF_GRIDS]; // 64*64，比如说有玩家进入，生成的怪物放到这个里面

动态数据

• 动态数据（mmogame是为角色玩家而设计的，假如某个玩家进入某个map，那该map才会被加载，假如玩家在某个cell，那只会加载该grid在内存里，其余部分不加载）

1. 数据组织
   1. NGridType* i_grids[MAX_NUMBER_OF_GRIDS][MAX_NUMBER_OF_GRIDS]
   2. MapRefManager m_mapRefManager,链表结构，当玩家登陆后，传送到上一次保存的地图位置（加载该map），就会调用map.m_mapRefManager.link(map, player),将该玩家加入到这个结构的最末位
   3. DynamicMapTree _dynamicTree
2. 数据驱动
   1. 玩家进入区域后被加载激活
   2. 服务端的数据都是配合玩家进行表演
3. 地图数据加载
   1. HandlerPlayerLogin
   2. AddPlayerToMap
      1. EnsureGridLoadedForActiveObject，加载地图数据主要代码

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

         bool Map::EnsureGridLoaded(Cell const&cell) { EnsureGridLoadedForActiveObject(GridCoord(cell.GridX(),cell.GridY())); // 确保加载某个cell的静态数据，以及创建动态数据结构，通过cell的坐标对应的静态文件名称，从文件中加载cell数据 NGridType *grid = getNGrid(cell.GridX(),cell.GridY()); ASSERT(grid != nullptr); if(!gird->isGridObjectDataLoaded()) { grid->setGridObjectDataLoaded(true); // 这里是访问者模式 ObjectGridLoader loader(*grid, this, cell); // 1. 加载动态数据到i_grid结构中，动态数据分为两部分，一部分来自于静态数据文件中的怪物和npc等，一部分是玩家本身，这里只加载前者; 2. 加载模型数据到_dynamicTree当中 loader.LoadN(); Balance(); return true; } return false; }

      2. AddToGrid ，玩家也加入到动态数据i_grid中
      3. player->SetMap(this)，将玩家也加入到m_mapRefManager结构中
      4. player->AddToWorld() ，将玩家也加入到_dynamicTree当中
4. grid状态机
   1. 状态值
      1. Invalid
      2. Idle
      3. Active
      4. Removal
   2. 状态定时维护
      1. MapManager::Update（主线程）
      2. m_updater.shedule_update
      3. m_updater.wait()（主线程等待）
      4. DelayedUpdate(uint32(i_timer.GetCurrent()))（主线程）
      5. si_GridStates[grid->GetFridState()]->Update(*this, *grid, *info, t_diff);（主线程）
5. 地图数据卸载
   1. LogoutPlayer
      1. _map->RemovePlayerFromMap(_player, true) // 此时不会立即卸载地图数据，而是会等定时器检测到idle状态一段时间后
   2. Invalid->Idle->Active->Idle->Removal
   3. map.UnloadGrid(grid, false) // removal状态一定时间后在主线程的DelayedUpdate中对removal状态的检测中，假如定时器到期调用map.UnloadGrid卸载数据

动态数据管理

• 设计模式-访问者模式

  • 概念：提供一个访问者类，它可以改变元素类的执行算法，元素的执行算法随着访问者改变而改变
  • 解决问题：稳定的数据结构和易变的操作耦合的问题
  • 如何解决：在元素类里面提供一个接待访问者的接口
  • 意图：主要将数据结构与数据操作进行分离

• 实现

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

  // T 算法 // CONTAINER 数据结构 template<class T, class CONTAINER> inline void Map::Visit(Cell const& cell, TypeContainerVisitor<T, CONTAINER>& visitor) { const uint32 x = cell.GridX(); const uint32 y = cell.GridY(); const uint32 cell_x = cell.CellX(); const uint32 cell_y = cell.CellY(); if(!cell.NoCreate()) EnsureGridLoaded(cell); NGridType* grid = getNGrid(x, y); if(grid && grid->isGridObjectDataLoaded()) grid->VisitGrid(cell_x, cell_y, visitor); }

  1. TypeContainer.h
     1. 双向链表
     2. 散列表
     3. 解决不同的双向链表，不同的散列表的差异
  2. TypeContainerFunctions.h
     1. 解决双向链表和散列表之间的差异
  3. TypeContainerVistor.h
     1. 对访问者的抽象
     2. template<class VISITOR, class TYPE_CONTAINER>

• 怎样理解这样的抽象

  1. TypeContainer.h 一种容器，抽象了双向链表和散列表
  2. TypeContainerFunctions.h 对TypeContainer进一步做抽象，将双向链表和散列表的接口统一
  3. TypeContainerVistor.h对访问者进行抽象，template<class VISITOR, class TYPE_CONTAINER>，实际上就是对容器调用传入visitor的.visitor函数。
  4. 现在map类非常的清爽，统一用TypeContainerVistor进行调用，我们只需要实现不同的visitor就可以了

• 应用举例：RefManager（双向链表形式的容器）

  1. Map（继承自RefManager，本身以双向链表来组织）
  2. NGridType（其中包含两个TypeContainer，也就是两个双向链表，一个是放数据，一个放包围盒）
     1. TypeMapContainer i_container（数据）
     2. TypeMapContainer i_objects（包围盒）
  3. 

• 使用访问者模式

  1 2 3 4 5 6 7 8 9 10 11

  { // load creatures and game objects TypeContainerVisitor<ObjectGridLoader, GridTypeMapContainer> visitor(*this); i_grid.VisitGrid(x, y, visitor) ; } { // load corpses(not bones) ObjectworldLoader worker(*this); TypeContainerVisitor<ObjectworldLoader, WorldTypeMapContainer> visitor(worker); i_grid.VisitGrid(x, y, visitor) ; }

碰撞检测

• 碰撞检测目标：对象模型
• 数据来源：加载地图数据时，vmap数据
• 功能：
  1. 是否在视线范围内
  2. 碰撞检测，算命中位置
  3. 获取地图信息
• 组织：
  • 每一个grid对应一个BIH树，用于碰撞检测
  • 一个map的grid是6464，BIH树也是6464，和grid一样，不是每一个grid都会被加载，只有玩家进入一个grid时才会加载，BIH树也是如此
• 实现
  1. AABB算法-轴对称边界盒算法——解决了光线与包围盒相交，避免费时计算
  2. 算法步骤
     1. 构建BIH树（快排思想）
        1. 计算包围盒（vmap4数据中已经有了，进行加载）
        2. 根节点包含该grid所有对象模型的包围盒
        3. 选取一个切割平面，将grid当中所有对象分为两个部分（这样，在碰撞检测的时候，可以每次排除一半）
        4. 将3个中的两个子集分别递归执行2，3，直到停止递归条件（递归深度为64就停止）
        • 注意：每个节点是其子节点的并集，就是上层节点是包含下层节点对象的
     2. 光线追踪
        1. 从根节点开始遍历，判断节点是否与光线相交
        2. 如果不想交，直接跳过该节点，以及其子树
        3. 如果相交，则继续向子树遍历该节点的子树
• 作用
  1. 通过使用BIH树，可以有效减少碰撞检测次数，提高检测效率
  2. 但是构建和遍历都是需要计算成本，而且BIH树本身是不稳定的（随时有新加入节点或删除节点）
• 优化
  1. 初始化时构建一次
  2. 定时构建
     • 如果BIH树发生改变才会重新构建
     • 200ms才检测一次是否需要构建（不会实时构建，成本太大）