title: How to quickly find optimal bomb drop zone?
body: <p>I've been given a homework that goes something like this:</p>
  <blockquote>
  <p>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:</p>
  <ul>
  <li><code>r</code> - bomb's radius of effect (in pixels, positive integer)</li>
  <li><code>e</code> - number of points for killing an enemy</li>
  <li><code>a</code> - number of points for killing an ally</li>
  </ul>
  <p>(for example <code>r = 10</code>, <code>e = 1</code>, <code>a = -2</code>)</p>
  <p>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.</p>
  <p>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.</p>
  </blockquote>
  <p>Here's an example image cropped, resized and with colors changed to improve readability:</p>
  <blockquote>
  <p><img src="https://i.stack.imgur.com/6gxo2.png" alt="Example four-colored image" /></p>
  </blockquote>
  <p>Original image I've been given can be found <a href="https://i.stack.imgur.com/hZbul.png" rel="noreferrer">here</a>.</p>
  <h1>What I have already worked out</h1>
  <p>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:</p>
  <pre><code>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
  </code></pre>
  <p>Of course this <em>'snippet'</em> 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.</p>
  <p>Without constraining circles I would do it like that:</p>
  <pre><code>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
  </code></pre>
  <p>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.</p>
  <p>I'm looking for a more elegant and <em>fast</em> solution to this problem. How would you solve it? I'll be implementing it in Python with PIL, if that helps.</p>
  <p>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.</p>
  <hr />