AOI主要有九宮格、燈塔和十字鏈表的算法實現(xiàn)。本文闡述十字鏈表的實現(xiàn)和嘗試。
1. 基本原理
根據(jù)二維地圖，將其分成x軸和y軸兩個鏈表。如果是三維地圖，則還需要維護多一個z軸的鏈表。將對象的坐標值按照大小相應的排列在相應的坐標軸上面。
2. 基本接口
對對象的操作主要有以下三個接口：
add：對象進入地圖；
leave：對象離開地圖；
move：對象在地圖內(nèi)移動。
2. 算法實現(xiàn)
既然是鏈表，很自然地想到用線性表來實現(xiàn)。因為存在向前和向后找的情況，所以使用雙鏈表實現(xiàn)。其實實現(xiàn)也是非常簡單，就是兩個雙鏈表（這里以二維地圖舉例）。那么我們的節(jié)點需要四個指針，分布為x軸的前后指針，y軸的前后指針。
// 雙鏈表（對象）class DoubleNode
{public:
DoubleNode(string key, int x, int y)
{ this->key = key; &nbs
