在游戏中放置防御结构

Question

我正在为Defcon游戏开发AI机器人.游戏中有不同人口的城市和范围有限的防御结构.我正在尝试制定一个用于放置防御塔的好算法.

因此,根据这三个规则,我们看到最好的位置是塔被放置在最大的人口区域周围的环(虽然我不希望算法只是盲目地在最高人口区域周围放置一个环,有时候可能有两组相距很远的城市,在这种情况下,算法应该制作2个圆圈,每个圆圈占我的总塔数的一半).

我想知道可以使用哪种算法来确定塔的位置？

Answer 1

我不知道这个游戏，但从你的描述来看，你似乎需要一种类似于解决（加权）k 中心问题的算法。不幸的是，这是一个 NP 难题，因此在最好的情况下，您将得到一个受某些因素限制的近似上限。