RTS遊戲中視線計算的快速算法

Question

我正在製作一個簡單的RTS遊戲。我希望它運行得非常快，因爲它可以與數千個單位和8名球員一起工作。

一切似乎都完美無缺，但似乎視線計算是一個瓶頸。很簡單：如果一個敵方單位比我單位的任何LOS距離都更近，它就會顯示出來。

目前我使用一個相當天真的算法：對於每個敵方單位，我檢查我的任何單位是否看到他。這是O（n^2）

所以，如果有8名球員，他們有3000個單位，每個球員在最壞的情況下意味着3000 * 21000 = 63000000測試。這很慢。

更多細節：這是一個愚蠢的簡單2D空間RTS：沒有網格，單位沿着直線移動，沒有碰撞，因此它們可以相互移動。因此，甚至有數百個單位可以在同一個地點。

我想以某種方式加快這個LOS算法。有任何想法嗎？

編輯：

所以額外的細節：

• 我是一個球員能有3000甚至單位。
• 我的單位有雷達，所以他們向所有方向平等。

Answer 1

使用spatial data structure可以按位置高效查找單位。

此外，如果你只關心一個單元是否是可見的，而不是哪個單位看上它，你可以做

for each unit 
    mark the regions this unit sees in your spatial data structure 

，並具有：

isVisible(unit) = isVisible(region(unit)) 

一個非常簡單的空間數據結構網格：你在賽場上覆蓋一個粗糙的網格。這些區域就是這個網格的單元格。你分配一個區域數組，併爲每個區域保留當前在這個區域中的單元列表。

您可能還會發現Muki Haklay's demonstration of spatial indexes有用。

Answer 2

gamedev中最基本的規則之一是通過利用遊戲定義的所有可能的約束條件來優化算法中的貝葉斯 - 這是您沒有看到在任何給定的頂部上構建的非常不同的遊戲的主要原因公司的遊戲引擎，他們已經非常有效地利用了他們的限制，以至於他們無法處理任何不在這些限制之內的事情。這就是說，你說單位直線移動 - 你說球員可以有3000個單位 - 即使我假設這對於8個球員來說是3000個單位，那麼每個球員的單位是375個單位，所以我認爲我是安全的假設在遊戲的每一步（我假設每一步都涉及上述計算）表示更多單位不會改變方向比單位將改變方向。所以，如果這是真的，那麼你想把你所有的作品分成兩個小組 - 那些在最後一步確實改變了方向，而那些沒有做到的小組。你需要做一些調整 - 對於任何兩個敵對部隊的單位，你想問'單元A何時會看到單元B，因爲單元A和單元B都不改變方向或速度？（可以處理加速/減速，但隨後會變得更加複雜） - 爲了計算這個，首先需要確定單元A和單元B正在行駛的矢量是否相交（簡單的2D線交點計算，並結合計算，告訴你什麼時候每個單位擊中這個交點） - 如果他們不這樣做，並且他們現在不能看到對方，那麼除非他們中的至少一個改變方向，否則他們永遠不會看到對方。如果它們相交，那麼你需要計算第一個單位和第二個單位通過交點的時間差 - 如果這個距離大於LOS範圍，那麼這些單位將永遠不會看到對方，除非一個方向改變 - 如果這個差值小於LOS範圍，那麼再多幾次（大力揮手）計算就會告訴你這個祝福事件將發生在。

現在，你所擁有的是一個信息集合，它被分解爲永不會彼此看到的元素，以及將來會在某個時間t看到彼此的元素 - 每一步，你只需處理已經發生變化的單位方向並計算它們與其餘單位的互動。 （哦，並且處理那些先前的計算告訴你會看到彼此的單元 - 記住要將它們保存在一個可插入的有序結構中）你有效地做的是利用系統的線性行爲來改變你的問題「並不單元A看到單元B」來「當意志單元A看到單元B」

現在，這一切說，這是不打折的空間數據結構的答案 - 這是一個很好的答案 - 然而，它也能夠處理隨機運動的單位，所以你想考慮如何進一步優化這個過程 - 你還需要小心處理跨區域的可見性，即在兩個不同區域的邊界的單位可能是能夠看到對方 - 如果你有碎片，往往會聚集在一起，你唱出具有可變尺寸的空間數據結構可能是答案，其中不在相同區域中的片段被保證不能夠看到彼此。

Answer 3

我會用網格做到這一點。我認爲這就是商業RTS遊戲如何解決這個問題。

• 使能見度跟蹤器的遊戲世界分散。 （方格是最容易的，用粗糙的實驗看看什麼值最好。）
• 記錄每個區域的當前單位。 （每當一個單位移動時更新。）
• 記錄每個玩家看到的區域。 （必須在單位移動時進行更新，單位可以輪詢以確定其可見的圖塊，或者您可以在遊戲開始前分析地圖。）
• 爲敵人制作一個列表（或任何適合的結構）每個玩家看到的單位。

現在只要一個單元從另一個知名度的一個區域去，進行檢查：

• 從一個看不見又到了看到區 - 單元添加到玩家的知名度跟蹤。
• 從看到的地方到看不見的地方 - 從玩家的能見度跟蹤器中移除單位。
• 在另外兩種情況下，沒有發生可見性變化。

這很快但需要一些記憶。但是，使用BitArrays和指針列表時，內存使用情況不會那麼糟糕。

有關於這一點的遊戲編程精粹的一本書的文章（前三之一，我想。）