1. 全栈程序员必看首页

AOI之十字链表法

全栈程序员-用户IM • • 未分类

AOI之十字链表法1.简介AOI主要有九宫格、灯塔和十字链表的算法实现。本文阐述十字链表的实现2. 基本原理若是二维地图，将地图内的对象按照坐标值，从小到大分在x轴和y轴两个链表上。如果是三维地图，则还需要维护多一个z轴的链表3.基本接口 Add：对象进入场景Move：对象在场景内移动Leave：对象离开场景4.代码如下scene.h#ifndef__CScene_H__#define__CScene_…

大家好，又见面了，我是你们的朋友全栈君。

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范围）：

AOI之十字链表法

步骤三完成后结果如下（红色框表示移动后的AOI范围）：

AOI之十字链表法

笔者这里的结果打印如下：

AOI之十字链表法

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/150316.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号