Roguelike游戏的视野算法
簡介
實現(xiàn)Roguelike的一項任務(wù)是弄清楚如何計算玩家或怪物的可見區(qū)域。現(xiàn)有的算法很多，但是都存在缺陷，因此我著手開發(fā)一種新的算法，該算法對我來說是快速，準(zhǔn)確和美觀的。盡管我沒有創(chuàng)建理想的算法，但我仍然認(rèn)為我的算法是對其他算法的改進(jìn)。
可見區(qū)域（視野/ field of view / FOV），判斷單位是否可以看到地形的某個部分。這里假設(shè)地牢是很常見的基于tiles的類型。玩家是否可以“看到tile”（視線/ line of sight / LOS）有時與玩家是否可以“看到tile中的怪物”有所不同，也不同于他是否可以使用遠(yuǎn)程武器或咒語”瞄準(zhǔn)該怪物“（瞄準(zhǔn)線/ line of targeting / LOT）。
理想的算法屬性
接下來首先描述視野算法一些常見而有用的特征，然后說明為什么大多數(shù)現(xiàn)有算法缺少這些特征中的一個或多個。
?
- 對稱性（Symmetry）： 如果站在tile A上可以看到tile B，那么站在tile B上就應(yīng)該能夠看到tile A。而且視野不對稱通常會導(dǎo)致戰(zhàn)術(shù)性和公平性變差（當(dāng)LOS與LOT相同）。當(dāng)然如果游戲是刻意造成不對稱的話是例外。
- 墻壁擴(kuò)展（Expansive Walls）：站在沒有凹陷的大房間時，你可以看到房間里所有的墻；而站在長走廊時，您可以看到走廊兩側(cè)所有的墻。盡管它很少影響游戲玩法，但如果算法不具有此屬性，看起來就會很丑，并且會使探索變得乏味。
- 擴(kuò)大柱子陰影： 當(dāng)視線被柱子遮擋時，柱子應(yīng)以扇形投射陰影。這通常可以提供更具戰(zhàn)術(shù)性的玩法：更容易隱藏，伏擊和逃脫。但是許多roguelike根本沒有柱子，這個屬性就跟他們沒啥關(guān)系了。
- 沒有盲角： 在拐角處可以在看到至少兩個tile。因此，如果沿拐角對角移動，你就不會發(fā)現(xiàn)自己旁邊突然出現(xiàn)之前看不見的怪物。這也意味著可以在進(jìn)入大廳之前看到兩側(cè)至少兩個tile。大多數(shù)情況下這都是可取的，如果玩家走過每個角落都必須小心翼翼就有些乏味了。一些算法允許拐角處可以看到無限遠(yuǎn)，也算保護(hù)玩家免受遠(yuǎn)程武器的傷害。
- 沒有偽影（Artifacts）： 盡管對于視野算法而言什么是“正確”有討論空間，但是算法至少應(yīng)該做到本份。意思是算法應(yīng)該定義如同現(xiàn)實世界的幾何圖形并準(zhǔn)確地模擬光傳播。偽影的意思是有些算法根本不符合現(xiàn)實世界的幾何體，是使用近似而非精確的數(shù)學(xué)來實現(xiàn)的，并且存在bug。
- 效率： 算法不應(yīng)該花費(fèi)很長時間，并且最好避免重復(fù)測試同一個tile。
現(xiàn)有算法
不算詳盡，涵蓋了最常用的算法。
光線投射（Ray casting）
優(yōu)點： 簡單。相當(dāng)快。擴(kuò)大柱子陰影。良好的光影平衡。沒有盲角。
缺點：?不對稱。沒有墻壁擴(kuò)展。間隙很多（可見性不連續(xù)）。
這算法會將光線從玩家投射到地圖邊緣上的每個點（或視野半徑邊緣的每個點）。光線用簡單的畫線算法投射（如Bresenham'的算法[0]），一碰到墻就會停止。光線投射是最簡單而且速度很快的算法，但是有許多問題。
?
- 不對稱。 Bresenham的算法是不對稱的，但是即使你用對稱的畫線算法，結(jié)果還是不對稱，因為在替換位置時線條的端點不會簡單地反轉(zhuǎn)。
- 在可見點和陰影上也都存在間隙，并且很古怪。后期處理可以修復(fù)間隙，可以消除難看的偽影，但會減慢速度，并且無法解決其他問題。
- 會多次重復(fù)測試tile，效率有些低下，但是由于簡單性，最終還是非?？?#xff0c;尤其是在較小的視線范圍。
光線投射以最快的算法聞名，但是這主要是由于較復(fù)雜的算法普遍實現(xiàn)的較差。實現(xiàn)良好的陰影投射算法永遠(yuǎn)比光線投射更勝一籌。但如果撇開間隙和不對稱，僅考慮光線和陰影的形狀，我認(rèn)為光線投射比陰影投射和菱形墻等更復(fù)雜的算法產(chǎn)生更好的結(jié)果。而且，隨著視線半徑的減小，大多數(shù)問題都變得沒那么嚴(yán)重了；如果圓形視線半徑為4或更小，它其實可以很好地工作，不需要進(jìn)行后期處理（盡管還是有些一些偽影）。
?
陰影投射（點對tile或點對點）（ Shadow casting）
優(yōu)點：快。擴(kuò)大柱子陰影。墻壁擴(kuò)展。連續(xù)的可見性。
缺點：對角線視野比平常窄得多。盲角。光束通過門擴(kuò)展得太多。不對稱。消除偽影的方法復(fù)雜（nontrivial）。
陰影投射是從玩家向外投射扇形光線的技術(shù)。當(dāng)一個扇區(qū)碰到墻時，該扇區(qū)可能會減小角度或分成兩個扇區(qū)，然后分別進(jìn)行處理。實現(xiàn)方式各不相同，但是好的實現(xiàn)只會訪問每個tile一次或接近一次，并且每個tile僅進(jìn)行少量且大致恒定的工作。如果實現(xiàn)得當(dāng)，陰影投射會成為最快的算法之一；但在實現(xiàn)不佳的情況下，它在走廊拐角和具有許多小障礙物的開放區(qū)域中的速度可能較慢。 “陰影投射”有點用詞不當(dāng)，因為實際投射的是光，但我還是會用這詞，因為“Light casting”跟“Ray casting”有些像。在我見過的所有case，陰影投射都使用正方形的tile，但是其他形狀也是可能的。
在通常的實現(xiàn)中游戲賬號拍賣，如果從玩家的tile中心到目標(biāo)tile的任何部分之間都存在一條暢通的線條，則tile為可見。這是一個示例，說明陰影投射如何針對單個八分圓扇形進(jìn)行工作。 （并非所有實現(xiàn)都可以在八分圓中工作）
上面就是不對稱性會減弱戰(zhàn)術(shù)性的一個原因。如果可以瞄準(zhǔn)看到的東西（LOS==LOT），那么走廊中間會比拐角具有優(yōu)勢，盡管拐角看上去更隱蔽。拐角的單位可以在不見攻擊者的情況下被射殺。像這樣的不對等就是對稱性是一種理想特性的原因。但是，如果上述不對稱性被逆轉(zhuǎn)，則實際上它可能是優(yōu)于對稱算法：可以使拐角真的更加隱蔽，使游戲更具戰(zhàn)術(shù)性（更佳的可能是LOS對稱，而LOT不對稱）。有一種稱為“反向陰影投射”的算法可以逆轉(zhuǎn)不對稱性，但通?？雌饋砀畈⑶疫\(yùn)行更慢。
不過，對陰影投射代碼進(jìn)行小的修改就足以使其對稱。這是通過更改算法來實現(xiàn)的，因此只有在從玩家的tile中心到目標(biāo)tile中心（而不是目標(biāo)tile的任何部分）有一條暢通無阻的線條時，它才判定tile可見。如下所示，這可以解決一些問題但會導(dǎo)致其他問題。
?
【key point is the strategy of how to determine a tile is visible: just need the sector cover the tile? or need to cover the center point? or cover a certain percentage of area? 發(fā)射點固定了在格子中央，但是被觀察的一方則是視線稍為蹭到格子都算看見，因此不對稱】
菱形墻（Diamond walls）（點對tile或點對點）
優(yōu)點：相當(dāng)快。擴(kuò)大支柱陰影。墻壁擴(kuò)展。沒有盲角?？梢娦曰具B續(xù)。
缺點：光束通過門會擴(kuò)展太多。不對稱；小更改即可解決，但相對會丟失墻壁擴(kuò)展并導(dǎo)致不連續(xù)
就像陰影投射一樣，如果從玩家tile的中心到目標(biāo)tile的任何部分都存在一條暢通無阻的線條，則tile為可見，但是它會將墻視為菱形。這比標(biāo)準(zhǔn)陰影投射有更大的拐角可視距離空間，更好地窺視各個角落。但它本身會帶來一些問題，主要是有點過于寬容，使太多的tile可見，盡管如此，這似乎也是對標(biāo)準(zhǔn)陰影投射的一種改進(jìn)。 （我稍為修改陰影投射代碼來實現(xiàn)）至于效率，它比普通陰影投射要慢一些，因為它需要為每個tile做更多的工作，但是仍然相當(dāng)快。
將墻視為菱形實際上在roguelikes中很有用。原因是大多數(shù)roguelikes允許單位在對角相鄰的墻之間移動，如果墻是正方形的，它們的角就會碰觸，沒有空間。如下圖所示。使游戲的物理學(xué)更加一致【指可移動范圍與可視范圍有一致性？ 】。菱形墻還可以使拐角處的視野更好，通常是好事。
?
不幸的是，菱形墻存在理論上的問題。與菱形成切線視之為不相交；零寬度的光束仍然能照亮tile。這樣可以在拐角處提供更好的視野，但在以下情況下使單位可以透視墻壁。應(yīng)該要在特殊情況下禁止透視墻壁，但會造成游戲物理在某些情況下不一致。
?
半寬墻（Half-width walls）
優(yōu)缺點： 與菱形墻相同，但更寬容，但速度稍慢。
另一個類似于菱形墻的想法，分別是它使用的墻是通常寬度的一半。它也解決了在對角tile之間的視野問題，但在我看來過于寬容，感覺比菱形墻更差。由于并非每個墻都是相同形狀，因此實施速度也稍慢。 （形狀取決于是否有相鄰的墻要連接。）我姑且實現(xiàn)了這算法，但實在不值得花這氣力。
寬容的FOV（Permissive field of view）（tile to tile）
優(yōu)點： 對稱。沒有盲角。墻壁擴(kuò)展。連續(xù)可見性。
缺點： 慢。沒有擴(kuò)大的支柱陰影。拐角處的可見性可能過多。
如果從玩家tile的任何部分到目標(biāo)tile的任何部分之間都存在一條暢通無阻的線條，則視tile為可見。此方法的大多數(shù)實現(xiàn)都是估算，例如僅對對角進(jìn)行相互測試【并不是任何部分，而是只有目標(biāo)和自己的四個邊角點】，在某些情況下會失敗。精準(zhǔn)的實現(xiàn)可以適應(yīng)所有情況，但是慢。我提供了一個精確的實現(xiàn)（改編自Jonathon Duerig[1]）。該算法的主要特征是對稱，并且在拐角可以看很遠(yuǎn)，但對我而言有些太寬容了，所以我沒有很努力優(yōu)化這算法。可以說如果所有生物的視線半徑都較短，那這算法感覺上和實際上都會更好。
有一個這算法的版本，可以在運(yùn)行時更改寬容度（permissivity）。我玩了一下，把通常寬容度減半看上去很不錯，但就不再對稱了，而且我想有個更快的算法anyway。
?
Digital FOV（菱到菱）
優(yōu)點和缺點： 與寬容FOV算法相同。
Digital FOV將每個tile都視為菱形，并且如果從玩家菱形的任何部分到目標(biāo)菱形的任何部分都存在一條暢通的線條，則認(rèn)為該tile可見。結(jié)果，它甚至比允寬容FOV稍微寬容一些（因為墻壁的障礙性更小） 。在其他方面所有相同的特征和缺點一樣，但更慢。這個想法是基于的相當(dāng)笨拙的digital straight line segments概念，我沒有費(fèi)心實現(xiàn)這個。 One interesting feature of the algorithm is that the knowledge of the digital line segment from a line-of-sight calculation allows easy tracing of a projectile path through space without hitting any walls, even down somewhat twisted tunnels (such as the Kuo corridor above) 。但是復(fù)雜性似乎超過了收益。
我的算法
以上沒有一個令我滿意。首先除了ray casting之外，要么太寬容，要么太過局限，有時兩者都有。而且ray casting有太多偽影，用不來。下面我打算修復(fù)的問題和我想要的功能。
?
- 沒大多數(shù)其他算法那么寬松
- 比其他算法對稱
- 能夠做到對稱（至少跟不能穿墻的怪物相對）而不會損失墻壁擴(kuò)展
- 良好的拐角視野，但不能太好
- 良好的狹窄的空間視野，而不會損失墻壁擴(kuò)展
- 比其他算法更少陰影間隙
- 與菱形墻相當(dāng)?shù)男?/li>
- 沒有死角
- 沒有偽影
- 一致的物理
為此，我會將地牢的幾何結(jié)構(gòu)像下圖一樣表示。 （注意：圖2中的兩個角應(yīng)該是斜角的。我畫錯了。不過，這圖說明了內(nèi)部正方形的用途。）
?
1.? ?? ???如果一個墻tile的兩個相鄰都不是墻，則將該角切成斜角。
2.? ?? ???如果光束與墻的形狀相交，則墻tile可見；
3.? ?? ???如果光束與中心正方形（size最大為tile的1/2）相交，則空白tile可見。
4.? ?? ???與圖形成切線不算相交，并且零寬度的扇形無法照亮。
帶有斜角的實心墻允許在拐角處窺視并可以看到對角空間，同時避免了鉆石墻的理論問題。除非光線在中心附近通過，否則不要看見空白tile，這應(yīng)該會沒那么寬容，減少陰影間隙，減少不對稱性并搞定光線通過窄空間的行為。
圖2說明了光線穿過狹窄空間的問題。不管沿著隧道走多遠(yuǎn)，扇形都會在離開走廊時打開，而其他算法會立即照亮出口上下方的tile。支柱也是同理，就像走廊的墻壁一樣，扇形在穿過支柱之間后打開。不照亮光線照射的比較少的tile就可以避免這種情況，還能讓柱子有效的阻擋光線。因為能防止小束光線照亮tile，應(yīng)該還能減少陰影間隙。
可以通過調(diào)整斜角的角度和內(nèi)部正方形的大小來調(diào)整寬容度。可以使用正方形以外的其他形狀，但是起碼要可以放在tile中的最大菱形區(qū)域（就是不應(yīng)該比柱子大）。用正方形的話，最大值為tile長寬的1/2，測試表明這樣的結(jié)果最好。使用3/8的寬度，可以在長走廊內(nèi)和拐角的單位之間對稱的互望，很不錯，但在其他情況感覺有些局限（尤其是在有許多柱子的環(huán)境下），所以我會用1 /2。實際的實現(xiàn)使用了修改的陰影投射算法，只要我能避免在每個tile上做太多工作就能有不錯的性能。
?
我的算法有兩個對稱版本：一個是完全對稱的版本，另一個是基本對稱的版本（就是單位之間是對稱但穿墻單位另算）。
?
基本對稱的版本。對稱時，它不會遇到其他算法的相同問題。最重要的是不會失去墻壁擴(kuò)展。這是兩個對稱版本中較好的，除非你需要與穿墻單位也對稱
?
完全對稱版本。它與所有穿墻單位都有對稱性，但沒了了墻壁擴(kuò)展；雖然擴(kuò)展程度比大多數(shù)算法更好（寬容FOV除外）。與對稱的菱形墻非常相似但不相同
總結(jié)
以上是生活随笔為你收集整理的Roguelike游戏的视野算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 如何突破瓶颈又释放工作量？ 深度剖析《闪
- 下一篇： 在现代引擎游戏中使用正确的渲染打光流程