在游戏中放置防御结构

我正在使用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

在游戏中放置防御结构

回答

相关问题