//依舊是一篇老文章，當年最後一屆“星貼獎”的獲獎徵文，是為數不多能搭的上機核氣質的文章。寫的有些枯燥晦澀，當時幾乎沒啥人看。值得注意的是，本文涉及一些技術發展和算法設計的內容，會有一點點（真的只有一點點）的專業性（硬核✗ 枯燥✓）的說教，請酌情食用。
前言
一些遊戲中所採用的部分技術其實脫胎自現實社會需求，而由遊戲引發的技術進步也可以反哺現實應用場景。
如今，伴隨著電動汽車產業的興起，自動駕駛成為新的技術熱點，然而複雜的城市街道，實時路況和突發事件無一不是考驗車載自動駕駛系統模型的重大課題。但是迴歸本質，自動駕駛技術實現卻離不開自動尋路功能，這是一個擁有較長髮展歷史的研究領域。
體現在遊戲中，尤其是擁有複雜世界地圖的RPG遊戲中，自動尋路也是方便玩家操作的常見功能。宏觀來看，無論是【逮蝦戶】的汽車自動駕駛；還是分揀包裹的機器人；亦或者在偌大地圖上指引玩家縱橫四海的遊戲指引，全都離不開這項簡單但實用的技術。本文以【自動尋路】的演化和應用作為展開，簡單闡述這項改變人類生活（至少改變了一丟丟）的技術。
自動尋路技術的演化歷史
（BT和庫伯之間的信賴超乎一般人機交互，遊戲設定中AI顯然更加“像人”）
在我的申訴郵件躺在客服系統中一個月之後，EA終於將我的賬戶解封，我終於可以和好友一起繼續在【Battlefield】中拉大栓了。但是在此之前，我又接觸到了由重生娛樂（Respawn Entertainment）製作的【泰坦隕落2】，在無法登錄聯機模式的一個多月裡，我把主線劇情玩了兩遍，甚至挑戰大師難度。體驗劇情期間我逐漸對遊戲中伴隨主角庫伯的泰坦BT-7274產生興趣，BT是位看似榆木腦袋實則富含人情味，可以“抄近路”掉坑或“協議三:保護鐵馭”的親密戰友。
可惜的是，現實中此類技術水平的輔助AI是不存在的，因為即使是為了完成【找條近路或者不堵的路】這一訴求，研究者們也已歷經十數載，付出無數的熬夜，頸椎病和掉頭髮…我首先對這個詞進行分解，【自動尋路】的母命題是【尋路 Wayfinding】，根據維基百科的介紹【2】，尋路指代：
人（動物）在物理空間上定位以及從一個地點去往另一個地點的所有導航方法的集和。
因此自動尋路是【導航 Navigation】功能的一種延申或者發展【3】，而導航則具體指代
：
監控載具從一個地點到另一個地點移動的過程。
然而廣域的歷史維度裡，導航技術的發展幾乎伴隨人類發展【4】，歷史上最早的導航法認為是波利尼西亞航海法（Polynesian Navigation【5】1761）。從遷徙到航海再到航天，從腓尼基到麥哲倫再到加加林，導航技術的不斷革新催生社會進步，這是在先驅者所汲汲的科學之力也是推動歷史車輪的駕轅之馬。
拋開長篇鉅製的【航海史】，當代自動尋路功能的實現是來自尋路算法（路徑探索 Pathfinding【6】），它的目的是用程序繪製兩個點之間最短的路徑，在這個研究領域中，絕大多數的研究成果都源自Dijkstra在加權圖上尋找最短路徑的算法。於是隆重登場——迪傑斯特拉算法（Dijkstra's algorithm 【7】），這是數據結構課本上最經典的算法之一，它由計算機科學家埃德斯格·迪傑斯特拉（Edsger W. Dijkstra 【8】）於1956年構思。在2001年接受《ACM通訊》雜誌採訪時，迪傑斯特拉回憶和分享了他當年構思該算法的故事：
從鹿特丹到格羅寧根的最短旅行線路是什麼？我大概花了二十分鐘去構思這個最短路徑問題。 那是一天早上，我和未婚妻在阿姆斯特丹購物，我們覺得累了於是便坐在咖啡館的露臺上喝杯咖啡，當時我只是疑慮自己是否能做到這一點，於是我設計出了這個最短路徑算法。正如我之前所說，這只是一個只用了二十分鐘的發明。
同樣的，貝爾實驗室的羅伯特·普里姆（Robert C. Prim）和同事約瑟夫·克魯斯卡爾（Joseph Kruskal）也開發了兩種不同的尋路算法【9】（即Prim算法（1957）和Kruskal算法（1956），但是Prim算法是迪傑斯特拉在解決“最大限度地減少連接機器後面板上引腳所需的電線量”這一問題時重新發現。）
（gif原文件丟了，只有jpg湊合~迪傑斯特拉算法的演示動畫）
除了迪傑斯特拉算法，各種更有趣的經典算法，比如弗洛伊德算法，Bellman-Ford算法，SPFA(Shortest Path Faster Algorithm)算法等也被陸續提出（覺得陌生不用擔心，因為它們最終出現在計算機系同學的期末試卷上）
在這篇文稿中，我不準備去介紹這些專業內覺得簡單，專業外覺得晦澀的知識，我們只要知道，在迪傑斯特拉算法提出之後，諸如A* algorithm，Sample algorithm等方法也被陸續提出，在這其中，A*算法是常見的在遊戲中使用的最短路徑算法，它的實質則是一個迪傑斯特拉算法的變體【10】。
回顧這些算法的發展，隨著遊戲產品的功能日漸豐富，各式算法也逐漸應用在這一產業領域，遊戲的AI尋路功能作為基礎需求也被提出。在1982年，克里斯·克勞福德（Chris Crawford【11】）回顧了他在遊戲【坦克（Tanktics: Computer Game of Armored Combat on the Eastern Front【12】 1976）】中為坦克設計尋路功能而煞費苦心，為此，我找到了1982年的Vol,2 Number 1期的《Computer Gaming World》雜誌，幸運的是，此雜誌的往期是開源的，我有幸回顧了關於遊戲【坦克（Tanktics）】和設計師克勞福德的專題報道。
我必須講明，【坦克】並未查證是世界上第一款擁有【尋路功能】的遊戲，我以他舉例是參考wiki詞條編輯者的觀點：這個遊戲以及遊戲設計者遇到的困難（尋路難）非常具有典型性。
為了解決尋路問題，克勞福德在【坦克】中不得不對遊戲地圖的山脈湖泊進行大量修改，刪除許多的地形結構以適應AI的行為邏輯（在電腦遊戲中，AI一方面需要對大地圖中行為路徑進行規劃，一方面又必須保證該算法較少的CPU資源和時間調用）
A*算法是一種啟發式算法，它的運行方法依賴於創建位置對應的節點， 這些節點同時也存儲這搜索的進度，但是顯而易見的是，這種方法僅僅適合在2D地圖的遊戲中進行路徑搜索，在圖形處理能力暴漲的當前，3D遊戲場景帶來的“空間（z軸）”使得A*算法需要處理的節點呈現指數增長【13】。經典算法亟待進化以適應新的需求。
//這部分的資料很難找，幸好我在CNKI上找到了一篇碩士論文【人工智能尋路算法在電子遊戲中的研究和應用】（該作者稱本篇論文的研究基礎源於GAMESTAR公司承包的Gauntlet（聖鎧傳說）【14】遊戲中的尋路算法），其中就有關於關於A*算法在遊戲中的優化，接下來我將簡要概括一下這些論文內容【15】。
因此，以地圖尺寸（宏觀的大地圖和微觀的小地圖）為衡量建立的分層尋路體系可以在兼顧硬件資源的前提下更好的實現AI角色尋路要求，該改進型算法在【帝國時代（Age of Empires）】【星際爭霸（StarCraft）】等RTS作品都有所體現。而在如Unity3D等遊戲引擎中，基於A*算法的WayPoint算法依舊是AI尋路功能實現的主要方法。
（這三部作品可以姑且算作RTS，MMORPG，（部分劣質的）網頁遊戲的代表，從中我們不難體會尋路功能和其算法在過去十數年中為無數玩家帶來的樂趣，回憶以及煩惱）
飽受爭議的遊戲功能
從上節中可以獲知，尋路功能最初是為了方便電腦AI擁有更好的性能，提升遊戲的遊戲性。但是隨著遊戲市場的規模擴大以及遊戲受眾的擴大，很多人對於遊戲中的自動尋路功能提出質疑和不滿。
有人指出，【自動尋路】功能會削弱玩家在遊戲中的操縱體驗，降低遊戲的遊玩樂趣。但是也有人堅持，自動尋路可以簡化遊戲操作，降低准入下限，從而提升玩家遊戲體驗。
然而，這個問題並不怪罪於尋路功能本身，自動尋路帶來的爭議源自遊戲 產品設計思路和遊戲玩家心理作用。準確的來說，它本質上卻是一個心理學/社會學問題。
（“風暴要火” ：MOBA或者說DOTA-LIKE遊戲脫胎自RTS遊戲，玩家操作單個角色進行多人合作競技，這類遊戲兼顧玩家的成就心和社交屬性）
首先自動尋路功能大多出現在大型多人在線網絡遊戲中，隨著產業發展，此類遊戲的世界地圖往往相當龐大，玩家在多個地點之間的移動往往會造成畫面卡頓，尋路效率低等問題，造成這些問題的原因在前文關於A*算法的講解中已經提到，無非是節點數量過多導致的資源佔用導致的。
為了解決這個問題，MMORPG遊戲往往採取以下幾種方法【16】，首先是地圖的動態加載。通過玩家的角色位置動態加載位置，並建立動態的索引表實時進行實時尋路，或者是建立評估函數，對路徑進行估算建立代價最低的通路。
從此角度看，自動尋路系統確實保障玩家提高效遊玩遊戲產品，避免了玩家因為在地圖中輾轉跑路所帶來的繁瑣重複操作，大量時間浪費以及對於遊戲體驗下降等弊端。
然而，不可以【拋開計量談毒性】。
難以否認的是，如今大量劣質遊戲充斥遊戲市場，它們最普遍的特徵就是幾乎完全自動化遊戲操作，玩家在遊玩時可能只需要寥寥點按幾下按鍵；充斥大量趨同且誇張的遊戲裝備系統和反饋機制（一刀999）；在部分手機遊戲中，玩家的遊玩中也包含了大量的自動操作內容，降低玩家的手控操作需求。凡此種種，以自動尋路功能為代表的自動化功能已經烙上游戲快餐化，劣質化的標籤。但是我認為：
忽視體驗的功能堆疊，對於產品遊戲性的無視，誘導用戶消費的急功近利才是導致遊戲產品劣質化的原因，而自動尋路等功能僅僅作為其比較突出的外部特徵，卻成為了被批評的眾矢之的。
（【鯤】吞的不是亙古巨獸，而是玩家的熱愛和感情。可惜的是，劣幣驅良幣的醜劇依舊在不斷上演）
介於端遊與手遊之間，輕量化Web網頁遊戲幾乎見證了遊戲市場的繁榮和畸變，以此為例（僅指代部分劣質網頁遊戲），我將從遊戲運營，玩家體驗兩方面介紹造成遊戲功能和遊戲體驗之間矛盾的咎因。
1.逐漸跑偏的遊戲運營
在2000年前後，“免費遊戲”機制代替“月卡”機制成為各種網絡遊戲的運營方式【17】，以此為分水嶺，玩家的遊戲門檻被大大降低，而玩家的點卡計時收費也轉變為購買道具（item billing），這種商業模式在極大提升遊戲營收的同時帶來了許多危及行業生態的隱患。這首先便是業界普遍存在的抄襲現象，這一現象最直觀體驗就是遊戲中的圖像（外向），背景（內在），可獨立部分（設計）等的同質化【18】，然而在規章約束有限的當下，這種不正之風依然司空見慣。
除此以外，諸如自動尋路等功能在遊戲中的保留目的是儘可能簡化遊戲操作流程，玩家的從遊戲中獲取的心理預期來自於簡單的數值比拼和虛擬社區中的聲望，加之交易體系和類似賭博的概率抽獎機制，此類遊戲的運營目的已經從以玩家體驗為中心向滿足玩家成就感（滿足心態）的轉變，其玩家在遊玩時的遊戲心態和情緒其實已經被刻意扭曲。
2.逐漸淡薄的遊戲體驗
正如部分玩家所批評的，自動尋路過度簡化遊戲內容，全自動化的流程淡薄了遊戲體驗，而數值化，功利化的社區環境（運營有意為之）還造成了遊戲的戾氣。遊戲社區是一個虛擬的社交平臺，根據社會網絡理論，親密性，互動時間，互動頻率和互惠互利是衡量社交關係強度的四個指標【19】，和諧的社交關係有助於玩家在虛擬和現實的人際中保持樂觀和積極的態度，反之，充滿競爭的社區中則會誕生交往障礙，人際疏離。（沒錯，有的人線上打的火熱，線下孤獨一人…比如我。即使沒有直觀的感受，但這也是遊戲開發者刻意營造或者蓄意引導的玩家感受。）
在遊戲中，玩家往往會追求成就感，這就形成了：
【遊戲等級（數值）】—>玩家之間的競爭（良性/惡性）—>成就感的遊戲體驗脈絡【20】。
遊戲機制中圍繞數值促成競爭，以成就感為目標價值的玩家往往會更樂意爭取額外獎勵（顯眼的形態，罕見物品或者稱號等），而這一切的代價就是急功近利的支出資金和精力（土豪也不例外的）。
這一章節內容與【自動尋路】功能似乎有些不搭界，實際上，聯繫前文所講述的算法更迭歷史，我想表達的是：
這是一個頗具“諷刺意味”的寓言故事： 尋路功能與算法最初是為了給遊戲帶來更棒的遊戲體驗，在五十幾年前，開發者們做到了，更聰明的電腦AI誕生，更高效低費的算法實現，於是玩法多樣，好玩有趣的遊戲不斷誕生。最終在發展頂峰，RTS（即時策略）遊戲裡，F2A，千軍萬馬也能井然有序的換家。
只是後來，大家忘記了這個功能的本意（初衷），在幾乎畸形的遊戲市場環境中，誕生了一堆以玩家成就感為誘導的，誘導氪金，惡性競爭為核心的遊戲產品。 可以說開發者抓住了玩家“人”的劣性，以社區生態為代價大肆收割利益，自動尋路作為遊戲操作自動化的基礎被他們大肆濫用，開發者全然不顧產品的遊戲性，設計感，”滾服“走過，素材拼湊又是整裝待發。 他們就像史矛革，眼裡只有黃金。
值得期待的應用前景
“算法永遠不會騙人”即使發展已有數十年，自動尋路功能依舊在現實生活中起到重要作用。
在此最值得介紹的就是導航技術和無人駕駛技術。但是它已不再是需要兼顧效費的經典算法，目前的尋路算法依託AI技術（Artificial Intelligence和前文的遊戲AI不同，這裡指一個廣泛的研究領域【21】，包含機器學習（Machine Learning）神經網絡（Neural Network）深度學習（Deep Learning）等領域）
隨著物聯網技術的發展，一些跨學科應用被不斷提出，其中，一個利用無人機（UAV）進行高空拍攝單幅全景圖像來評估AQI（空氣質量指數）的文章【22】就是其中典型，作者在研究中指出他們為無人機指定飛行路線時便採用了經典最短路算法的優化算法。這是我最近精讀的一篇文章，似乎與本文主題有點搭，於是拿出來稍稍講一下，噠噠噠~
（這是本文【AQ360: UAV-aided air quality monitoring by 360-degree aerial panoramic images in urban areas】的圖摘要）
（無人機尋路原理的示意圖，路徑上的權值決定了它的下一個目標區塊，最終達到最短路徑完成拍攝任務）
無人機的算法將目標區域劃分為一個個六邊形區塊，然後依據區塊內建築物的高低（因為高層建築會遮蔽拍攝視角）設計飛行路線，在電池耗能的前提下，保證拍攝的照片可以最大程度的囊括區域內所有場景，提升評估準確率。類似的應用還有很多，包括不僅限於“掃地機器人規劃房間清掃線路”和“戰鬥機器人規劃巡邏線路（這個真的有）
”但是這些看似智能的路徑規劃，其原理”只是“一種可以自學習的網絡結構，它來自於簡單的線性和非線性函數，通過權值和偏差值的變化對目標進行自適應以總結特徵規律，並封裝為模型路徑，成為可以適用在各種場景中的“算法模型”。在真實世界裡，它們幾乎可以應用在現實生活中的各種領域內，只是不像”BT“”查亞塔“或者”傀儡師“，由於模型不存在內在的邏輯性，這些”電子神經網絡“並不會產生奇特的”腦波“（更別提沒有足夠的存儲），所以並不會產生科幻電影中的”智械危機“”天網滅世“。
最後的最後，回到遊戲中，隨著【開放世界】成為越來越多開發商所熱衷的遊戲要素，自動尋路也在以不同的形象登場在各個遊戲世界中，但是作為一種最常見的遊戲功能，無論它的算法歷經多少次迭代，優化，編譯，封裝，調用，它依舊會忠實的履行自己的使命。
在【GTA5】中它是小地圖上標記紫色的通路，在【巫師3】裡它是不斷扭動的點線指引，在【輻射4】裡它是不怎麼好用的距離光標，在【無主之地3】中它是一個變化大小的菱形圖標...忘記現實，迷失在遊戲世界裡也是遊戲的一部分。
後記
由於我最近在寫一些學習上的東西，不自覺地，自己寫文的思路就會隨著平時看的文獻一起互相交織，於是原本侃侃而談的文字竟然也變得嚴肅起來。
這一次，我決心跳脫“介紹遊戲”的思路。我決定嘗試闡述遊戲功能的發展歷史，現狀以及前景，這是一次很有意思的嘗試，文中既有大量歷史背景的科普，同時也包含部分領域專業知識，甚至還有心理學的討論。同樣的，這篇文字也帶給我巨大的工作量，我需要查閱大量文獻，從中一點點整理有用的知識點和思想，CNKI和谷歌學術可以幫我寫遊戲雜談，SCI一區的核心頂刊被我引用拿來打豆豆，這是我最近的重大發現，跑。
//文字寫的倉促和粗糙，紕漏也所難免，希望我的文字能給大家有所幫助，啟發或者博君一笑也足夠了。
南大鳥
2021年5月19日 金城 大雨