[前言]時間過的好快去年的這時候都在趕專題，
而我在今年底也要開始去服兵役了，
最近公司做的專案也差不多做到一個進度點，
利用vue+webpack+cordova 開發前端，
總覺得目前做的專案很難讓自己程式功力有很大的提升，
於是在閒暇之餘開始在用LeetCode刷題，
目前已先刷通簡單題目為目標!
LeetCode 上面有很多程式題庫，聽說也有很多面試題目重裡面出來的，
有興趣的可以自行前往練習。
在我練習時開始看到連結串列(linked list)、二分法...各種資料結構，
雖然算法思路都還記得，但是實作都有點忘記了，
這樣刷一刷下來對我的幫助還是挺大的。
說到連結串列想提一下，當初我剛學這算法完，就去用C語言實作一個飛機遊戲，
這個是沒有使用任何框架，原生C語言寫的，
原理就是printf東西出來，在定時使用system("cls")，
把畫面上的東西清除，達到動畫的效果，
當時把所有的子彈，都是利用linked list的方式去儲存的，
現在想想覺得其實用普通陣列去儲存就可以了...
不過這樣也好那時在我寫完這個小遊戲後，
對指針的概念功力提升許多。
....題外話說遠了，其實在我當初最早提出的遊戲專題構想，
有三大遊戲模式，第一種模式就是口袋江湖那樣的玩法
第二種模式是戰場模式，第三種模式則是大地圖模式，
本來的構想是想要製作一款遊戲像"做騎馬與砍殺"的手機板，
玩家能在第一種遊玩模式，和村裡NPC交談，招兵買馬之類的，
然後可以隨時跳到第二種模式去帶兵打仗，如果打贏了，
就能在大地圖上一一的征服每一個城鎮，讓玩家享受征服天下的感覺。
所以我當時在製作第一種遊玩模式到一個階段後，就在開始研發第二種戰場模式，
不過也隨著負責美術的組員進度過慢，導致這些元素沒有出現在遊戲中，
不過這個戰場模式程式架構上來說 也算至少開發了35%左右，
而我今天就要來分享在我開發這個戰場模式時，所遇到的一些問題，以及最終解法。
[實際影片]
影片中的音效及動畫皆來自網路上，只用於學術研究。
[搜尋敵人思路]
剛好找到我一年前meeting畫的圖片。
紅色圈圈是玩家軍人，咖啡色圈圈是敵人軍人，
紅色箭頭是玩家軍人準備攻擊的目標，咖啡色箭頭是敵人軍人準備攻擊的目標，
一開始不會想太多，就用兩個for迴圈去尋找對面的每一個軍人位子，
去找哪一個敵人離我最近，我就去打他，這是我最一開始想到的思路，
以這張圖的"軍人陣型"來看不會有甚麼問題，最終兩軍交戰時，都會一字排開的互相廝殺。
但是當今天我軍人陣型改一下，如下圖所示
左邊是一開始軍人的陣型，隨著雙方慢慢靠近，尋找自己的目標廝殺，
因為是2D遊戲，所以會發現動畫會完全疊在一起，
原因在於，以我方的紅色的軍人來看，每一個離他們最近的咖啡色球，
都是最尖端的哪一個，所以當雙方軍人朝著自己目標靠近，最終就都疊在一起。
接著我又改良了一下算法
一樣的去尋找自己的目標，但是當找到自己的目標時，給目標身上的計數+1，
下一個人搜尋目標時，遇到目標上的計數為1了，那就跳過此軍人，尋找下一個目標。
用計數的好處是，如果我今天計數上限改成2，
戰場上就會出現兩人打一人的效果，以此類推。
上面效果看似不錯，但是就在雙方軍隊死傷差不多時，出現了一個奇怪問題....
假設搜尋計數都是以1為上限
戰場階段1:
紅A 和 咖啡A 對打，
紅B 和 咖啡B 對打，
紅C發呆。
戰場階段2:
紅A率先陣亡 咖啡A找到新目標紅C，
紅C也找到新目標咖啡A，
紅B 和 咖啡B 打得不分上下大戰三百回合。
戰場階段3:
紅B被咖啡B殺死了，
由於紅C與咖啡B的距離要比咖啡A近，
所以紅C轉移目標，準備去攻擊咖啡B，
由於紅C已經被咖啡A鎖定了，因此咖啡B無法鎖定紅C，
於是我們就會看到咖啡B原地發呆直到被紅C打死....
最終我的解法是當軍人被某一個敵人攻擊時，此時就不會管搜尋問題，
直接把攻擊目標轉向攻擊自己的人，一種誰打我，我就打回去的概念，
也就不會有原地等著被打死的狀況發生了。
[搜尋效率]
前面搜尋問題跑了幾次戰場，讓士兵打一打感覺效果不錯，
就在我把對戰人數加到100人對上100人時，開始出現嚴重掉禎現象，
前面提到我是用兩個for迴圈下去跑自然效率其差無比，fps平均只有10 fps...
我軍100人每一個人掃一下對面所有軍人100人的次數，
100*100=10000次
敵軍也掃10000次
效率真的低到不行。
於是我跑去找學校教授討論一下解法，教授給了我一個思路，就是把地圖切成格子。
在遊戲loading時，我先用兩個for迴圈去算出每一個士兵出生在哪一個格子裡面，
接著當士兵移動時，我只要判斷士兵走過哪條線，就讓士兵自己更新他的格子在哪，
這樣我就不用在額外算出士兵究竟在哪個格子中，
接著當士兵要搜索敵人時，我只需要搜尋自己格子附近的士兵就好，
大幅的減少搜尋時間，
紅色為我軍，指搜尋橘色畫起來的格子，
最終整個效果完成，就像實際影片那樣。
[結語]
演算法這種東西真的平常上課會聽到想睡覺，
但是當需要用到時，就會了解演算法真的很神奇。
創作內容
Cocos2d-x遊戲 100人VS 100人 戰場AI思路分享
Cocos2d-x (8)