游戏服务端 - AOI九宫格算法

2023-10-08 17:10
文章标签 算法 服务端 游戏 九宫格 aoi

本文主要是介绍游戏服务端 - AOI九宫格算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

游戏服务端 - AOI九宫格算法

  下面简述内容，只针对平面上的简易场景。我们将平面上的场景分为一个个格子（Grid），场景管理所有的Grid。如下（假设场景的长宽均为20，每个格子宽高定义为1）：

效果图

  其中可分为400个Grid，即如果一个场景每个Grid的宽高均为1（即每个单元unitSizeX为1，unitSizeY为1），那么一个场景需要同时管理400个Grid。

TIPS：每个Grid中可能有多个物体（角色），目前暂定场景中都是玩家对象，即为网络游戏，均为在线玩家角色（AOI对象）。

Grid对象

  作为服务端AOI算法，那么我们应当知道，在什么情况下应该通知附近的Grid哪个AOI对象消失，哪个AOI对象出现、哪个AOI对象状态发生改变（主要针对状态同步，当状态改变时时通知）。以及对于状态改变的玩家来说，在它自己的视野里，哪些Grid的AOI即将在视野内消失，哪些Grid的AOI即将在视野内出现。也就是说，这里有一个一对多和多对一的概念，对于其它Grid中的AOI，我们应该告知它们当前状态发生改变的AOI即将消失、即将出现、状态改变，也就是多对一，多个Grid中的AOI关注一个AOI。而对于当前状态发生改变的AOI，它自己视野内有哪些Grid中的AOI即将消失、出现，也就是一个AOI关注多个Grid中的AOI，一对多。这里指的状态改变包括从一个Grid移动到另外一个Grid、即使没有走出当前Grid，但是从停止到移动等这类改变均统称为状态改变。

  再给出示例之前，需要先知道如果获取一个AOI的视野范围？

bool _GetAOI(int32_t centerGridIndex,std::vector<int32_t>& outPut) {if (centerGridIndex == -1) {return false;}//视野方向：从右方逆时针旋转，共八个方向int32_t col = m_role->GetScene()->GetCol(); //获取列，这里为20int deltaIndexArr[8] = {1, -col + 1, -col, -col - 1, -1, col - 1, col, col + 1 };//获取实体 AOIoutPut.clear();outPut.push_back(centerGridIndex);  //包括自身在内的九宫格for (int i = 0; i < 8; i++) {outPut.push_back(centerGridIndex + deltaIndexArr[i]);}return true;
}

  通过上述我们可以获取一个AOI的视野范围（包括自己所在Grid）。

  现假定一个AOI从Grid为21的格子向42的位置移动。那么该AOI旧的视野范围为0、1、2、20、21、22、40、41、42。新的视野范围为21、22、23、41、42、43、61、62、63。那么对于其它Grid中的AOI来说，我们应该通知它们（包括0、1、2、20、40格子内的AOI）当前AOI即将消失。同时通知（包括23、43、61、62、63格子内的AOI）当前AOI即将出现。针对当前AOI来说，它的视野范围也有变化，那就是Grid为0、1、2、20、40格子内的AOI即将消失，Grid为23、43、61、62、63格子内的AOI即将出现。那么对于Grid为21、22、41、42的格子，如果当前AOI没有发生其它的状态改变，那么是不用通知的。因为对于这些Grid中的AOI，当前AOI意味这不改变状态。

效果图

  下面给出通过目的地Grid，求三个队列状态（即将出现、即将消失、状态改变）的算法。

