導語： 本文提出一種利用無序數組、雙向鏈表、位元標記進行視野管理的演算法， 可以將每次增、刪、查視野列表的複雜度降為O(1)。
1. 視野管理的必要性
在大型多人線上遊戲MMO（Massively Multiplayer Online）中， 多個玩家在同一場景， 此時玩家需要能看到其附近的玩家， 同時不需要看到與其距離遠的玩家。 這就是視野管理需要做的事情：為每個玩家維護一個視野列表， 管理每個玩家可見視野內的其他玩家。
MMO遊戲中， 視野對伺服器造成的壓力主要來源於兩點：
一， 玩家頻繁移動造成視野列表的頻繁更新的壓力；
二， 廣播視野列表的頻寬壓力。
因為視野列表中的玩家頻繁變化， 有的玩家離開當前玩家的視野， 有的玩家新進入當前玩家的視野， 因此當前玩家的視野清單需要進行頻繁的增、刪、查操作， 因此增、刪、查操作的時間複雜度要盡可能的低， 從而緩解視野列表頻繁更新的壓力。 如果當前視野列表中有100個玩家， 每個玩家都移動了一段距離， 為了讓其他玩家看到自己的移動， 每個玩家都需要被通知其他99個玩家的移動， 這就需要廣播100*99個資料包， 隨著地圖中玩家數目增加， 造成廣播量急劇增加， 對頻寬造成極大壓力， 因此玩家的視野清單需要有規模限制， 從而緩解頻寬壓力。
本文提出一種利用無序數組、雙向鏈表、位元標記進行視野管理的演算法，
2. 視野管理演算法
2.1 九宮格
遊戲中地圖用來承載阻擋、靜態建築、NPC（非玩家控制角色：Non-Player-Controlled Character）、WRAP點等。 玩家在地圖上移動， 其可見的其他玩家即發生變化， 如果玩家的每次移動， 都更新視野列表， 時間成本太高， 因此只有當玩家離開某個區域時， 才更新視野清單， 而在這個區域內的移動， 並不更新視野列表。 為了劃分這個區域， 引入九宮格概念， 如圖1所示， 九個格子的總面積大於一個手機螢幕， 小於兩個手機螢幕。 大於一個手機螢幕的原因是， 可以預先計算當前螢幕外的一些玩家， 但又沒有必要預先計算太多的螢幕外玩家， 因此小於兩個手機螢幕， 玩家可見的範圍為以玩家為中心周圍九個格子內的其他玩家。
圖1 玩家從九宮格的格子5移動到格子8
2.2 視野管理的資料結構
視野管理共採用三個資料結構：無序數組、雙向鏈表、位元標記。 無序數組的增刪時間複雜度為O(1)；雙向鏈表可以在遍歷視野列表時避免遍歷整個無序數組；位元標記在判斷兩個玩家是否相互可見時時間複雜度為O(1)。
2.2.1 無序數組
視野管理的資料結構首先是採用無序數組：每個玩家有兩個陣列， 一個陣列A存儲其他玩家資訊的物件指標， 物件包含三個元素：其他玩家的指標、當前玩家在其他玩家視野陣列中的索引、其他玩家在當前玩家視野陣列中的索引， 第二個索引供雙向鏈表使用， A陣列某些元素可能空置；另一個陣列B輔助管理A陣列， 陣列元素是一個結構體， 成員變數為：標識變數、記錄A的空閒位置的變數， 陣列B的規模與陣列A規模大小相同。 其中， 陣列B的第i個元素中的標識變數表徵A陣列的第i個元素是否被分配。 另外， 設置兩個指標在B陣列上移動， 分為頭指標和尾指標， 用於維護、快速查找A陣列上空閒的位置， 如果分配空閒位置，
如果從Me的視野列表中刪除He， 首先查找He在Me的A陣列的索引， 單獨查找索引的演算法並非O(1)的演算法， 但批量查詢索引的演算法是O(1)的演算法， 詳情見下文：視野管理的流程。 通過索引可以直接查到該玩家He在Me的A陣列中存儲位置， 然後清空Me的A陣列中該玩家He資訊， 並將Me的B陣列對應的位置的分配標記置為空閒， B陣列的尾指標位置記錄新空閒位置， 尾指針右移；如果要加入一個玩家He， 通過Me的頭指標查詢到Me的B陣列中存儲的第一個空閒位置， 並檢查B陣列中該位置的分配標記， 如果分配標記為空閒， 即可將新入玩家He放到Me的A陣列中該位置， 並將Me的B陣列中該位置置為已分配， 頭指針右移。
假設視野清單大小為5，下面以表格的形式演示本文演算法，表格的前三行對應B陣列每個元素對應三元組（ArrayIndex,EmptyIndex,State），其中ArrayIndex是B陣列元素位置索引，EmptyIndex是A陣列中空閒的位置索引，State是A陣列中該位置是否被分配（只是為了校驗）：值為E表示A陣列該位置未被分配，可在該位置存儲新進入視野清單玩家；值為U表示該位置已分配，存儲了視野清單中的玩家。表格的第四行（Pointer）行，標記在B陣列遊走的兩個指針的遊走位置，Head：表示頭指針；Tail表示尾指針。下面展示B陣列在為A陣列分配和回收位置時的變化。
初始狀態如表1所示，初始狀態視野清單為空，即A陣列中不存儲任何可見玩家，B陣列中EmptyIndex記錄A陣列全部位置：0、1、2、3、4；B陣列中State全部為E，表示A陣列全部為空；B陣列中的兩個指標Pointer都指向第一個位置。
假設需要分配A陣列中三個空閒位置給進入視野列表玩家，此時遍歷Head指標和Tail指標中的位置，因為這兩個指標之間的位置存儲的都是空閒位置，每分配一個空閒位置，都將對應State標記為U，同時Head指標右移動，分配的位置為A陣列中的0、1、2。結果狀態如表2所示。
接著，假設刪除一個玩家（該玩家在A陣列中索引為2），則將Tail指針所指位置的EmptyIndex改為2，同時Tail指標右移，表示Head和Tail指標中的空閒位置多了2，將B陣列中位置2處的State改為E，表示A陣列中索引為2的位置空閒。狀態結果如表3所示。
然後，再分配A陣列中兩個空閒位置給新進入視野列表玩家，此時遍歷頭指標Head和Tail指標中的位置，將A陣列中位置為3、4分配給新玩家，將B陣列中3、4處的State改為U，Head移動到0處，狀態結果如表4所示。
最後，清空A陣列中所有玩家（4個玩家索引分別為0、1、3、4），將Tail指針所指位置1的EmptyIndex改為0,0位置處的State改為E，Tail指針右移，直到所有玩家清空，狀態結果如表5所示。
表1 初始狀態，視野清單為空
表2分配三個位置給進入視野清單玩家的結果狀態
表3刪除A陣列中位置為2的玩家的結果狀態
表4分配兩個位置給進入視野清單玩家的結果狀態
表5刪除A陣列中全部玩家後的結果狀態
2.2.2 雙向鏈表
採用無序數組的一個弊端是陣列中存在很多碎片，有些位置並沒有存儲玩家。這就導致遍歷玩家的視野清單時，需要把整個無序數組A全部遍歷一遍，極端情況下玩家的視野列表一個玩家都沒有，但也需要遍歷整個陣列。因此採用雙向鏈表輔助存儲，雙向鏈表中每個節點存儲的元素和無序數組A存儲的元素一樣，存儲其他玩家資訊的物件指標，物件包含三個元素：其他玩家的指標、當前玩家在其他玩家視野陣列中的索引、其他玩家在當前玩家視野陣列中的索引，但所有節點都是有效的，如果視野列表無其他玩家，則雙向鏈表為空。遍歷玩家的視野列表時，只需要遍歷雙向鏈表即可，不用遍歷整個無序數組。雙向鏈表增刪時間複雜度均為O(1)，將一個玩家加入無序數組A時，將其插入雙向鏈表尾部；將一個玩家從無序數組A刪除時，因為無序數組和雙向鏈表存儲的元素一樣，從無序數組中拿到存儲元素，將該元素從雙向鏈表刪除即可。
2.2.3 位元標記
遊戲中需要頻繁的判斷兩個玩家是否相互可見，然而採用無序數組+雙向鏈表的資料結構，最快只能採用遍歷雙向鏈表的方法，該時間複雜度為O(n)，因此採用第三個資料結構：位元標記輔助完成這項工作。每個場景中的Obj數量是有限的，我們遊戲每個場景的Obj數目最大為2048，ObjID編號從0到2047，每個玩家是否可見用一個bit表示。所以每個玩家共需要2047個bit表示是否與其他2047個Obj可見，即0.25M。假設He的ObjID為10，判斷Me是否可見He，只需要查看Me的第10個位標記是否為1即可。
2.3 視野管理的流程
如圖1所示，玩家Me從格子5移動到格子8，老視野可見的玩家為紅色和綠色格子內的玩家，新視野可見的玩家為紫色和綠色格子內的玩家。首先遍歷Me的雙向鏈表，對所有老視野列表的玩家打上標籤1，然後遍歷紫色和綠色格子內的玩家，如果玩家He已打標籤1，則將玩家He打上標籤2，說明玩家He在新視野和老視野都可見；如果玩家He沒打標籤1，則說明玩家He是新進視野的玩家，加入EnterList；重新遍歷Me的雙向鏈表，如果玩家He仍然是標籤1，說明玩家He只在老視野，沒在新視野中，加入LeaveList，同時記錄玩家He在玩家Me視野陣列中的索引。例如Me在格子5時老視野列表裡的玩家為：User1、User2、User3、User4、User5、User6；Me移動到格子8時，紫色和綠色格子內的玩家有User3、User4、User5、User6、User7、User8。首先對雙向鏈表User1到User6六個玩家打標籤1；然後對User3到User8打標籤，因為User3到User6已打標籤1，所以對這4個玩家打標籤2，而User7、User8沒打標籤1，所以這兩個玩家加入EnterList；再遍歷雙向鏈表User1、User2因為仍然是標籤1，所以將這兩個玩家加入LeaveList，同時記錄這兩個玩家在Me視野陣列中的索引Index1、Index2。
對LeaveList的兩個玩家User1、User2，首先根據User1的索引Index1從Me的視野陣列A中刪除，並將Me的B陣列對應的位置的分配標記置為空閒，B陣列的尾指標記錄新空閒位置Index1並右移；將Me雙向鏈表中User1對應的節點刪除；將位元標記User1對應的bit置為0。因為視野是相互的，根據Me的A陣列中記錄的Me在He的A陣列中的位置，將Me也從User1的視野列表中刪除。對User2採用同樣操作。
對EnterList中的玩家，需要按照優先順序高低放到不同的桶裡，比如隊友的優先順序比其他玩家優先順序高。然後按照優先順序高低的順序加入視野清單，如果視野列表已滿，優先順序高的玩家仍然沒進入視野清單，需要從視野清單中刪除優先順序低的玩家，以便騰出空間將優先順序高的玩家加入。對EnterList的兩個玩家User7、User8，通過Me的頭指針查詢到Me的B陣列中存儲的第一個空閒位置，並檢查B陣列中該位置的分配標記，如果分配標記為空閒，即可將新入玩家User7放到Me的A陣列中該位置，並將Me的B陣列中該位置置為已分配，頭指針右移；將User7對應的節點插入雙向鏈表尾部；將位元標記User7對應的bit置為1。因為視野是相互的，也需要將Me加入User7的視野列表。對User8採用同樣操作。
頭指針右移。假設視野清單大小為5，下面以表格的形式演示本文演算法，表格的前三行對應B陣列每個元素對應三元組（ArrayIndex,EmptyIndex,State），其中ArrayIndex是B陣列元素位置索引，EmptyIndex是A陣列中空閒的位置索引，State是A陣列中該位置是否被分配（只是為了校驗）：值為E表示A陣列該位置未被分配，可在該位置存儲新進入視野清單玩家；值為U表示該位置已分配，存儲了視野清單中的玩家。表格的第四行（Pointer）行，標記在B陣列遊走的兩個指針的遊走位置，Head：表示頭指針；Tail表示尾指針。下面展示B陣列在為A陣列分配和回收位置時的變化。
初始狀態如表1所示，初始狀態視野清單為空，即A陣列中不存儲任何可見玩家，B陣列中EmptyIndex記錄A陣列全部位置：0、1、2、3、4；B陣列中State全部為E，表示A陣列全部為空；B陣列中的兩個指標Pointer都指向第一個位置。
假設需要分配A陣列中三個空閒位置給進入視野列表玩家，此時遍歷Head指標和Tail指標中的位置，因為這兩個指標之間的位置存儲的都是空閒位置，每分配一個空閒位置，都將對應State標記為U，同時Head指標右移動，分配的位置為A陣列中的0、1、2。結果狀態如表2所示。
接著，假設刪除一個玩家（該玩家在A陣列中索引為2），則將Tail指針所指位置的EmptyIndex改為2，同時Tail指標右移，表示Head和Tail指標中的空閒位置多了2，將B陣列中位置2處的State改為E，表示A陣列中索引為2的位置空閒。狀態結果如表3所示。
然後，再分配A陣列中兩個空閒位置給新進入視野列表玩家，此時遍歷頭指標Head和Tail指標中的位置，將A陣列中位置為3、4分配給新玩家，將B陣列中3、4處的State改為U，Head移動到0處，狀態結果如表4所示。
最後，清空A陣列中所有玩家（4個玩家索引分別為0、1、3、4），將Tail指針所指位置1的EmptyIndex改為0,0位置處的State改為E，Tail指針右移，直到所有玩家清空，狀態結果如表5所示。
表1 初始狀態，視野清單為空
表2分配三個位置給進入視野清單玩家的結果狀態
表3刪除A陣列中位置為2的玩家的結果狀態
表4分配兩個位置給進入視野清單玩家的結果狀態
表5刪除A陣列中全部玩家後的結果狀態
2.2.2 雙向鏈表
採用無序數組的一個弊端是陣列中存在很多碎片，有些位置並沒有存儲玩家。這就導致遍歷玩家的視野清單時，需要把整個無序數組A全部遍歷一遍，極端情況下玩家的視野列表一個玩家都沒有，但也需要遍歷整個陣列。因此採用雙向鏈表輔助存儲，雙向鏈表中每個節點存儲的元素和無序數組A存儲的元素一樣，存儲其他玩家資訊的物件指標，物件包含三個元素：其他玩家的指標、當前玩家在其他玩家視野陣列中的索引、其他玩家在當前玩家視野陣列中的索引，但所有節點都是有效的，如果視野列表無其他玩家，則雙向鏈表為空。遍歷玩家的視野列表時，只需要遍歷雙向鏈表即可，不用遍歷整個無序數組。雙向鏈表增刪時間複雜度均為O(1)，將一個玩家加入無序數組A時，將其插入雙向鏈表尾部；將一個玩家從無序數組A刪除時，因為無序數組和雙向鏈表存儲的元素一樣，從無序數組中拿到存儲元素，將該元素從雙向鏈表刪除即可。
2.2.3 位元標記
遊戲中需要頻繁的判斷兩個玩家是否相互可見，然而採用無序數組+雙向鏈表的資料結構，最快只能採用遍歷雙向鏈表的方法，該時間複雜度為O(n)，因此採用第三個資料結構：位元標記輔助完成這項工作。每個場景中的Obj數量是有限的，我們遊戲每個場景的Obj數目最大為2048，ObjID編號從0到2047，每個玩家是否可見用一個bit表示。所以每個玩家共需要2047個bit表示是否與其他2047個Obj可見，即0.25M。假設He的ObjID為10，判斷Me是否可見He，只需要查看Me的第10個位標記是否為1即可。
2.3 視野管理的流程
如圖1所示，玩家Me從格子5移動到格子8，老視野可見的玩家為紅色和綠色格子內的玩家，新視野可見的玩家為紫色和綠色格子內的玩家。首先遍歷Me的雙向鏈表，對所有老視野列表的玩家打上標籤1，然後遍歷紫色和綠色格子內的玩家，如果玩家He已打標籤1，則將玩家He打上標籤2，說明玩家He在新視野和老視野都可見；如果玩家He沒打標籤1，則說明玩家He是新進視野的玩家，加入EnterList；重新遍歷Me的雙向鏈表，如果玩家He仍然是標籤1，說明玩家He只在老視野，沒在新視野中，加入LeaveList，同時記錄玩家He在玩家Me視野陣列中的索引。例如Me在格子5時老視野列表裡的玩家為：User1、User2、User3、User4、User5、User6；Me移動到格子8時，紫色和綠色格子內的玩家有User3、User4、User5、User6、User7、User8。首先對雙向鏈表User1到User6六個玩家打標籤1；然後對User3到User8打標籤，因為User3到User6已打標籤1，所以對這4個玩家打標籤2，而User7、User8沒打標籤1，所以這兩個玩家加入EnterList；再遍歷雙向鏈表User1、User2因為仍然是標籤1，所以將這兩個玩家加入LeaveList，同時記錄這兩個玩家在Me視野陣列中的索引Index1、Index2。
對LeaveList的兩個玩家User1、User2，首先根據User1的索引Index1從Me的視野陣列A中刪除，並將Me的B陣列對應的位置的分配標記置為空閒，B陣列的尾指標記錄新空閒位置Index1並右移；將Me雙向鏈表中User1對應的節點刪除；將位元標記User1對應的bit置為0。因為視野是相互的，根據Me的A陣列中記錄的Me在He的A陣列中的位置，將Me也從User1的視野列表中刪除。對User2採用同樣操作。
對EnterList中的玩家，需要按照優先順序高低放到不同的桶裡，比如隊友的優先順序比其他玩家優先順序高。然後按照優先順序高低的順序加入視野清單，如果視野列表已滿，優先順序高的玩家仍然沒進入視野清單，需要從視野清單中刪除優先順序低的玩家，以便騰出空間將優先順序高的玩家加入。對EnterList的兩個玩家User7、User8，通過Me的頭指針查詢到Me的B陣列中存儲的第一個空閒位置，並檢查B陣列中該位置的分配標記，如果分配標記為空閒，即可將新入玩家User7放到Me的A陣列中該位置，並將Me的B陣列中該位置置為已分配，頭指針右移；將User7對應的節點插入雙向鏈表尾部；將位元標記User7對應的bit置為1。因為視野是相互的，也需要將Me加入User7的視野列表。對User8採用同樣操作。