AOI主要有九宮格、燈塔和十字鏈表的算法實(shí)現(xiàn)。本文闡述十字鏈表的實(shí)現(xiàn)和嘗試。
1. 基本原理
根據(jù)二維地圖，將其分成x軸和y軸兩個(gè)鏈表。如果是三維地圖，則還需要維護(hù)多一個(gè)z軸的鏈表。將對(duì)象的坐標(biāo)值按照大小相應(yīng)的排列在相應(yīng)的坐標(biāo)軸上面。
2. 基本接口
對(duì)對(duì)象的操作主要有以下三個(gè)接口：
- add：對(duì)象進(jìn)入地圖；
- leave：對(duì)象離開地圖；
- move：對(duì)象在地圖內(nèi)移動(dòng)。
2. 算法實(shí)現(xiàn)
既然是鏈表，很自然地想到用線性表來實(shí)現(xiàn)。因?yàn)榇嬖谙蚯昂拖蚝笳业那闆r，所以使用雙鏈表實(shí)現(xiàn)。其實(shí)實(shí)現(xiàn)也是非常簡(jiǎn)單，就是兩個(gè)雙鏈表（這里以二維地圖舉例）。那么我們的節(jié)點(diǎn)需要四個(gè)指針，分布為x軸的前后指針，y軸的前后指針。
// 雙鏈表（對(duì)象）
class DoubleNode
{
public:
DoubleNode(string key, int x, int y)
{
this->key = key;
this->x = x;
this->y = y;
xPrev = xNext = NULL;
};
DoubleNode * xPrev;
DoubleNode * xNext;
DoubleNode * yPrev;
DoubleNode * yNext;
string key; // 只是一個(gè)關(guān)鍵字
int x; // 位置（x坐標(biāo)）
int y; // 位置（y坐標(biāo)）
private:
};
下面是地圖場(chǎng)景信息和接口。這里的實(shí)現(xiàn)比較粗略，是帶頭尾的的雙鏈表，暫時(shí)不考慮空間占用的問題。類Scene有分別有一個(gè)頭尾指針，初始化的時(shí)候會(huì)為其賦值，主要用DoubleNode類的指針來存儲(chǔ)x軸和y軸的頭尾。初始化的時(shí)候，將_head的next指針指向尾_tail；將_tail的prev指針指向_head。
// 地圖/場(chǎng)景
class Scene
{
public:
Scene()
{
this->_head = new DoubleNode("[head]", 0, 0); // 帶頭尾的雙鏈表(可優(yōu)化去掉頭尾)
this->_tail = new DoubleNode("[tail]", 0, 0);
_head->xNext = _tail;
_head->yNext = _tail;
_tail->xPrev = _head;
_tail->yPrev = _head;
};
// 對(duì)象加入(新增)
DoubleNode * Add(string name, int x, int y);
// 對(duì)象離開(刪除)
void Leave(DoubleNode * node);
// 對(duì)象移動(dòng)
void Move(DoubleNode * node, int x, int y);
// 獲取范圍內(nèi)的AOI (參數(shù)為查找范圍)
void PrintAOI(DoubleNode * node, int xAreaLen, int yAreaLen);
private:
DoubleNode * _head;
DoubleNode * _tail;
};
2.1. add(進(jìn)入地圖)
將DoubleNode對(duì)象插入到十字鏈表中。x軸和y軸分別處理，處理方法基本一致。其實(shí)就是雙鏈表的數(shù)據(jù)插入操作，需要從頭開始遍歷線性表，對(duì)比相應(yīng)軸上的值的大小，插入到合適的位置。
void _add(DoubleNode * node)
{
// x軸處理
DoubleNode * cur = _head->xNext;
while(cur != NULL)
{
if((cur->x > node->x) || cur==_tail) // 插入數(shù)據(jù)
{
node->xNext = cur;
node->xPrev = cur->xPrev;
cur->xPrev->xNext = node;
cur->xPrev = node;
break;
}
cur = cur->xNext;
}
// y軸處理
cur = _head->yNext;
while(cur != NULL)
{
if((cur->y > node->y) || cur==_tail) // 插入數(shù)據(jù)
{
node->yNext = cur;
node->yPrev = cur->yPrev;
cur->yPrev->yNext = node;
cur->yPrev = node;
break;
}
cur = cur->yNext;
}
}
假設(shè)可視范圍為x軸2以內(nèi)，y軸2以內(nèi)，則運(yùn)行：
- 分別插入以下數(shù)據(jù)a(1,5)、f(6,6)、c(3,1)、b(2,2)、e(5,3)，然后插入d(3,3)，按照x軸和y軸打印其雙鏈表結(jié)果；
- 插入d(3,3)數(shù)據(jù)，求其可視AOI范圍（如圖，除了f(6,6)，其它對(duì)象都在d的可視范圍內(nèi)）。
控制臺(tái)結(jié)果（前8行）：
步驟1結(jié)果圖示：
步驟2結(jié)果圖示：
2.2. leave(離開地圖)和move(移動(dòng))
其實(shí)都是雙鏈表的基本操作，斷掉其相應(yīng)的指針就好了。按理，是需要
move和leave操作如圖，move是將d(3,3)移動(dòng)到(4,4)，然后再打印其AOI范圍。
控制臺(tái)結(jié)果：
移動(dòng)后AOI范圍圖示：
3. 完整代碼實(shí)例
// ConsoleApplication2.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include "stdafx.h"
#include "stdio.h"
#include <iostream>
#include <string>
using namespace std;
// 雙鏈表（對(duì)象）
class DoubleNode
{
public:
DoubleNode(string key, int x, int y)
{
this->key = key;
this->x = x;
this->y = y;
xPrev = xNext = NULL;
};
DoubleNode * xPrev;
DoubleNode * xNext;
DoubleNode * yPrev;
DoubleNode * yNext;
string key;
int x; // 位置（x坐標(biāo)）
int y; // 位置（y坐標(biāo)）
private:
};
// 地圖/場(chǎng)景
class Scene
{
public:
Scene()
{
this->_head = new DoubleNode("[head]", 0, 0); // 帶頭尾的雙鏈表(可優(yōu)化去掉頭尾)
this->_tail = new DoubleNode("[tail]", 0, 0);
_head->xNext = _tail;
_head->yNext = _tail;
_tail->xPrev = _head;
_tail->yPrev = _head;
};
// 對(duì)象加入(新增)
DoubleNode * Add(string name, int x, int y)
{
DoubleNode * node = new DoubleNode(name, x, y);
_add(node);
return node;
};
// 對(duì)象離開(刪除)
void Leave(DoubleNode * node)
{
node->xPrev->xNext = node->xNext;
node->xNext->xPrev = node->xPrev;
node->yPrev->yNext = node->yNext;
node->yNext->yPrev = node->yPrev;
node->xPrev = NULL;
node->xNext = NULL;
node->yPrev = NULL;
node->yNext = NULL;
};
// 對(duì)象移動(dòng)
void Move(DoubleNode * node, int x, int y)
{
Leave(node);
node->x = x;
node->y = y;
_add(node);
};
// 獲取范圍內(nèi)的AOI (參數(shù)為查找范圍)
void PrintAOI(DoubleNode * node, int xAreaLen, int yAreaLen)
{
cout << "Cur is: " << node->key << "（" << node->x << "," << node->y << ")" << endl;
cout << "Print AOI:" << endl;
// 往后找
DoubleNode * cur = node->xNext;
while (cur != _tail)
{
if ((cur->x - node->x) > xAreaLen)
{
break;
}
else
{
int inteval = 0;
inteval = node->y - cur->y;
if (inteval >= -yAreaLen && inteval <= yAreaLen)
{
cout << "\t" << cur->key << "(" << cur->x << "," << cur->y << ")" << endl;
}
}
cur = cur->xNext;
}
// 往前找
cur = node->xPrev;
while (cur != _head)
{
if ((node->x - cur->x) > xAreaLen)
{
break;
}
else
{
int inteval = 0;
inteval = node->y - cur->y;
if (inteval >= -yAreaLen && inteval <= yAreaLen)
{
cout << "\t" << cur->key << "(" << cur->x << "," << cur->y << ")" << endl;
}
}
cur = cur->xPrev;
}
};
// 調(diào)試代碼
void PrintLink() // 打印鏈表(從頭開始)
{
// 打印x軸鏈表
DoubleNode * cur = _head->xNext;
while (cur != _tail)
{
cout << (cur->key) << "(" << (cur->x) << "," << (cur->y) << ") -> ";
cur = cur->xNext;
}
cout << "end" << endl;
// 打印y軸鏈表
cur = _head->yNext;
while (cur != _tail)
{
cout << (cur->key) << "(" << (cur->x) << "," << (cur->y) << ") -> ";
cur = cur->yNext;
}
cout << "end" << endl;
};
private:
DoubleNode * _head;
DoubleNode * _tail;
void _add(DoubleNode * node)
{
// x軸處理
DoubleNode * cur = _head->xNext;
while (cur != NULL)
{
if ((cur->x > node->x) || cur == _tail) // 插入數(shù)據(jù)
{
node->xNext = cur;
node->xPrev = cur->xPrev;
cur->xPrev->xNext = node;
cur->xPrev = node;
break;
}
cur = cur->xNext;
}
// y軸處理
cur = _head->yNext;
while (cur != NULL)
{
if ((cur->y > node->y) || cur == _tail) // 插入數(shù)據(jù)
{
node->yNext = cur;
node->yPrev = cur->yPrev;
cur->yPrev->yNext = node;
cur->yPrev = node;
break;
}
cur = cur->yNext;
}
}
};
// --------------------------------------------
int _tmain(int argc, _TCHAR* argv[])
{
Scene scene = Scene();
// 增加
scene.Add("a", 1, 5);
scene.Add("f", 6, 6);
scene.Add("c", 3, 1);
scene.Add("b", 2, 2);
scene.Add("e", 5, 3);
DoubleNode * node = scene.Add("d", 3, 3);
scene.PrintLink();
scene.PrintAOI(node, 2, 2);
// 移動(dòng)
cout << endl << "[MOVE]" << endl;
scene.Move(node, 4, 4);
scene.PrintLink();
scene.PrintAOI(node, 2, 2);
// 刪除
cout << endl << "[LEAVE]" << endl;
scene.Leave(node);
scene.PrintLink();
}
算法的大概思想如下.每個(gè)場(chǎng)景維護(hù)兩個(gè)鏈表,分別為X軸和Y軸的坐標(biāo)按序排列好的鏈表,也就是比如在X軸鏈表上,越在前的對(duì)象,X坐標(biāo)越小,Y軸鏈表同理.這樣,每次需要更新狀態(tài)的時(shí)候,只需要在這個(gè)鏈表上向前或者向后遍歷結(jié)點(diǎn)就知道該通知誰了.
這里假設(shè)有三個(gè)API:Add(向場(chǎng)景中添加一個(gè)對(duì)象),Leave(某對(duì)象離開場(chǎng)景),Move(某對(duì)象在場(chǎng)景中移動(dòng)).
來一個(gè)一個(gè)看.
Add:根據(jù)新增對(duì)象的X,Y坐標(biāo),依次遍歷X,Y軸坐標(biāo)鏈表,這里有兩個(gè)目的,一個(gè)是獲得這個(gè)新增對(duì)象的坐標(biāo)在X,Y軸坐標(biāo)的位置,另一方面獲得該通知哪些結(jié)點(diǎn).通知的范圍,每個(gè)對(duì)象可以自己定制自己的通知范圍.但是為了簡(jiǎn)單起見,在這里我們假設(shè)每個(gè)結(jié)點(diǎn)X,Y坐標(biāo)相差1,而通知的范圍是2.比如原有的X軸坐標(biāo)為:
a->b->c->d->e->f->g->h
假設(shè)新增一個(gè)對(duì)象z,它最終所在的位置是c和d之間,根據(jù)前面的假設(shè),它只需要通知b,c,e,f四個(gè)結(jié)點(diǎn)就好了.所以,新增一個(gè)結(jié)點(diǎn)的時(shí)候,并不需要遍歷完鏈表的.
但是這里還需要注意的是,一個(gè)結(jié)點(diǎn),必須X,Y坐標(biāo)同時(shí)都在通知范圍內(nèi)才可以進(jìn)入通知集合.
Leave:在添加了對(duì)象之后,對(duì)象身上掛了兩個(gè)結(jié)點(diǎn),分別存放在X,Y軸坐標(biāo)鏈表上的位置,那么在這個(gè)對(duì)象要離開場(chǎng)景時(shí),也只需要向前向后探索一定的范圍,就可以得到需要通知該對(duì)象要離開的集合了.
Move:移動(dòng)操作比較麻煩,但是也可以比較漂亮的解決.在更新位置之前,同樣根據(jù)前面的算法得到要通知的結(jié)點(diǎn)集合,稱為old_set;更新位置之后,再獲取另一個(gè)通知集合,稱為new_set;然后,old_set和new_set的交集,稱為move_set,在此集合中的結(jié)點(diǎn),在移動(dòng)前后都在通知范圍,因此要向這個(gè)集合的結(jié)點(diǎn)發(fā)送該對(duì)象移動(dòng)的消息;而old_set-move_set的集合,在移動(dòng)之后已經(jīng)離開了視野,因此要向它們發(fā)送該對(duì)象離開的消息;最后,new_set-move_set是移動(dòng)之后才看見該結(jié)點(diǎn)的結(jié)點(diǎn)集合,這個(gè)集合的結(jié)點(diǎn),要發(fā)送該結(jié)點(diǎn)進(jìn)入場(chǎng)景的消息.