//destGridIndex 目的地Grid，output为输入输出值
bool GetChangedAOIs(int32_t destGridIndex,std::vector<std::vector<int32_t>>& outPut) {outPut.clear();outPut.resize(3);std::vector<int32_t>& appearAOIArr    = outPut[(int)AOI_STATUS::AOI_APPEAR];std::vector<int32_t>& disappearAOIArr = outPut[(int)AOI_STATUS::AOI_DISAPPEAR];std::vector<int32_t>& unChangeAOIArr  = outPut[(int)AOI_STATUS::AOI_UNCHANGE];int32_t oldGridIndex = m_centerGridIndex;//获取实体 旧AOIstd::vector<int32_t> oldAOIArr;//获取实体 新AOIstd::vector<int32_t> newAOIArr;if (oldGridIndex >= 0) {_GetAOI(oldGridIndex, oldAOIArr);_GetAOI(destGridIndex, newAOIArr);}std::sort(oldAOIArr.begin(), oldAOIArr.end());std::sort(newAOIArr.begin(), newAOIArr.end());//求对用的AOI区域int32_t indexOld = 0;int32_t indexNew = 0;while (indexOld < oldAOIArr.size() && indexNew < newAOIArr.size()) {//两个AOI的交集，即不变的AOI区域if (oldAOIArr[indexOld] == newAOIArr[indexNew]) {unChangeAOIArr.push_back(newAOIArr[indexNew]);++indexOld;++indexNew;}// oldAOI特有的区域，即需要通知的AOI，告知即将有AOI实体出现else if (oldAOIArr[indexOld] < newAOIArr[indexNew]) {appearAOIArr.push_back(newAOIArr[indexNew]);indexNew++;}else if (oldAOIArr[indexOld] > newAOIArr[indexNew]) {disappearAOIArr.push_back(oldAOIArr[indexOld]);indexOld++;}//将剩下部分加入对应队列中while (indexNew < newAOIArr.size()) {appearAOIArr.push_back(newAOIArr[indexNew]);++indexNew;}while (indexOld < oldAOIArr.size()) {disappearAOIArr.push_back(oldAOIArr[indexOld]);++indexOld;}}return true;
}

AOI对象

  在当前示例中，一个AOI对象实际上就是一个角色，那么如何通过角色坐标获取到它应当位于哪个Grid中呢？

