1. 簡介

AOI主要有九宮格、燈塔和十字鏈表的算法實現(xiàn)。本文闡述十字鏈表的實現(xiàn)

2.?基本原理

若是二維地圖，將地圖內(nèi)的對象按照坐標值，從小到大分在x軸和y軸兩個鏈表上。如果是三維地圖，則還需要維護多一個z軸的鏈表

3. 基本接口

?Add：對象進入場景

Move：對象在場景內(nèi)移動

Leave：對象離開場景

4. 代碼如下，注釋非常詳盡

scene.h

#ifndef __CScene_H__ #define __CScene_H__ #include <map> #include <list> using namespace std;// 注意：本示例的AOI范圍指的是以對象為中心的正方形// 地圖內(nèi)的對象 class CEntity { public:int x; // X坐標int y; // Y坐標int id; // 對象的唯一IDint radius; // 對象的AOI半徑list<CEntity*>::iterator x_pos; // X鏈上的指針list<CEntity*>::iterator y_pos; // Y鏈上的指針CEntity(int _id, int _x, int _y, int _radius) : id(_id), x(_x), y(_y), radius(_radius) {} };typedef map<int, CEntity*> EntityMap; typedef list<CEntity*> EntityList;// 場景 class CScene { public:CScene();~CScene();// 添加一個新的對象插入到指定坐標（x,y）void Add(int id, int x, int y, int distance = 2);// 移動一個對象，新位置點（x,y）void Move(int id, int x, int y);// 刪除一個對象void Leave(int id);private:// 獲取指定對象的AOI對象列表void GetRangeSet(CEntity* pEntity, EntityMap* pEntityMap);// 更新對象CEntity到坐標（x,y）void UpdateEntityPosition(CEntity* pEntity, int x, int y);private:EntityMap m_mapEntity; // 本場景所有的對象EntityList m_listXEntity; // X鏈EntityList m_listYEntity; // Y鏈 };#endif // __CScene_H__

scene.cpp

