Finding the furthest point in a grid when compared to other points

Question

I have a rectangular grid of variable size but averaging 500x500 with a small number of x,y points in it (less than 5). I need to find an algorithm that returns an x,y pair that is the farthest away possible from any of the other points.

Context: App's screen (grid) and a set of x,y points (enemies). The player dies and I need an algorithm that respawns them as far away from the enemies so that they don't die immediately after respawning.

What I have so far: The algorithm I wrote works but doesn't perform that great in slower phones. I'm basically dividing up the grid into squares (much like a tic tac toe) and I assign each square a number. I then check every single square against all enemies and store what the closest enemy was at each square. The square with the highest number is the square that has the closest enemy furthest away. I also tried averaging the existing points and doing something similar to this and while the performance was acceptable, the reliability of the method was not.

If you haven't already done so, try replacing squareroot(deltax^2 + deltay^2) with deltax+deltay, that should improve your peformance a bit. — Roy Shahaf, Aug 11 '15 at 21:49
One approach might be to set some minimum distance threshold that the new player must be away from all enemies in order to respawn, then generate random points until one of them meets that threshold. It's not optimal but it would be fast and might be 'good enough'. — Tony Tuttle, Aug 11 '15 at 22:39
Is the distance to the closest enemy all-important, or can one be relatively close if all the others are far away? — m69's been on strike for years, Aug 11 '15 at 22:40
@huck_cussler that's a great idea, please post it as an answer as it might just be what I'm looking for. m69 yes, it's important as it's a fast paced game. Roy Shahaf, still no dice, thanks! — Julian, Aug 11 '15 at 22:52
The best tactic for the enemy is to organise into a circle radius 125*sqrt(2) around the centre, then tighten the net when the player spawns into the trap. — Colonel Panic, Aug 12 '15 at 15:52
@Julian Please see my updated answer for a demonstration. Cheers. — גלעד ברקן, Aug 12 '15 at 22:23

m69's been on strike for years · Accepted Answer · 2015-08-12T04:43:19.563

This is the simplest algorithm I could think of that still gives good results. It only checks 9 possible positions: the corners, the middle of the sides, and the center point. Most of the time the player ends up in a corner, but you obviously need more positions than enemies.

