Placement of defensive structures in a game

Question

I am working on an AI bot for the game Defcon. The game has cities, with varying populations, and defensive structures with limited range. I'm trying to work out a good algorithm for placing defence towers.

• Cities with higher populations are more important to defend
• Losing a defence tower is a blow, so towers should be placed reasonably close together
• Towers and cities can only be placed on land

So, with these three rules, we see that the best kind of placement is towers being placed in a ring around the largest population areas (although I don't want an algorithm just to blindly place a ring around the highest area of population, sometime there might be 2 sets of cities far apart, in which case the algorithm should make 2 circles, each one half my total towers).

I'm wondering what kind of algorithms might be used for determining placement of towers?

Answer 1

Just define a utility function that takes a potential build position as input and returns a "rating" for that position. I imagine it would look something like:

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

(k1, k2, and k3 are arbitrary constants that you'll need to tune)

Then, just randomly sample of bunch of different points, p and choose the one with the highest utility.

Answer 2

I would define a function determines the value of a tower placed at that position. Then search for maxima in that function and place a tower there.

A sketch for the function could look like this:

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 

Should give a reasonable algorithm to start with. For improvement you might change the 1/distance function to something different, to get a faster or slower drop of.

Answer 3

I'd start with implementing a fitness function that calculates the expected protection provided by a set of towers on a given map.

You'd calculate the amount of population inside the "protected" area where areas covered by two towers is rated a bit higher than area covered by only one tower (the exact scaling factor depends a lot on the game mechanics, 'though).

Then you could use a genetic algorithm to experiment with different sets of placements and let that run for several (hundered?) iterations.

If your fitness function is a good fit to the real quality of the placement and your implementation of the genetic algorithm is correct, then you should get a reasonable result.

And once you've done all that you can start developing an attack plan that tries to optimize the casualties for any given set of defense tower placements. Once you have that you can set the two populations against each other and reach even better defense plans this way (that is one of the basic ideas of artificial life).

Answer 4

I don't know the game but from your description it seems that you need an algorithm similar to the one for solving the (weighted) k-centers problem. Well, unfortunately, this is an NP hard problem so in the best case you'll get an approximation upper bounded by some factor.

Take a look here: http://algo2.iti.kit.edu/vanstee/courses/kcenter.pdf