在遊戲中放置防禦結構

我正在使用AI機器人遊戲Defcon。遊戲中有城市，人口衆多，防禦性結構範圍有限。我正在嘗試制定一個放置防禦塔的好算法。在遊戲中放置防禦結構

城市具有較高的人羣是防守
失去一個防禦塔是一個打擊更重要，因此塔應合理靠近配置
塔和城市只能放在土地

所以，有了這三條規則，我們發現最好的放置方式是在最大的人口區域周圍放置一個環形塔（儘管我不希望算法只是盲目地在最高的人口區域放置一個環，有時可能會有2套卡西在這種情況下，該算法應該製作2個圈，每個圈都是我的總塔數）。

我不知道會用什麼樣的算法來確定塔的位置？

來源

2010-02-23 Martin

我不知道遊戲，但從你的描述看來，你似乎需要一個類似於解決（加權）k中心問題的算法。那麼，不幸的是，這是一個NP難題，所以在最好的情況下，你會得到一個由某個因子約束的近似值。

到這裏看看：http://algo2.iti.kit.edu/vanstee/courses/kcenter.pdf

來源

2010-02-23 11:55:50

哦，這看起來很有趣，它看起來很像我的問題。我將詳細瞭解k中心問題。謝謝 – Martin 2010-02-23 12:02:09

我不認爲這是同一類問題。 1.大多數遊戲只允許在不連續的位置放置棋子，所以蠻力算法可能是多項式的。 2.我無法看到k中心問題如何可能導致OP描述的環狀結構，以及哪種聲音合理。 – 2010-02-23 12:04:52

我認爲Defcon允許單位被放置在浮點位置，所以它不在離散位置。想想這樣，我們希望最大限度地減少從一個城市到一個塔的最大距離，並按照人口規模加權。聽起來更像現在的kcenter問題？ – Martin 2010-02-23 12:15:00

只要定義一個效用函數，需要一個潛在的建造位置作爲輸入，並返回該位置的「評級」。我想這將是這個樣子：

utility(position p) = k1 * population_of_city_at_p + 
         k2 * new_area_covered_if_placed_at_p + 
         k3 * number_of_nearby_defences

（，k2，並且k3是，你需要調整任意常數）

然後，一羣不同點的只是隨機抽樣，p和選擇效用最高的那個。

來源

2010-02-23 11:51:03

我會定義一個函數來確定放置在該位置的塔的值。然後搜索該功能的最大值，並在那裏放置一個塔。

一種功能草圖看起來是這樣的：

if water return 0 

popsum = sum for all city over (population/distance) // it's better to have towers close by 

towersum = - sum for all existing towers (1/distance) // you want you towers spread somewhat evenly 

return popsum + towersum*f // f adjusts the relative importance of spreading towers equally and protecting the population centers with many towers

應該給出一個合理的算法開始。爲了改進，你可以將1 /距離函數改爲不同的東西，以獲得更快或更慢的下降。

來源

2010-02-23 11:52:32

我與執行計算由一組塔給定的地圖上提供的預期保護健身功能啓動。

您會計算「受保護」區域內兩個塔所覆蓋的區域的評分稍高於只有一個塔的區域的人口數量（確切的縮放因子很大程度上取決於遊戲機制，''雖然）。

那麼你可以使用一個genetic algorithm嘗試不同的展示位置集合，並讓數即運行（hundered？）迭代。

如果您的健身功能，是一個不錯的選擇，以安置的實際質量和你的遺傳算法的實現是正確的，那麼你應該得到一個合理的結果。

而且一旦你已經做了所有你可以開始開發，試圖優化傷亡任何給定的防禦塔的展示位置的攻擊計劃。一旦你有了這些，你就可以將這兩個人羣相互對抗，並以這種方式達到更好的防禦計劃（這是artificial life的基本思想之一）。

來源

2010-02-23 11:53:56

這聽起來像是一個不錯的主意，但運行的遺傳算法的DEFCON會有點後勤困難很遺憾。我會研究它：D – Martin 2010-02-23 12:00:10

遊戲機制聽起來比GA更適合模擬退火;通常，SA中的多維連續值維度比GA更容易。兩種算法在合理的時間內都能很好地逼近NP難題......完美並不總是值得等待。 – 2010-02-23 12:30:35

@McGregor：這很可能是真的，我只是比GA更熟悉GA ;-) – 2010-02-23 13:24:23

在遊戲中放置防禦結構

回答

相關問題