大家好，又见面了，我是你们的朋友全栈君。
1. 简介
AOI主要有九宫格、灯塔和十字链表的算法实现。本文阐述十字链表的实现
2. 基本原理
若是二维地图，将地图内的对象按照坐标值，从小到大分在x轴和y轴两个链表上。如果是三维地图，则还需要维护多一个z轴的链表
3. 基本接口
Add：对象进入场景
Move：对象在场景内移动
Leave：对象离开场景
4. 代码如下，注释非常详尽
scene.h
#ifndef __CScene_H__
#define __CScene_H__
#include <map>
#include <list>
using namespace std;
// 注意：本示例的AOI范围指的是以对象为中心的正方形
// 地图内的对象
class CEntity
{
public:
int x; // X坐标
int y; // Y坐标
int id; // 对象的唯一ID
int 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()
{
// 删除场景内的所有对象
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)
{
// 已经存在该ID，直接返回
if (m_mapEntity.find(id) != m_mapEntity.end())
{
return;
}
// 新创建一个对象
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，他们进入了AOI
for (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;
// 往后面移动一个节点，作为搜索起始节点
++iter;
// 删除X链的旧节点
m_listXEntity.erase(pEntity->x_pos);
// 往后面遍历
while (iter != m_listXEntity.end())
{
// 找到第一个x值大于新坐标x指的节点
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;
// 往前面移动一个节点，作为搜索起始节点
--iter;
// 删除旧节点
m_listXEntity.erase(pEntity->x_pos);
// 往前面遍历
while (iter != m_listXEntity.begin())
{
// 找到第一个x值小于新坐标x指的节点
if ((*iter)->x < pEntity->x)
{
// 要指向该节点的下一个节点，因为iter是第一个比pEntity的x值小的，那么后面一个节点才是大于等于x值的，应该插在这个节点前面才对
++iter;
break;
}
--iter;
}
// X链新位置上插入，并记录位置
pEntity->x_pos = m_listXEntity.insert(iter, pEntity);
}
else
{
// 不需处理，因为已经是最前面了，x,y坐标改了就行
}
}
// 如果新坐标的y值比旧坐标的y值大，就往后面遍历
if (y > old_y)
{
if (pEntity->y_pos != m_listYEntity.end())
{
// 取得原y指针位置
iter = pEntity->y_pos;
// 往后面移动一个节点，作为搜索起始节点
++iter;
// 删除Y链的旧节点
m_listYEntity.erase(pEntity->y_pos);
// 往后面遍历
while (iter != m_listYEntity.end())
{
// 找到第一个y值大于新坐标y值的节点
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;
// 往前面移动一个节点，作为搜索起始节点
--iter;
// 删除Y链的旧节点
m_listYEntity.erase(pEntity->y_pos);
// 往前面遍历
while (iter != m_listYEntity.begin())
{
// 找到第一个y值小于新坐标y值的节点
if (pEntity->y - (*iter)->y > 0)
{
// 要指向该节点的下一个节点，因为iter是第一个比pEntity的y值小的，那么后面一个节点才是大于等于y值的，，应该插在这个节点前面才对
++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范围内的对象，注意：并不是最终的AOI对象，因为还要检测Y链上的位置是否在AOI范围内
EntityMap x_map;
EntityList::iterator iter;
// X链上往后面遍历
iter = pEntity->x_pos;
while(iter != m_listXEntity.end())
{
++iter;
// 到了最后，跳出
if (iter == m_listXEntity.end())
{
break;
}
// 正向距离已经超过半径，跳出
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;
// 负向距离已经超过半径，跳出
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;
}
// 正向距离已经超过半径，跳出
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;
// 负向距离已经超过半径，跳出
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)
{
// 对象列表中是否存在该ID
EntityMap::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;
}分析：
步骤一完成后结果如下：
步骤二完成后结果如下（红色框表示AOI范围）：
步骤三完成后结果如下（红色框表示移动后的AOI范围）：
笔者这里的结果打印如下：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/150316.html原文链接：https://javaforall.net
