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.

Answer 2

I think the algorithm you suggest yourself is a good approach:

• For each enemy/ally, draw the partially obscured circle of all locations from which that target could be hit by a bomb, with the given walls.

• Accumulate all these circles with their respective enemy/ally cost together, the pixel with the highest score is your solution

One optimization you could do is this:

• store the enemy targets in a fast spatial datastructure such as a KD-tree
• For each enemy, find the number of neighboring enemies within distance 2*r
• sort the enemies by the number of their neighbors, descending
• go through the list of enemies, starting with the enemy with the most neighbors, and only construct the accumulator map in a radius of 2*r around the current enemy.
• if the current enemy has n neighbors, this means you can achieve at most a score of (n+1)*e with this enemy, assuming you hit all his neighbors too and no allies. So if the the remaining enemies do not have enough neighbors to top the current best score, you can stop the search.

(this assumes that hitting allies does not improve your score)

Finding all nearest neighbors within a fixed radius is a well-researched problem, there should be several efficient implementations in python available.

Answer 3

Here is way might do it more efficiently:-

1. Scan the grid for soldiers
2. Maintain scores for each point in the grid initially at zero
3. For each soldier calculate all points on circumference of circle centered at soldier and radius r
4. Traverse through the ray joining soldier and point on circumference.
5. Check if there is obstacle at current point the ray joining soldier and point on circumference
6. if obstacle not found add e or a according to soldier to the score of current point and move to next.
7. else break and continue with next point on circumference
8. Maintain the highest score achieved while updating a score and also the point.
9. The point and score at end will be optimum drop zone

Time Complexity : -

Scan grid :- O(N*M)

Find circumference : - O(r)

Traverse ray :- O(r)

Work done per soldier :- O(r)*O(r) = O(r^2)

Total time complexity = O(N*M + S*r^2) where S is number of soldiers