How to quickly find optimal bomb drop zone?

Question

I've been given a homework that goes something like this:

You're given an image consisting of pixels in four colors. Colours correspond to terrain, enemies, allies and walls. A bomb can be dropped at any coordinate (a pair of integers). You are also given:

• r - bomb's radius of effect (in pixels, positive integer)
• e - number of points for killing an enemy
• a - number of points for killing an ally

(for example r = 10, e = 1, a = -2)

When a bomb is dropped, all enemies and allies in radius (Euclidean distance) are killed, unless there is a wall between them and the bomb (ie. non-antialiased line connecting the soldier with bomb crosses a wall). When the bomb falls on a wall, this specific pixel behaves just like normal terrain. The rest of the wall is still a wall.

You're starting with a score of 0. Find the coordinates where you should drop one bomb to get best score possible. If there are multiple optimal solutions, return any of them.

Here's an example image cropped, resized and with colors changed to improve readability:

Original image I've been given can be found here.

What I have already worked out

I know that brute-forcing this problem is a terrible solution. I came up with an idea how to solve it quickly when there are no walls. Here's some pseudocode:

args Map, R, A, E

for (every Soldier)
    create a Heightmap with dimensions of Map
    zero-fill the Heightmap
    on the Heightmap draw a filled circle of value 1 around Soldier with radius R

    if (Soldier is Ally)
        multiply Heightmap by A
    else
        multiply Heightmap by E

add all Heightmaps together
return coordinates of highest point in TotalHeightmap

Of course this 'snippet' can be optimized, but it's easier to understand in this form. It could be extended to a full solution by constraining heightmap circles with walls. Drawing circles is simple and many image-processing libraries provide functions to do it, so maybe it's a good idea to draw circles, then draw walls on them and flood-fill circles from the center stopping on walls or circle boundaries. I'll check the performance when I'll be implementing it.

Without constraining circles I would do it like that:

run the above code to get a TotalHeightmap
create empty PointList

for (every Point in TotalHeightmap)
    create PointObject with properties:
        Coordinates,
        Height,
        WallsFlag = False
    add PointObject to PointList

sort PointList by descending Height

until (PointList[0].WallsFlag == True)
    for (every Soldier in radius R from PointList[0])
        if (Bresenham line connecting Soldier with PointList[0] intersects a Wall)
            subtract (A if Soldier is Ally else E) from PointList[0].Height

    set PointList[0].WallsFlag = True
    sort PointList by descending Height

return PointList[0].Coordinates

It will work as long as both enemy and ally scores are non-negative, so it's far from perfect. To fix that I could loop over all pixels, but that would be terribly slow (not as slow as brute-forcing it, I guess, but it doesn't sound like a good idea). The method of finding wall intersections seems crude too.

I'm looking for a more elegant and fast solution to this problem. How would you solve it? I'll be implementing it in Python with PIL, if that helps.

Btw I believe my teacher is fine with me posting this question on SO, I believe he even expects me to discuss it and implement best solution.

---

Answer 1

Here's a partial answer that I hope will spark some discussion:

The first rule of solving any problem is to find an easier problem. In this case, we can ask:

What would be a good solution if there were no walls?

and further reduce that to

What would be a good solution if there were no walls or enemies?

and even further,

What would be a good solution if there were no walls or enemies and the bomb's radius was 1?

which is equivalent to saying

Given a set of points, position a unit disk to cover the largest number of points possible.

Cool. That feels like a nice, solid, domain-independent problem that many people are sure to have encountered before. Some quick Googling and wahey, we find quite a few relevant resources, including this SO question.

In that question, the accepted answer makes an important observation: that if we have a disk that covers the maximum number of points, we can move that disk about to get another disk with at least two points on its edge. As such if we take every pair of points within distance 2 of eachother and construct the two unit circles through that pair of points (for O(n^2) circles overall), then one of these circles is guaranteed to contain the maximal number of points possible.

This can easily be adapted to the "without walls" version of your problem. While it'll be O(n^3) naively (possibly O(n^2) circles and possibly n points inside each circle), it's likely much faster than that in typical problem instances. If you want to be clever about it though, look into the fixed radius nearest-neighbour problem (best paper I could find is here but unfortunately there's no public version).

How can we introduce walls though? If a disk intersects a wall, we can't reliably move it so that two points lie on the edge while maintaining the same score. I'll have a think about it, and hopefully someone else will have some ideas in the meantime.

Three scenarios to mentally test any candidate algorithm against:

1. Find the location that maximizes the number of points simultaneously within unit distance and line of sight when there is a single "pixel" of wall on the map.

2. Find the location that maximizes the number of points simultaneously within unit distance and line of sight when there is a single, straight wall on the map.

3. Find the location that maximizes the number of points simultaneously within unit distance and line of sight when the walls form a single, hollow, square on the map.