#include <math.h> #include <stdio.h> #include <stdlib.h> #include "scene.h"CScene::CScene() { }CScene::~CScene() {// 刪除場景內(nèi)的所有對象EntityMap::iterator tmp;for (EntityMap::iterator iter = m_mapEntity.begin(); iter != m_mapEntity.end(); ) {tmp = iter;++iter;delete tmp->second;} }// 添加一個新的對象插入到指定坐標（x,y） void CScene::Add(int id, int x, int y, int distance) {// 已經(jīng)存在該ID，直接返回if (m_mapEntity.find(id) != m_mapEntity.end()) {return;}// 新創(chuàng)建一個對象CEntity* pEntity = new CEntity(id, x, y, distance);m_mapEntity[pEntity->id] = pEntity;EntityList::iterator iter;// 在X鏈上找到插入位置 for (iter = m_listXEntity.begin(); iter != m_listXEntity.end();iter++){if ((*iter)->x > x){break;}}// 在iter位置前面插入，同時記錄下在X鏈上的位置pEntity->x_pos = m_listXEntity.insert(iter,pEntity);// 在Y鏈上找到插入位置 for (iter = m_listYEntity.begin(); iter != m_listYEntity.end();iter++){if ((*iter)->y > y){break;}}// 在iter位置前面插入，同時記錄下在Y鏈上的位置pEntity->y_pos = m_listYEntity.insert(iter,pEntity);// 獲取AOI列表EntityMap newMap;GetRangeSet(pEntity, &newMap);// 1. 把pEntity的進入AOI消息通知他們 // 2. 通知pEntity，他們進入了AOIfor (EntityMap::iterator iter = newMap.begin(); iter != newMap.end(); ++iter) {printf("send [%d:(%d,%d)]\t ENTER msg to obj [%d:(%d,%d)]\n",pEntity->id, pEntity->x, pEntity->y,iter->first, iter->second->x, iter->second->y);printf("send [%d:(%d,%d)]\t ENTER msg to obj [%d:(%d,%d)]\n",iter->first, iter->second->x, iter->second->y,pEntity->id, pEntity->x, pEntity->y);} }// 更新對象CEntity到坐標（x,y） void CScene::UpdateEntityPosition(CEntity* pEntity, int x, int y) {// 原來的坐標int old_x = pEntity->x;int old_y = pEntity->y;// 新坐標pEntity->x = x;pEntity->y = y;EntityList::iterator iter;// 查找新的X坐標// 如果新坐標的x比舊坐標的x大，就往后面遍歷if (pEntity->x > old_x) {if (pEntity->x_pos != m_listXEntity.end()) {// 取得原X指針位置iter = pEntity->x_pos;// 往后面移動一個節(jié)點，作為搜索起始節(jié)點++iter;// 刪除X鏈的舊節(jié)點m_listXEntity.erase(pEntity->x_pos);// 往后面遍歷while (iter != m_listXEntity.end()) {// 找到第一個x值大于新坐標x指的節(jié)點if ((*iter)->x > pEntity->x) {break;}++iter;}// X鏈新位置上插入，并記錄位置pEntity->x_pos = m_listXEntity.insert(iter, pEntity);}} else if (x < old_x) // 如果新坐標的x比舊坐標的x小，就往前面遍歷{if (pEntity->x_pos != m_listXEntity.begin()) {// 取得原X指針位置iter = pEntity->x_pos;// 往前面移動一個節(jié)點，作為搜索起始節(jié)點--iter;// 刪除舊節(jié)點m_listXEntity.erase(pEntity->x_pos);// 往前面遍歷while (iter != m_listXEntity.begin()) {// 找到第一個x值小于新坐標x指的節(jié)點if ((*iter)->x < pEntity->x) {// 要指向該節(jié)點的下一個節(jié)點，因為iter是第一個比pEntity的x值小的，那么后面一個節(jié)點才是大于等于x值的，應(yīng)該插在這個節(jié)點前面才對++iter;break;}--iter;}// X鏈新位置上插入，并記錄位置pEntity->x_pos = m_listXEntity.insert(iter, pEntity);}else{// 不需處理，因為已經(jīng)是最前面了，x,y坐標改了就行}}// 如果新坐標的y值比舊坐標的y值大，就往后面遍歷if (y > old_y) {if (pEntity->y_pos != m_listYEntity.end()) {// 取得原y指針位置iter = pEntity->y_pos;// 往后面移動一個節(jié)點，作為搜索起始節(jié)點++iter;// 刪除Y鏈的舊節(jié)點m_listYEntity.erase(pEntity->y_pos);// 往后面遍歷while (iter != m_listYEntity.end()) {// 找到第一個y值大于新坐標y值的節(jié)點if ((*iter)->y > pEntity->y) {break;}++iter;}// Y鏈新位置上插入，并記錄位置pEntity->y_pos = m_listYEntity.insert(iter, pEntity);}} else if (y < old_y) // 如果新坐標的x比舊坐標的x小，就往前面遍歷{if (pEntity->y_pos != m_listYEntity.begin()) {// 取得原y指針位置iter = pEntity->y_pos;// 往前面移動一個節(jié)點，作為搜索起始節(jié)點--iter;// 刪除Y鏈的舊節(jié)點m_listYEntity.erase(pEntity->y_pos);// 往前面遍歷while (iter != m_listYEntity.begin()) {// 找到第一個y值小于新坐標y值的節(jié)點if (pEntity->y - (*iter)->y > 0) {// 要指向該節(jié)點的下一個節(jié)點，因為iter是第一個比pEntity的y值小的，那么后面一個節(jié)點才是大于等于y值的，，應(yīng)該插在這個節(jié)點前面才對++iter;break;}--iter;}// Y鏈新位置上插入，并記錄位置pEntity->y_pos = m_listYEntity.insert(iter, pEntity);}} }// 移動一個對象，新位置點（x,y） void CScene::Move(int id, int x, int y) {// 在對象列表中查找該對象EntityMap::iterator iterEntity = m_mapEntity.find(id);if (iterEntity == m_mapEntity.end()) {return;}// 該對象指針CEntity* pEntity = iterEntity->second;// 舊AOI列表，新AOI列表EntityMap oldMap, newMap;// 獲取舊的AOI列表GetRangeSet(pEntity, &oldMap);// 更新對象位置到新坐標（x,y）UpdateEntityPosition(pEntity, x, y);// 獲取新的AOI列表GetRangeSet(pEntity, &newMap);// 遍歷舊AOI列表里面的對象// 若在新AOI列表里面存在，說明該對象是兩次AOI列表里面的交集，把pEntity的移動消息通知他們// 若在新AOI列表里面不存在，則說明是要刪除的對象（操作如下 1.把pEntity的離開AOI消息通知他們 2. 通知pEntity，他們離開了AOI）for (EntityMap::iterator iter = oldMap.begin(); iter != oldMap.end(); ++iter) {if (newMap.find(iter->first) != newMap.end()) {printf("send [%d:(%d,%d)]\t MOVE msg to obj [%d:(%d,%d)]\n",pEntity->id, pEntity->x, pEntity->y, iter->first, iter->second->x, iter->second->y);}else{printf("send [%d:(%d,%d)]\t LEAVE msg to obj [%d:(%d,%d)]\n",pEntity->id, pEntity->x, pEntity->y,iter->first, iter->second->x, iter->second->y);printf("send [%d:(%d,%d)]\t LEAVE msg to obj [%d:(%d,%d)]\n",iter->first, iter->second->x, iter->second->y,pEntity->id, pEntity->x, pEntity->y);}}// 遍歷新AOI列表里面的對象// 若在交集move_set中不存在，則說明是新添加的對象（操作如下 1.把pEntity的進入AOI消息通知他們 2. 通知pEntity，他們進入了AOI）for (EntityMap::iterator iter = newMap.begin(); iter != newMap.end(); ++iter) {if (oldMap.find(iter->first) == oldMap.end()) {printf("send [%d:(%d,%d)]\t ENTER msg to obj [%d:(%d,%d)]\n",pEntity->id, pEntity->x, pEntity->y,iter->first, iter->second->x, iter->second->y);printf("send [%d:(%d,%d)]\t ENTER msg to obj [%d:(%d,%d)]\n",iter->first, iter->second->x, iter->second->y,pEntity->id, pEntity->x, pEntity->y);}} }// 獲取指定對象的AOI對象列表 void CScene::GetRangeSet(CEntity* pEntity, EntityMap* pEntityMap) {if (pEntity == NULL || pEntityMap == NULL){return;}// X鏈上的AOI范圍內(nèi)的對象，注意：并不是最終的AOI對象，因為還要檢測Y鏈上的位置是否在AOI范圍內(nèi)EntityMap x_map;EntityList::iterator iter;// X鏈上往后面遍歷iter = pEntity->x_pos;while(iter != m_listXEntity.end()){++iter;// 到了最后，跳出if (iter == m_listXEntity.end()) {break;}// 正向距離已經(jīng)超過半徑，跳出if ((*iter)->x - pEntity->x > pEntity->radius) {break;}// 添加進X方向的AOI集合x_map[(*iter)->id] = *iter;}// X鏈上往前面遍歷iter = pEntity->x_pos;while(iter != m_listXEntity.begin()){--iter;// 負向距離已經(jīng)超過半徑，跳出if (pEntity->x - (*iter)->x > pEntity->radius) {break;}// 添加進X方向的AOI集合x_map[(*iter)->id] = *iter;// 到了最前面，跳出，注意：不能放在加入AOI集合的前面，因為begin()位置也是有效對象if (iter == m_listXEntity.begin()) {break;}}// Y鏈上往后面遍歷iter = pEntity->y_pos;while(iter != m_listYEntity.end()){++iter;// 到了最后，跳出if (iter == m_listYEntity.end()) {break;}// 正向距離已經(jīng)超過半徑，跳出if ((*iter)->y - pEntity->y > pEntity->radius) {break;}// X方向AOI集合中存在的，則添加該對象到最終的AOI列表中if (x_map.find((*iter)->id) != x_map.end()) {(*pEntityMap)[(*iter)->id] = *iter;}}// Y鏈上往前面遍歷iter = pEntity->y_pos;while(iter != m_listYEntity.begin()){--iter;// 負向距離已經(jīng)超過半徑，跳出if (pEntity->y - (*iter)->y > pEntity->radius) {break;}// X方向AOI集合中存在的，則添加該對象到最終的AOI列表中if (x_map.find((*iter)->id) != x_map.end()) {(*pEntityMap)[(*iter)->id] = *iter;}// 到了最前面，跳出，注意：不能放在加入AOI集合的前面，因為begin()位置也是有效對象if (iter == m_listYEntity.begin()) {break;}} }// 刪除一個對象 void CScene::Leave(int id) {// 對象列表中是否存在該IDEntityMap::iterator iterEntity = m_mapEntity.find(id);if (iterEntity == m_mapEntity.end()) {return;}// 找到該對象CEntity* pEntity = iterEntity->second;// 獲取該對象的AOI列表EntityMap leaveMap;GetRangeSet(pEntity, &leaveMap);// 通知AOI列表中的每個對象，pEntity要離開了// 通知pEntity，你看不到AOI列表中的每個對象了for (EntityMap::iterator iter = leaveMap.begin(); iter != leaveMap.end(); ++iter) {printf("send [%d:(%d,%d)]\t LEAVE msg to obj [%d:(%d,%d)]\n",pEntity->id, pEntity->x, pEntity->y,iter->first, iter->second->x, iter->second->y);printf("send [%d:(%d,%d)]\t LEAVE msg to obj [%d:(%d,%d)]\n",iter->first, iter->second->x, iter->second->y,pEntity->id, pEntity->x, pEntity->y);}// X鏈，Y鏈上刪除m_listXEntity.erase(pEntity->x_pos);m_listYEntity.erase(pEntity->y_pos);// 對象列表中刪除m_mapEntity.erase(iterEntity);// 釋放對象delete pEntity; }

測試代碼test.cpp

#include <stdlib.h> #include <stdio.h> #include <time.h> #include "scene.h"int main() {// 新建一個場景CScene scene;printf("步驟一：添加5個對象\n");scene.Add(1,1,5); // 對象1，坐標（1,5）scene.Add(2,2,2); // 對象2，坐標（2,2）scene.Add(3,3,1); // 對象3，坐標（3,1）scene.Add(4,5,3); // 對象4，坐標（5,3）scene.Add(5,6,6); // 對象5，坐標（6,6）printf("步驟二：添加一個新的對象到坐標（3,3）\n");scene.Add(6,3,3); // 對象6，坐標（3,3）printf("步驟三：把對象3移動到坐標（4,4）\n");scene.Move(6,4,4);printf("步驟四：移除這6個對象\n");for (int i = 1; i <= 6; ++i) {scene.Leave(i);}system("pause");return 0; }

分析：

步驟一完成后結(jié)果如下：

步驟二完成后結(jié)果如下（紅色框表示AOI范圍）：

步驟三完成后結(jié)果如下（紅色框表示移動后的AOI范圍）：

筆者這里的結(jié)果打印如下：

總結(jié)

以上是生活随笔為你收集整理的AOI之十字链表法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。