确定离其他点最远的点

Question

我正在创建一个简单的游戏，在一些游戏内计算机控制的玩家中实现了一些简单的 AI。我有一个代表玩家可能移动的点的列表。我需要编写一个方法，将玩家移动到该列表中所有敌人最远的点。我用图片说明了这个问题，数字代表列表中点的位置。我希望玩家(4)能移动到列表中位置为2或6的任意一个点，它们是离任何敌人最远的点。如果网格中有多个敌人，我已经通过迭代列表并使用Point的distance()方法来确定哪个点最远，并解决了这个问题。但代码必须在网格中有多个敌人时也能正常工作。

- Fredkr

Answer 1

嗯，你怎么考虑反过来做：

1. Iterate over each point.
2. Find out how close it is to its closest enemy.
3. Choose the point that is furthest from its closest enemy.

早期退出有很大的潜力：

Within the loop store the currently furthest point. 
If you are then inspecting another point and find out
it has a closer enemy, you can immediately skip to the
next point

[编辑]: 如果你正在使用如上所示的网格，你可以

1. Check if there's an enemy on the currently processed 
   point *before* iterating through other enemies. That way
   you can exclude it as early as possible.

2. If it's a densely populated grid, consider doing a breadth-first
   flood-fill starting at the current point. That might find the closest
   enemy much faster than iterating though all of them.

- HumanCatfood