防守结构在游戏中的位置

Question

我正在为游戏德文的AI机器人工作。游戏有城市，人口不同，防御结构有限。我在努力想出一个很好的算法来放置防御塔。

• 人口较多的城市更需要保护。
• 失去一座防御塔是一个打击，所以应该合理地将塔放置在一起。
• 高塔和城市只能放在陆地上。

因此，有了这三条规则，我们看到最好的放置方式是将塔放置在一个圈内，围绕着最大的人口区域(虽然我不想要一个算法只是盲目地在最高的人口区域周围放置一个圈，有时可能有两组城市相距很远，在这种情况下，算法应该是两个圆圈，每一个是我的塔总数的一半)。

我想知道什么样的算法可以用来确定塔的位置？

Answer 1

我不知道这个游戏，但是从你的描述来看，你似乎需要一个类似于(加权)k中心问题的算法。嗯，不幸的是，这是一个NP难问题，所以在最好的情况下，你会得到一个由某个因子限制的近似上限。

看看这里：http://algo2.iti.kit.edu/vanstee/courses/kcenter.pdf

Answer 2

我会定义一个函数来决定放置在那个位置的塔的价值。然后在这个函数中搜索极大值，并在那里放置一座塔。

函数的草图可能如下所示：

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/ change函数更改为不同的函数，以得到更快或更慢的下降。

Answer 3

我首先要实现一个健身功能，它计算给定地图上的一组塔所提供的预期保护。

你可以计算出“保护”区域内的人口数量，在那里，两座塔覆盖的区域比只有一座塔覆盖的区域要高一些(确切的比例因子在很大程度上取决于游戏机制)。

然后，您可以使用一个遗传算法来试验不同的位置，并让它运行几个(？)迭代。

如果你的适应度函数是一个很好的符合实际质量的布局，而你的遗传算法的实现是正确的，那么你应该得到一个合理的结果。

一旦你完成了所有的工作，你就可以开始制定一个攻击计划，试图为任何一组防御塔的位置优化伤亡人数。一旦你有了它，你就可以让这两个群体互相对抗，并以这种方式达成更好的防御计划(这是人工生命的基本思想之一)。