Determine the farthest point from other points

Question

I am creating a simple game with some simple AI implementations on some players playing a gaming computer.

I have a Point list representing possible actions for a player. I need to write a method that moves the player to Point beyond all possible enemies on this list. I illustrated this with a picture:

The numbers represent the poistion points in the list.

I want player (4) to move to Point at positions 2 or 6, which are farthest from any enemies. I managed to solve this if there is one enemy, iterating over the list and using the distance() Point method to determine which point is farthest. But the code should work even if there are several enemies in the grid.

Answer 1

Hmm, how about you doing it the other way around:

 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. 

There are many opportunities for early outs:

 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 

[edit]: also, if you work with the grid as described above, you can

 1. Check if there 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 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.