int32_t index = (int)(pos.X / m_unitSizeX) + m_col * (int)(pos.Y / m_unitSizeY);

  pos表示角色的平面坐标。m_unitSizeX、m_unitSizeY对应上文已经阐述，即为1。m_col为列长（宽，20）。假如当前有一个角色的坐标为(2.8,1.9），那么根据上述公式为：index = (int)(2.8 / 1) + 20 * (1.9 / 1) = 22，即它位于第22个Grid中（根据常识也可验证，这么计算是正确的）。

  通过比较它即将前往的位置和当前位置，即可知是否改变Grid。

bool _IsChangeGridIndex(const struct POSITION& oldPos,const struct POSITION& newPos){int32_t oldGridIndex = _GetGridIndex(oldPos);int32_t newGridIndex = _GetGridIndex(newPos);return (oldGridIndex != newGridIndex);
}

完整实例

  实现完整实例如下（仅包含AOI相关代码，仅供参考）：

Scene.h

//管理所有加入场景的角色（一个玩家对应一个角色）
class Scene {
public:Scene()  {}~Scene() {}bool Init(int32_t width, int32_t length);bool UnInit();//场景逻辑帧更新bool UpdateScene();         //角色加入场景bool AddRole(class Player* player, class Role* role);bool DelteRole(class Role* role);int32_t GetCol();int32_t GetRow();// AOI操作, 位置同步AOI// isStatusChange = true时，表示状态改变，即使不跨Grid也广播信息// isStatusChange = false时，表示状态不改变，这时跨Grid或者达到边缘时广播信息bool MoveSyncAOI(class Role* role, const struct POSITION& newPos, bool isStatusChange);bool EnterGrid(class Role* role);bool ExitGrid(class Role* role);
private://角色退出场景bool _OnDeleteRole(Topicype type, void* userData);//AOI操作 //查看是否改变grid，不变则返回false，改变则返回truebool _IsChangeGridIndex(const struct POSITION& oldPos,const struct POSITION& newPos);//获取坐标所在的Grid位置int32_t _GetGridIndex(const struct POSITION& pos);//进入一个Gridbool _EnterGrid(class Role* role, int32_t gridIndex);//从一个Grid退出bool _ExitGrid(class Role* role);//区域事件广播bool _OtherAOIAnnounce();//自身视野变化广播bool _SelfAOIAnnounce();
private:class RoleMgr*     m_roleMgr;       //角色管理器//AOI模块std::vector<Grid*> m_gridArrs;int32_t m_unitSizeX;int32_t m_unitSizeY;int32_t m_col;int32_t m_row;//对AOI区域队列进行广播，这里表示多个AOI区域对一个Role的观察，多对一std::vector<std::pair<std::vector<int32_t>, class Role*>> m_enterOtherAOISightArr;std::vector<std::pair<std::vector<int32_t>, int64_t>> m_exitOtherAOISightArr;std::vector<std::pair<std::vector<int32_t>, class Role*>> m_statusChangeAOISightArr;//更新自身的AOI，即AOI自身角度看哪些AOI消失、AOI出现，一对多std::vector<std::pair<class Role*, std::vector<int32_t>>> m_enterSelfAOISightArr;std::vector<std::pair<class Role*, std::vector<int32_t>>> m_exitSelfAOISightArr;
};

Scene.cpp

#include "Scene.h"bool Scene::Init(int32_t width, int32_t length) {m_roleMgr   = (RoleMgr*)MALLOC(sizeof(RoleMgr));assert(NULL != m_roleMgr);new(m_roleMgr) RoleMgr();m_roleMgr->Init(this);//初始化AOIm_unitSizeX = 1;m_unitSizeY = 1;m_row = length / m_unitSizeY;m_col = width / m_unitSizeX;for (int i = 0; i < m_row* m_col; i++) {Grid* grid = (Grid*)MALLOC(sizeof(Grid));assert(NULL != grid);new(grid) Grid();grid->Init(i);m_gridArrs.push_back(grid);}m_enterOtherAOISightArr.clear();m_exitOtherAOISightArr.clear();m_statusChangeAOISightArr.clear();m_enterSelfAOISightArr.clear();m_exitSelfAOISightArr.clear();result = true;
Exit:return result;
}bool Scene::UnInit() {if (m_roleMgr) {m_roleMgr->UnInit();Free(m_roleMgr);m_roleMgr = nullptr;}//释放AOI队列for (auto& grid : m_gridArrs) {grid->UnInit();Free(grid);}m_gridArrs.clear();m_enterOtherAOISightArr.clear();m_exitOtherAOISightArr.clear();m_statusChangeAOISightArr.clear();m_enterSelfAOISightArr.clear();m_exitSelfAOISightArr.clear();return true;
}bool Scene::UpdateScene() {//移动同步m_roleMgr->UpdateRoles();//处理AOI队列_OtherAOIAnnounce();_SelfAOIAnnounce();return true;
}bool Scene::AddRole(Player* player, Role* role) {//加入场景m_roleMgr->AddRole(player, role);//进入AOIbool nRet = EnterGrid(role);return nRet;
}//事件系统通知
bool Scene::DeleteRole(class Role* role) {ExitGrid(role);//退出场景，删除rolem_roleMgr->DeleteRole(role);return true;
}int32_t Scene::GetCol() {return m_col;
}int32_t Scene::GetRow() {return m_row;
}bool Scene::MoveSyncAOI(Role* role, const POSITION& newPos, bool isStatusChange) {bool nRet = _IsChangeGridIndex(role->GetRoleStatus()->POS, newPos);//位置合法且Grid改变，这时需要通知对该区域感兴趣的AOIif (newPos.X >= 0 && newPos.X < m_sceneMap.GetLength() &&newPos.Y >= 0 && newPos.Y < m_sceneMap.GetWidth()  && nRet) {int32_t newGridIndex = _GetGridIndex(newPos);if (newGridIndex >= 0 && newGridIndex < m_gridArrs.size()) {_ExitGrid(role);_EnterGrid(role, newGridIndex);//更新坐标//role->SetPos(newPos.X, newPos.Y);//获取即将出现、即将消息、不变的AOI区域std::vector<std::vector<int32_t>> aoiArrs;role->GetChangedAOIs(newGridIndex, aoiArrs);//加入即将出现队列m_enterOtherAOISightArr.push_back(std::make_pair(aoiArrs[(int32_t)AOI_STATUS::AOI_APPEAR], role));//加入即将消失队列m_exitOtherAOISightArr.push_back(std::make_pair(aoiArrs[(int32_t)AOI_STATUS::AOI_DISAPPEAR], role->GetRoleID()));//加入状态改变队列m_statusChangeAOISightArr.push_back(std::make_pair(aoiArrs[(int32_t)AOI_STATUS::AOI_UNCHANGE], role));//更新自身的AOI，即AOI自身角度看哪些AOI消失、AOI出现，一对多m_enterSelfAOISightArr.push_back(std::make_pair(role, aoiArrs[(int32_t)AOI_STATUS::AOI_APPEAR]));m_exitSelfAOISightArr.push_back(std::make_pair(role, aoiArrs[(int32_t)AOI_STATUS::AOI_DISAPPEAR]));role->UpdateSelfAOI(newGridIndex);}}//Grid未改变，此时如果状态发生改变则加入状态改变队列中else { //更新坐标//role->SetPos(newPos.X, newPos.Y);if (isStatusChange) {//加入状态改变队列m_statusChangeAOISightArr.push_back(std::make_pair(role->GetAOI(), role));}}return true;
}bool Scene::EnterGrid(Role* role) {//AOI 进入场景//获取加入场景角色GridIndexint32_t gridIndex = _GetGridIndex(role->GetRoleStatus()->POS);bool nRet = _EnterGrid(role, gridIndex);if (nRet) {//更新实体自身的AOIrole->UpdateSelfAOI(gridIndex);//加入即将出现队列const std::vector<int32_t>& gridArrs = role->GetAOI();m_enterOtherAOISightArr.push_back(std::make_pair(gridArrs, role));//更新自身AOI队列m_enterSelfAOISightArr.push_back(std::make_pair(role, gridArrs));}return nRet;
}bool Scene::ExitGrid(Role* role) {//AOI 退出场景bool nRet = _ExitGrid(role);if (nRet) {//加入即将消失队列const std::vector<int32_t>& gridArrs = role->GetAOI();m_exitOtherAOISightArr.push_back(std::make_pair(gridArrs, role->GetRoleID()));//更新自身AOIrole->UpdateSelfAOI(-1);}return nRet;
}bool Scene::_IsChangeGridIndex(const POSITION& oldPos,const POSITION& newPos) {int32_t oldGridIndex = _GetGridIndex(oldPos);int32_t newGridIndex = _GetGridIndex(newPos);return (oldGridIndex != newGridIndex);
}int32_t Scene::_GetGridIndex(const POSITION& pos) {int32_t index = (int)(pos.X / m_unitSizeX) + m_col * (int)(pos.Y / m_unitSizeY);return index;
}bool Scene::_EnterGrid(Role* role, int32_t gridIndex) {assert(role != nullptr);bool result = false;if (gridIndex >= 0 && gridIndex < m_gridArrs.size()) {result = m_gridArrs[gridIndex]->AddEntity(role);}return result;
}bool Scene::_ExitGrid(Role* role) {assert(nullptr != role);bool result = false;int32_t gridIndex = _GetGridIndex(role->GetRoleStatus()->POS);if (gridIndex >= 0 && gridIndex < m_gridArrs.size()) {result = m_gridArrs[gridIndex]->RemoveEntity(role);}return result;
}bool Scene::_OtherAOIAnnounce() {//进入视野for (auto& gridList : m_enterOtherAOISightArr) {//一个角色即将进入某些AOI的视野for (auto& gridIndex : gridList.first) {if (gridIndex >= 0 && gridIndex < m_gridArrs.size()) {m_gridArrs[gridIndex]->OtherEntityEnterAnnounce(gridList.second);}}}m_enterOtherAOISightArr.clear();//离开视野for (auto& gridList : m_exitOtherAOISightArr) {//一个角色即将离开某些AOI的视野for (auto& gridIndex : gridList.first) {if (gridIndex >= 0 && gridIndex < m_gridArrs.size()) {m_gridArrs[gridIndex]->OtherEntityExitAnnounce(gridList.second);}}}m_exitOtherAOISightArr.clear();//状态改变for (auto& gridList : m_statusChangeAOISightArr) {for (auto& gridIndex : gridList.first) {if (gridIndex >= 0 && gridIndex < m_gridArrs.size()) {m_gridArrs[gridIndex]->EntityStatusChangeAnnounce(gridList.second);}}}m_statusChangeAOISightArr.clear();return true;
}bool Scene::_SelfAOIAnnounce() {//进入视野for (auto& gridList : m_enterSelfAOISightArr) {//一个角色自身AOI的视野即将出现哪些Gridfor (auto& gridIndex : gridList.second) {if (gridIndex >= 0 && gridIndex < m_gridArrs.size()) {m_gridArrs[gridIndex]->NotifyEntityEnter(gridList.first);}}}m_enterSelfAOISightArr.clear();//离开视野for (auto& gridList : m_exitSelfAOISightArr) {//一个角色自身AOI的视野即将消失哪些Gridfor (auto& gridIndex : gridList.second) {if (gridIndex >= 0 && gridIndex < m_gridArrs.size()) {m_gridArrs[gridIndex]->NotifyEntityExit(gridList.first);}}}m_exitSelfAOISightArr.clear();return true;
}

