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)

既然是鏈表，很自然地想到用線性表來(lái)實(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;      &nbs