algorithm - 如何快速找到最佳投弹区？

Question

我的家庭作业是这样的:

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 .

我已经解决的问题

我知道暴力破解这个问题是一个糟糕的解决方案。我想出了一个想法，如何在没有墙的情况下快速解决它。这是一些伪代码:

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

当然这个'snippet'可以优化，但是这种形式更容易理解。它可以通过用墙限制高度图圆圈来扩展为完整的解决方案。画圆很简单，许多图像处理库都提供了这样做的功能，所以画圆，然后在圆上画墙，然后从中心填充圆，停在墙或圆边界上，这也许是个好主意。我会在实现时检查性能。

如果没有约束圈，我会这样做:

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

只要敌人和盟友的分数都为非负值，它就会起作用，所以它远非完美。为了解决这个问题，我可以遍历所有像素，但这会非常慢(我猜不如暴力破解那么慢，但这听起来不是个好主意)。寻找墙交点的方法也很粗糙。

我正在寻找一个更优雅和快速的解决方案来解决这个问题。你会怎么解决？如果有帮助，我将使用 PIL 在 Python 中实现它。

顺便说一句，我相信我的老师对我在 SO 上发布这个问题没有意见，我相信他甚至希望我讨论它并实现最佳解决方案。

---

Answer 1

以下是我希望能引发一些讨论的部分答案:

解决任何问题的首要规则是找到更简单的问题。在这种情况下，我们可以问:

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

并进一步减少到

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

更进一步，

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

相当于说

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

很酷。这感觉像是一个很好的、可靠的、与领域无关的问题，很多人以前肯定遇到过。一些快速的谷歌搜索和哇嘿，我们找到了很多相关资源，包括 this SO question .

在该问题中，已接受的答案提出了一个重要的观察结果:如果我们有一个覆盖最大点数的圆盘，我们可以将该圆盘移动到另一个边缘至少有两个点的圆盘上。因此，如果我们取彼此距离为 2 以内的每一对点，并通过这对点构造两个单位圆(对于 O(n^2) 个圆)，那么这些圆中的一个是保证包含尽可能多的点数。

这可以很容易地适应您问题的“无墙”版本。虽然这将是 O(n^3) 天真(可能是 O(n^2) 个圆圈，每个圆圈内可能有 n 个点) ，它可能比典型问题实例中的速度快得多。如果你想聪明点，看看固定半径最近邻问题(我能找到的最好的论文是 here 但不幸的是没有公开版本)。

我们如何引入墙？如果一个圆盘与一堵墙相交，我们就无法可靠地移动它，使两个点位于边缘上，同时保持相同的分数。我会考虑一下，同时希望其他人能有一些想法。

对任何候选算法进行心理测试的三种场景:

1. 本地图上只有一个“像素”墙时，找到在单位距离和视线内同时使点数最多的位置。

2. 本地图上有一面直墙时，找到在单位距离和视线内同时最大化点数的位置。

3. 当墙壁在 map 上形成一个单一的空心正方形时，找到单位距离和视线内同时点数最多的位置。