Grid.h

#pragma once
#include <unordered_set>
#include <assert.h>
#include "../Role.h"class Grid {
public:Grid()  {}~Grid() {}bool Init(int32_t gridIndex);bool UnInit();bool AddEntity(GAME_SERVICE::Role* role);bool RemoveEntity(GAME_SERVICE::Role* role);//多对一bool OtherEntityEnterAnnounce(GAME_SERVICE::Role* role);bool OtherEntityExitAnnounce(int64_t roleID);bool EntityStatusChangeAnnounce(GAME_SERVICE::Role* role);//一对多bool NotifyEntityEnter(GAME_SERVICE::Role* role);bool NotifyEntityExit(GAME_SERVICE::Role*  role);private:bool _EnterOrStatusChangeAnnounce(GAME_SERVICE::Role* role);private:int32_t m_gridIndex;std::unordered_set<GAME_SERVICE::Role*> m_entitySet;        //该grid上存在的实体
};

Grid.cpp

#include "Grid.h"bool Grid::Init(int32_t gridIndex) {assert(gridIndex >= 0);m_gridIndex = gridIndex;m_entitySet.clear();return true;
}bool Grid::UnInit() {m_entitySet.clear();return true;
}bool Grid::AddEntity(GAME_SERVICE::Role* role) {assert(role != nullptr);auto nRet = m_entitySet.insert(role);return nRet.second;
}bool Grid::RemoveEntity(GAME_SERVICE::Role* role) {assert(role != nullptr);m_entitySet.erase(role);return true;
}bool Grid::OtherEntityEnterAnnounce(GAME_SERVICE::Role* role) {return _EnterOrStatusChangeAnnounce(role);
}bool Grid::OtherEntityExitAnnounce(int64_t roleID) {TCCamp::ExitSceneAnnounce exitAnnounce;exitAnnounce.add_roleids(roleID);for (auto& other : m_entitySet) {other->SendMsg(TCCamp::SERVER_CMD::SERVER_ROLE_EXIT_SCENE_ANNOUNCE, &exitAnnounce);}return true;
}bool Grid::EntityStatusChangeAnnounce(GAME_SERVICE::Role* role) {return _EnterOrStatusChangeAnnounce(role);
}bool Grid::NotifyEntityEnter(GAME_SERVICE::Role* role) {TCCamp::MoveSyncAnnounce    moveAnnounce;TCCamp::PBRoleMoveSyncData* pbRoleMoveSyncData = nullptr;for (auto& other : m_entitySet) {if (other->GetRoleID() != role->GetRoleID()) {pbRoleMoveSyncData = moveAnnounce.add_datas();pbRoleMoveSyncData->set_roleid(other->GetRoleID());other->RoleStatusConvertToPBObj(pbRoleMoveSyncData->mutable_status());}}role->SendMsg(TCCamp::SERVER_CMD::SERVER_ROLE_MOVE_SYNC_ANNOUNCE,&moveAnnounce);return true;
}bool Grid::NotifyEntityExit(GAME_SERVICE::Role* role) {TCCamp::ExitSceneAnnounce exitAnnounce;for (auto& other : m_entitySet) {if (other->GetRoleID() != role->GetRoleID()) {exitAnnounce.add_roleids(other->GetRoleID());}}role->SendMsg(TCCamp::SERVER_CMD::SERVER_ROLE_EXIT_SCENE_ANNOUNCE,&exitAnnounce);return true;
}bool Grid::_EnterOrStatusChangeAnnounce(GAME_SERVICE::Role* role) {TCCamp::MoveSyncAnnounce    moveAnnounce;TCCamp::PBRoleMoveSyncData* pbRoleMoveSyncData = nullptr;pbRoleMoveSyncData = moveAnnounce.add_datas();pbRoleMoveSyncData->set_roleid(role->GetRoleID());role->RoleStatusConvertToPBObj(pbRoleMoveSyncData->mutable_status());for (auto& other : m_entitySet) {other->SendMsg(TCCamp::SERVER_CMD::SERVER_ROLE_MOVE_SYNC_ANNOUNCE, &moveAnnounce);}return true;
}