The algorithm runs in 0.013ms on my i5 desktop. If you replace the Math.pow() by Math.abs(), that comes down to 0.0088ms, though obviously with less reliable results. (Oddly enough, that's slower than my other answer which uses trigonometry functions.)

Running the code snippet (repeatedly) will show the result with randomly positioned enemies in a canvas element.

function furthestFrom(enemy) {
    var point = [{x:0,y:0},{x:250,y:0},{x:500,y:0},{x:0,y:250},{x:250,y:250},{x:500,y:250},{x:0,y:500},{x:250,y:500},{x:500,y:500}];
    var dist2 = [500000,500000,500000,500000,500000,500000,500000,500000,500000];
    var max = 0, furthest;

    for (var i in point) {
        for (var j in enemy) {
             var d = Math.pow(point[i].x - enemy[j].x, 2) + Math.pow(point[i].y - enemy[j].y, 2);
             if (d < dist2[i]) dist2[i] = d;
        }
        if (dist2[i] > max) {
            max = dist2[i];
            furthest = i;
        }
    }
    return(point[furthest]);
}

// CREATE TEST DATA
var enemy = [];
for (var i = 0; i < 5; i++) enemy[i] = {x: Math.round(Math.random() * 500), y: Math.round(Math.random() * 500)};

// RUN FUNCTION
var result = furthestFrom(enemy);

// SHOW RESULT ON CANVAS
var canvas = document.getElementById("canvas");
canvas.width = 500; canvas.height = 500;
canvas = canvas.getContext("2d");
for (var i = 0; i < 5; i++) {
    paintDot(canvas, enemy[i].x, enemy[i].y, 10, "red");
}
paintDot(canvas, result.x, result.y, 20, "blue");
function paintDot(canvas, x, y, size, color) {
canvas.beginPath();
canvas.arc(x, y, size, 0, 6.2831853);
canvas.closePath();
canvas.fillStyle = color;
canvas.fill();
}

<BODY STYLE="margin: 0; border: 0; padding: 0;">
<CANVAS ID="canvas" STYLE="width: 200px; height: 200px; background-color: #EEE;"></CANVAS>
</BODY>

After trying all the answers on this page, this one was the one that I ended up using as it gave me predictable performance. I tweaked the preset points dynamically with every game play so they would "look" random at least on every level. Thanks! — Julian, Aug 12 '15 at 18:53

John Coleman · Answer 2 · 2015-08-12T00:58:21.277

This is similar to what you are already doing, but with two passes where the first pass can be fairly crude. First decrease resolution. Divide the 500x500 grid into 10x10 grids each of which is 50x50. For each of the resulting 100 subgrids -- determine which have at least one enemy and locate the subgrid that is furthest away from a subgrid which contains an enemy. At this stage there is only 100 subgrids to worry about. Once you find the subgrid which is furthest away from an enemy -- increase resolution. That subgrid has 50x50 = 2500 squares. Do your original approach with those squares. The result is 50x50 + 100 = 2600 squares to process rather than 500x500 = 250,000. (Adjust the numbers as appropriate for the case in which there isn't 500x500 but with the same basic strategy).

Here is a Python3 implementation. It uses two functions:

1) fullResSearch(a,b,n,enemies) This function takes a set of enemies, a corner location (a,b) and an int, n, and finds the point in the nxn square of positions whose upper-left hand corner is (a,b) and finds the point in that square whose which has the maximum min-distance to an enemy. The enemies are not assumed to be in this nxn grid (although they certainly can be)

2) findSafePoint(n, enemies, mesh = 20) This function takes a set of enemies who are assumed to be in the nxn grid starting at (0,0). mesh determines the size of the subgrids, defaulting to 20. The overall grid is split into mesh x mesh subgrids (or slightly smaller along the boundaries if mesh doesn't divide n) which I think of as territories. I call a territory an enemy territory if it has an enemy in it. I create the set of enemy territories and pass it to fullResSearch with parameter n divided by mesh rather than n. The return value gives me the territory which is farthest from any enemy territory. Such a territory can be regarded as fairly safe. I feed that territory back into fullResSearch to find the safest point in that territory as the overall return function. The resulting point is either optimal or near-optimal and is computed very quickly. Here is the code (together with a test function):

import random

def fullResSearch(a,b,n,enemies):

    minDists = [[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            minDists[i][j] = min((a+i - x)**2 + (b+j - y)**2 for (x,y) in enemies)

    maximin = 0
    for i in range(n):
        for j in range(n):
            if minDists[i][j] > maximin:
                maximin = minDists[i][j]
                farthest = (a+i,b+j)
    return farthest

def findSafePoint(n, enemies, mesh = 20):
    m = n // mesh 
    territories = set() #enemy territories
    for (x,y) in enemies:
        i = x//mesh
        j = y//mesh
        territories.add((i,j))
    (i,j) = fullResSearch(0,0,m,territories)
    a = i*mesh
    b = j*mesh
    k = min(mesh,n - a,n - b) #in case mesh doesn't divide n
    return fullResSearch(a,b,k,enemies)

def test(n, numEnemies, mesh = 20):
    enemies = set()
    count = 0
    while count < numEnemies:
        i = random.randint(0,n-1)
        j = random.randint(0,n-1)
        if not (i,j) in enemies:
            enemies.add ((i,j))
            count += 1
    for e in enemies: print("Enemy at", e)
    print("Safe point at", findSafePoint(n,enemies, mesh))

A typical run:

>>> test(500,5)
Enemy at (216, 67)
Enemy at (145, 251)
Enemy at (407, 256)
Enemy at (111, 258)
Enemy at (26, 298)
Safe point at (271, 499)

(I verified by using fullResSearch on the overall grid that (271,499) is in fact optimal for these enemies)

firereaction · Answer 3 · 2015-08-12T08:52:13.263

Here's an interesting solution, however I cannot test it's efficiency. For each enemy, make a line of numbers from each number, starting with one and increasing by one for each increase in distance. Four initial lines will come from the four edges and each time you go one further out, you create another line coming out at a 90 degree angle, also increasing the number each change in distance. If the number line encounters an already created number that is smaller than it, it will not overwrite it and will stop reaching further. Essentially, this makes it so that if the lines find a number smaller than it, it won't check any further grid marks, eliminating the need to check the entire grid for all of the enemies.

<<<<<<^^^^^^^
<<<<<<^^^^^^^
<<<<<<X>>>>>>       
vvvvvvv>>>>>>
vvvvvvv>>>>>>

public void map(int posX, int posY)
{
    //left up right down
    makeLine(posX, posY, -1, 0, 0, -1);
    makeLine(posX, posY, 0, 1, -1, 0);
    makeLine(posX, posY, 1, 0, 0, 1);
    makeLine(posX, posY, 0, -1, 1, 0);
    grid[posX][posY] = 1000;
}
public void makeLine(int posX, int posY, int dirX, int dirY, int dir2X, int dir2Y)
{
    int currentVal = 1;
    posX += dirX;
    posY += dirY;
    while (0 <= posX && posX < maxX && posY < maxY && posY >= 0 && currentVal < grid[posX][posY])
    {
        int secondaryPosX = posX + dir2X;
        int secondaryPosY = posY + dir2Y;
        int secondaryVal = currentVal + 1;
        makeSecondaryLine( secondaryPosX, secondaryPosY, dir2X, dir2Y, secondaryVal);
        makeSecondaryLine( secondaryPosX, secondaryPosY, -dir2X, -dir2Y, secondaryVal);
        grid[posX][posY] = currentVal;
        posX += dirX;
        posY += dirY;
        currentVal++;
    }
}
public void makeSecondaryLine(int secondaryPosX, int secondaryPosY, int dir2X, int dir2Y, int secondaryVal)
{
    while (0 <= secondaryPosX && secondaryPosX < maxX && secondaryPosY < maxY && 
            secondaryPosY >= 0 && secondaryVal < grid[secondaryPosX][secondaryPosY])
    {
        grid[secondaryPosX][secondaryPosY] = secondaryVal;
        secondaryPosX += dir2X;
        secondaryPosY += dir2Y;
        secondaryVal++;
    }
}

}

Here is the code I used to map out the entire grid. The nice thing about this, is that the number of times the number is checked/written is not that much dependent on the number of enemies on the screen. Using a counter and randomly generated enemies, I was able to get this: 124 enemies and 1528537 checks, 68 enemies and 1246769 checks, 15 enemies and 795695 500 enemies and 1747452 checks. This is a huge difference compared to your earlier code which would do number of enemies * number of spaces. for 124 enemies you'd have done 31000000 checks, while instead this did 1528537, which is less than 5% of the number of checks normally done.

I'm not entirely sure what you mean by "make a line of numbers from each number" and "Four initial lines will come from the four edges". Could you clarify the answer or maybe post some pseudocode? — Julian, Aug 11 '15 at 22:16
I was curious to see how my code performs compared to this, so I tried to javascriptify your code for a quick comparison. Which values do you use for maxX and maxY? — m69's been on strike for years, Aug 12 '15 at 12:13
maxX and maxY are sizes of the grid. if the grid is 500x500 maxX is 500 and maxY is 500. I used a 500x500 grid. You also run map with every enemy on the grid, not just one of them. — firereaction, Aug 12 '15 at 18:44
Then just go through the grid and find the spot with the highest number. — firereaction, Aug 12 '15 at 19:09
The nice thing about this is that you can use a courser grid too; that way you get to choose whether you want accuracy or speed, or something inbetween. (It's difficult to time it, because I have to fill up the grid with initial values between every run.) — m69's been on strike for years, Aug 12 '15 at 19:16
The Javascript version takes around 3ms on an i5 desktop at a resolution of 100x100, which still gives good results. At full resolution however, it takes almost 100ms. — m69's been on strike for years, Aug 12 '15 at 19:29
It also depends on how many enemies Julian has on the grid . If he has a small number of enemies it would definitely be better to use some other method, but the nice thing about this one is that the speed of it doesn't really depend as much on the number of enemies, but rather the size of the grid. I am also still a student so I didn't really expect it to be that efficient. — firereaction, Aug 12 '15 at 19:31
Yes, the limited number of enemies favours solutions with per-enemy instead of per-location calculatons. — m69's been on strike for years, Aug 12 '15 at 19:41

m69's been on strike for years · Answer 4 · 2015-08-12T04:41:14.557

This method looks at all the enemies from the center point, checks the direction they're in, finds the emptiest sector, and then returns a point on a line through the middle of that sector, 250 away from the center.
The result isn't always perfect, and the safe spot is never in the center (though that could be added), but maybe it's good enough.

The algorithm runs more than a million times per second on my i5 desktop, but a phone may not be that good with trigonometry. The algorithm uses 3 trigonometry functions per enemy: atan2(), cos() and sin(). Those will probably have the most impact on the speed of execution. Maybe you could replace the cos() and sin() with a lookup table.

Run the code snippet to see an example with randomly positioned enemies.

function furthestFrom(e) {
    var dir = [], widest = 0, bisect;
    for (var i = 0; i < 5; i++) {
        dir[i] = Math.atan2(e[i].y - 250, e[i].x - 250);
    }
    dir.sort(function(a, b){return a - b});
    dir.push(dir[0] + 6.2831853);
    for (var i = 0; i < 5; i++) {
        var angle = dir[i + 1] - dir[i];
        if (angle > widest) {
            widest = angle;
            bisect = dir[i] + angle / 2;
        }
    }
    return({x: 250 * (1 + Math.cos(bisect)), y: 250 * (1 + Math.sin(bisect))});
}

// CREATE TEST DATA
var enemy = [];
for (var i = 0; i < 5; i++) enemy[i] = {x: Math.round(Math.random() * 500), y: Math.round(Math.random() * 500)};

// RUN FUNCTION AND SHOW RESULT ON CANVAS
var result = furthestFrom(enemy);
var canvas = document.getElementById("canvas");
canvas.width = 500; canvas.height = 500;
canvas = canvas.getContext("2d");
for (var i = 0; i < 5; i++) {
    paintDot(canvas, enemy[i].x, enemy[i].y, "red");
}
paintDot(canvas, result.x, result.y, "blue");

// PAINT DOT ON CANVAS
function paintDot(canvas, x, y, color) {
canvas.beginPath();
canvas.arc(x, y, 10, 0, 6.2831853);
canvas.closePath();
canvas.fillStyle = color;
canvas.fill();
}

<BODY STYLE="margin: 0; border: 0; padding: 0">
<CANVAS ID="canvas" STYLE="width: 200px; height: 200px; background-color: #EEE;"CANVAS>
</BODY>

גלעד ברקן · Answer 5 · 2015-08-13T10:16:28.010

Triangulate the enemies (there's less than 5?); and triangulate each corner of the grid with the closest pair of enemies to it. The circumcenter of one of these triangles should be a decent place to re-spawn.

Below is an example in JavaScript. I used the canvas method from m69's answer for demonstration. The green dots are the candidates tested to arrive at the blue-colored suggestion. Since we are triangulating the corners, they are not offered as solutions here (perhaps the randomly-closer solutions can be exciting for a player? Alternatively, just test for the corners as well..).

// http://stackoverflow.com/questions/4103405/what-is-the-algorithm-for-finding-the-center-of-a-circle-from-three-points
function circumcenter(x1,y1,x2,y2,x3,y3)
{
  var offset = x2 * x2 + y2 * y2;
  var bc =   ( x1 * x1 + y1 * y1 - offset ) / 2;
  var cd =   (offset - x3 * x3 - y3 * y3) / 2;
  var det =  (x1 - x2) * (y2 - y3) - (x2 - x3)* (y1 - y2);

  var idet = 1/det;

  var centerx =  (bc * (y2 - y3) - cd * (y1 - y2)) * idet;
  var centery =  (cd * (x1 - x2) - bc * (x2 - x3)) * idet;

  return [centerx,centery];
}

var best = 0,
    candidates = [];

function better(pt,pts){
  var temp = Infinity;
  for (var i=0; i<pts.length; i+=2){
    var d = (pts[i] - pt[0])*(pts[i] - pt[0]) + (pts[i+1] - pt[1])*(pts[i+1] - pt[1]);
    if (d <= best)
      return false;
    else if (d < temp)
      temp = d;
  }
  best = temp;
  return true;
}

function f(es){
  if (es.length < 2)
    return "farthest corner";
    
  var corners = [0,0,500,0,500,500,0,500],
      bestcandidate;  
  
  // test enemies only
  if (es.length > 2){
    for (var i=0; i<es.length-4; i+=2){
      for (var j=i+2; j<es.length-2; j+=2){
        for (var k=j+2; k<es.length; k+=2){
          var candidate = circumcenter(es[i],es[i+1],es[j],es[j+1],es[k],es[k+1]);
          if (candidate[0] < 0 || candidate[1] < 0 || candidate[0] > 500 || candidate[1] > 500)
            continue;
          candidates.push(candidate[0]);
          candidates.push(candidate[1]);
          if (better(candidate,es))
            bestcandidate = candidate.slice();
        }
      }
    }
  }
  //test corners
  for (var i=0; i<8; i+=2){
    for (var j=0; j<es.length-2; j+=2){
      for (var k=j+2; k<es.length; k+=2){
        var candidate = circumcenter(corners[i],corners[i+1],es[j],es[j+1],es[k],es[k+1]);
        if (candidate[0] < 0 || candidate[1] < 0 || candidate[0] > 500 || candidate[1] > 500)
          continue;
        candidates.push(candidate[0]);
        candidates.push(candidate[1]);
        if (better(candidate,es))
          bestcandidate = candidate.slice();
      }
    }
  }
  best = 0;
  return bestcandidate;
}

// SHOW RESULT ON CANVAS
var canvas = document.getElementById("canvas");
canvas.width = 500; canvas.height = 500;
context = canvas.getContext("2d");

//setInterval(function() {
  // CREATE TEST DATA
  context.clearRect(0, 0, canvas.width, canvas.height);
  candidates = [];

  var enemy = [];
  for (var i = 0; i < 8; i++) enemy.push(Math.round(Math.random() * 500));

  // RUN FUNCTION
  var result = f(enemy);

  for (var i = 0; i < 8; i+=2) {
    paintDot(context, enemy[i], enemy[i+1], 10, "red");
  }

  for (var i = 0; i < candidates.length; i+=2) {
    paintDot(context, candidates[i], candidates[i+1], 7, "green");
  }

  paintDot(context, result[0], result[1], 18, "blue");

  function paintDot(context, x, y, size, color) {
  context.beginPath();
  context.arc(x, y, size, 0, 6.2831853);
  context.closePath();
  context.fillStyle = color;
  context.fill();
  }
//},1500);

<BODY STYLE="margin: 0; border: 0; padding: 0;">
<CANVAS ID="canvas" STYLE="width: 200px; height: 200px; background: 
radial-gradient(rgba(255,255,255,0) 0, rgba(255,255,255,.15) 30%, rgba(255,255,255,.3) 32%, rgba(255,255,255,0) 33%) 0 0,
radial-gradient(rgba(255,255,255,0) 0, rgba(255,255,255,.1) 11%, rgba(255,255,255,.3) 13%, rgba(255,255,255,0) 14%) 0 0,
radial-gradient(rgba(255,255,255,0) 0, rgba(255,255,255,.2) 17%, rgba(255,255,255,.43) 19%, rgba(255,255,255,0) 20%) 0 110px,
radial-gradient(rgba(255,255,255,0) 0, rgba(255,255,255,.2) 11%, rgba(255,255,255,.4) 13%, rgba(255,255,255,0) 14%) -130px -170px,
radial-gradient(rgba(255,255,255,0) 0, rgba(255,255,255,.2) 11%, rgba(255,255,255,.4) 13%, rgba(255,255,255,0) 14%) 130px 370px,
radial-gradient(rgba(255,255,255,0) 0, rgba(255,255,255,.1) 11%, rgba(255,255,255,.2) 13%, rgba(255,255,255,0) 14%) 0 0,
linear-gradient(45deg, #343702 0%, #184500 20%, #187546 30%, #006782 40%, #0b1284 50%, #760ea1 60%, #83096e 70%, #840b2a 80%, #b13e12 90%, #e27412 100%);
background-size: 470px 470px, 970px 970px, 410px 410px, 610px 610px, 530px 530px, 730px 730px, 100% 100%;
background-color: #840b2a;"></CANVAS>
<!-- http://lea.verou.me/css3patterns/#rainbow-bokeh -->
</BODY>

Maybe you should slow down the animation a bit; now and then the choice of safe point doesn't seem optimal, but it takes more time to really judge it, especially with the green dots complicating the image. — m69's been on strike for years, Aug 13 '15 at 03:45

Aleksei Shestakov · Answer 6 · 2015-08-12T17:44:13.947

You can choose some random point at the grid and then move it iteratively from the enemies, here is my implementation in python:

from numpy import array
from numpy.linalg import norm
from random import random as rnd


def get_pos(enem):
    # chose random start position
    pos = array([rnd() * 500., rnd() * 500.])
    # make several steps from enemies
    for i in xrange(25):  # 25 steps
        s = array([0., 0.])  # step direction
        for e in enem:
            vec = pos - array(e)  # direction from enemy
            dist = norm(vec)  # distance from enemy
            vec /= dist  # normalize vector
            # calculate size of step
            step = (1000. / dist) ** 2
            vec *= step
            s += vec
        # update position
        pos += s
        # ensure that pos is in bounds
        pos[0] = min(max(0, pos[0]), 500.)
        pos[1] = min(max(0, pos[1]), 500.)
    return pos


def get_dist(enem, pos):
    dists = [norm(pos - array(e)) for e in enem]
    print 'Min dist: %f' % min(dists)
    print 'Avg dist: %f' % (sum(dists) / len(dists))

enem = [(0., 0.), (250., 250.), (500., 0.), (0., 500.), (500., 500.)]
pos = get_pos(enem)
print 'Position: %s' % pos
get_dist(enem, pos)

Output:

Position: [   0.          250.35338215]
Min dist: 249.646618
Avg dist: 373.606883

Finding the furthest point in a grid when compared to other points

6 Answers6