2D的俯視圖經常用于從給定點計算可視區域。例如，你可能想把某些東西隱藏在玩家看不見的地方，亦或你想知道點燃火炬后能看見什么地方。
?

拖動圓點轉一圈，看看玩家都能看到些什么：

這個算法也能計算出給定光源所照亮的區域。對每條光線，我們可以構建出被照亮區域的光線圖。如果我們給上面的迷宮放上24個燈呢？見光線圖。

roguelike（譯注：類地下城RPG游戲統稱）社區已經收集了好幾種算法，尤其是網格類的。消減算法是從可見的一切區域開始，減去不可見區域；添加算法是從不可見區域開始，加上可見區域。我將描述一種可工作于線段的添加算法，不僅僅是固體分塊或者網格。

光線投射

一個簡單地方法是從中心點投射光線，這是得到一個近似解的合理的第一步：
?

更聰明的是，讓光線投射到所有墻體的開端和末端。這些光線所產生的三角形就是可見區域：
?

就是這樣！該算法如下：

計算到墻體開始或結束的角度。

從中心點沿各個角度投出光線。

對這些光線所產生的三角形進行填充。

墻體跟蹤

我們可以到此為止了，尤其是如果我們有一個快速光線投射算法，可使用空間哈希以避免與每一個墻體進行相交計算。然而，更有效的方法是將光線投射和墻體相交結合成一個算法。我將在這里描述了一種圓形掃描算法，對所有的擊中點按角度進行排序; 它也可以擴展成圓形外擴算法，對所有的擊中點按半徑排序，但我還沒有嘗試過這種方法。

位于連續幾個射線之間的區域，我們需要找到最近的墻。這面墻就被照亮了; 所有其他墻面應該被隱藏。我們的策略是360°掃描，處理所有的墻端點。當運行時，我們會持續跟蹤與掃描線相交的墻壁。點擊觀看端點掃描：
?

下一步驟是將跟蹤哪些墻壁會被掃描線穿過。只有最近的壁是可見的。你如何找出哪些墻壁是最近的？最簡單的方法是計算從中心到墻的距離。然而，如果墻壁大小不同，這種方法不能很好地工作，所以演示中使用一個稍微復雜的方法，這里我就不解釋了。

按PLAY可看到掃描中最近的墻面以白色繪制和其他墻面繪成黑色。
?

每當最近的墻面終止，或者有新的墻面比其它的都近時，我們創建了一個三角形表示可見區域。這些三角形的并集就是所述中心點的可視區域。

０００００
需要注意的是創建一個三角形涉及到之前與掃描線相交的墻面。其結果是，三角形的新邊緣可能長于或短于掃描線，并且該三角形最遠的邊緣比之前的墻面短。

試驗場

這里有一塊試驗場，有很多可用的方塊。可以拖拽方塊到網格內。點擊play/pause按鈕可以查看算法運行，或者移動中心點查看哪些是可見的，就像玩家四處查看一樣。
?

組合輸出

我們可以使用集合運算以有趣的方式組合該算法的輸出。手機號拍賣平臺這些也可被實現為用布爾運算分析輸出，或者用位圖操作渲染輸出。

玩家視野

限制玩家的視野最簡單的操作是將輸出與有限的視野求交集。例如，相交算法使用圓圈來限制可見半徑。與漸變填充圈相交，可使光按距離改變明暗。與圓錐相交可打造出“手電筒”效果，可以讓你把前面看得更遠，但沒有相應視野在你身后（見隨后Dynamite Jack的一個例子）。假如用雙眼代替單點，玩家的視野也更好看。我希望你可以合并所有眼睛的可視區域，但我還沒有試過。

地圖物體

可見性也可用于計算哪些區域被火炬點亮。在頁面的頂部演示了首先對每個火炬所點亮的區域進行求并集，然后與玩家可以看見的區域相交。（請注意，此算法會產生硬陰影，你將不得不對輸出進行后處理來獲得軟陰影。）

同樣的計算可用于確定哪些地區可被安全攝像頭可以看到，有哪些被盾牌保護著，或者是否足夠靠近某些魔法設施，使它賦予你屬性加成或是詛咒。

AI行為

可見性也可用于構建AI行為。例如，假設敵人的AI是想扔了一枚手榴彈擊中玩家，也想站在玩家射擊不到的地方。手榴彈需要足夠近才能擊中玩家，并且無法擊中障礙物后面的。下圖顯示標注了AI單位的地圖的可能計算：
?

手榴彈扔進紫色區域將成功擊中一名玩家。黃色和紫色區域是危險區域; 玩家可以從那里攻擊AI單位。AI需要站在一個安全的區域（深藍色）并且投擲了一枚手榴彈到紫色區域，然后尋找掩體。如何計算掩體？在AI準備投擲手雷的地方再次運行可見性算法，讓櫥柜和桌子擋住視線。

實現

我已經用HAXE 3來實現這個算法，使用Apache v2開源協議（類似MIT和BSD，它可以在商業項目中使用）。HAXE代碼可以編譯成JavaScript，ActionScript，C ++，Java，C#或PHP。我把它編譯成JavaScript來制作這個網頁，并為我的其他項目編譯成Flash。我編譯成以下語言：
?

• Actionscript；可讀，因為Actionscript和Haxe并非截然不同
• Javascript（用于此頁面上的演示）；大多是可讀的。
• Java ；輕度可讀，但不是很好。
• C# ；輕度可讀，但不是很好。Roy Triesscheijn有一個更好的版本在這里。

Wade Tritschler建議手工移植，所產生的代碼要比使用Haxe輸出的代碼更干凈。我同意這個觀點。如果你手寫代碼還可以更好得了解該算法。盡管該算法主要在CPU中進行，可以使用GPU為位圖進行三角形渲染和合并位圖輸出。（布爾AND操作可變成位圖乘法;布爾OR操作可變成位圖添加和鉗位。）在我的項目中該性能已經足夠，所以我還沒有構建GPU版本。如果你的游戲有CPU限制，可以考慮使用消減算法（而不是這里顯示的添加算法），渲染四邊形的每條線段的影子。它會增加GPU渲染負載，但它并不需要在CPU上排序。如果填充率是一個問題，考慮渲染一個比游戲畫面分辨率低的光度圖，然后擴大它。

相關內容

視覺和光線覆蓋了可見性的問題; 在我的博客文章有更多的鏈接。地平線問題類似2D可見性問題，但它在直角坐標系中，而不是極坐標。另外還有美術館問題，關于放置多少個警衛就可以看到地圖的每一個區域。我正Trello上創建了一份列表，未來可能更新這個頁面。

總結

以上是生活随笔為你收集整理的技术分享：游戏中的 2D 可见性的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。