AOI.h

#pragma once//对当前区域感兴趣的格子（Grid），该区域对它们来说的状态
enum class AOI_STATUS {AOI_APPEAR,AOI_DISAPPEAR,AOI_UNCHANGE,
};class AOI {
public:AOI()  {}~AOI() {}bool Init(class Role* role);bool UnInit();//更新实体AOI（通知场景 更新实体能看到的其它实体信息）bool UpdateAOI(int32_t destGridIndex);//获取当前AOI区域const std::vector<int32_t>& GetAOI();// 获取实体，包括即将出现、即将消失、状态不变的AOI// TIPS:（不保证gridIndex合法，后续使用需判断合法性）bool GetChangedAOIs(int32_t destGridIndex,std::vector<std::vector<int32_t>>& outPut);
private:// 获取以当前场景的centerGridIndex为中心的AOI区域// TIPS:（不保证gridIndex合法，后续使用需判断合法性）bool _GetAOI(int32_t centerGridIndex, std::vector<int32_t>& outPut);private:int32_t m_centerGridIndex;Role*   m_role;std::vector<int32_t> m_aoiGridIndexArr;
};

AOI.cpp

#include "AOI.h"
#include "../Scene.h"
#include "../Role.h"bool AOI::Init(Role* role) {assert(nullptr != role);m_centerGridIndex = -1;m_role = role;m_aoiGridIndexArr.clear();return true;
}bool AOI::UnInit() {m_aoiGridIndexArr.clear();m_centerGridIndex = -1;m_role = nullptr;return true;
}bool AOI::UpdateAOI(int32_t destGridIndex) {// 更新aoim_centerGridIndex = destGridIndex;m_aoiGridIndexArr.clear();_GetAOI(m_centerGridIndex, m_aoiGridIndexArr);return true;
}const std::vector<int32_t>& AOI::GetAOI() {return m_aoiGridIndexArr;
}bool AOI::GetChangedAOIs(int32_t destGridIndex,std::vector<std::vector<int32_t>>& outPut) {bool result = false;outPut.clear();outPut.resize(3);std::vector<int32_t>& appearAOIArr    = outPut[(int)AOI_STATUS::AOI_APPEAR];std::vector<int32_t>& disappearAOIArr = outPut[(int)AOI_STATUS::AOI_DISAPPEAR];std::vector<int32_t>& unChangeAOIArr  = outPut[(int)AOI_STATUS::AOI_UNCHANGE];int32_t oldGridIndex = m_centerGridIndex;//获取实体 旧AOIstd::vector<int32_t> oldAOIArr;//获取实体 新AOIstd::vector<int32_t> newAOIArr;if (oldGridIndex >= 0) {_GetAOI(oldGridIndex, oldAOIArr);_GetAOI(destGridIndex, newAOIArr);}std::sort(oldAOIArr.begin(), oldAOIArr.end());std::sort(newAOIArr.begin(), newAOIArr.end());//求对用的AOI区域int32_t indexOld = 0;int32_t indexNew = 0;while (indexOld < oldAOIArr.size() && indexNew < newAOIArr.size()) {//两个AOI的交集，即不变的AOI区域if (oldAOIArr[indexOld] == newAOIArr[indexNew]) {unChangeAOIArr.push_back(newAOIArr[indexNew]);++indexOld;++indexNew;}// oldAOI特有的区域，即需要通知的AOI，告知即将有AOI实体出现else if (oldAOIArr[indexOld] < newAOIArr[indexNew]) {appearAOIArr.push_back(newAOIArr[indexNew]);indexNew++;}else if (oldAOIArr[indexOld] > newAOIArr[indexNew]) {disappearAOIArr.push_back(oldAOIArr[indexOld]);indexOld++;}//将剩下部分加入对应队列中while (indexNew < newAOIArr.size()) {appearAOIArr.push_back(newAOIArr[indexNew]);++indexNew;}while (indexOld < oldAOIArr.size()) {disappearAOIArr.push_back(oldAOIArr[indexOld]);++indexOld;}}return true;
}bool AOI::_GetAOI(int32_t centerGridIndex,std::vector<int32_t>& outPut) {if (centerGridIndex == -1) {return false;}//视野方向：从右方逆时针旋转，共八个方向int32_t col = m_role->GetScene()->GetCol();int deltaIndexArr[8] = {1, -col + 1, -col, -col - 1, -1, col - 1, col, col + 1 };//获取实体 AOIoutPut.clear();outPut.push_back(centerGridIndex);  //包括自身在内的九宫格for (int i = 0; i < 8; i++) {outPut.push_back(centerGridIndex + deltaIndexArr[i]);}return true;
}

这篇关于游戏服务端 - AOI九宫格算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/166771。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
国产游戏崛起：技术革新与文化自信的双重推动

国产游戏崛起：技术革新与文化自信的双重推动

近年来，国产游戏行业发展迅猛，技术水平和作品质量均得到了显著提升。特别是以《黑神话：悟空》为代表的一系列优秀作品，成功打破了过去中国游戏市场以手游和网游为主的局限，向全球玩家展示了中国在单机游戏领域的实力与潜力。随着中国开发者在画面渲染、物理引擎、AI 技术和服务器架构等方面取得了显著进展，国产游戏正逐步赢得国际市场的认可。然而，面对全球游戏行业的激烈竞争，国产游戏技术依然面临诸多挑战，未来的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2