Search code examples
javascriptalgorithmpath-finding

Closest coordinate around

I have hero coordinates, target coordinate and range.

Let's say my hero is at x: 1, y: 1;

Target coordinates are: x: 4, y: 4;

I'm getting every coordinate from target within range. So if range is 1 then I create array of objects like this:

[
    {x: 3, y: 3},
    {x: 4, y: 3},
    {x: 5, y: 3},
    {x: 3, y: 4},
    {x: 5, y: 4},
    {x: 3, y: 5},
    {x: 4, y: 5},
    {x: 5, y: 5}
]

just 1 sqm - 8 coordinates around target. I'm getting that with simple algorithm

const hero = {x: 1, y: 1};
const closest = {x: 4, y: 4};
const range = 1;
const coordsAround = [];


for (let i = 0; i <= range * 2; i++) {
  for (let j = 0; j <= range * 2; j++) {
    let newCoord = { x: closest.x - range + j, y: closest.y - range + i };
    //here note
    if(!((newCoord.x === 3 && newCoord.y === 3) || (newCoord.x === 4 && newCoord.y === 3))) {
      coordsAround.push(newCoord);  
    }
  }
}

but additionally before push to coordsAround I'm executing some function which check collisions. Here in example I just added if statement to simplify it a bit. And with this if I excluded 3,3 and 4,3.

So now my dashboard is like this:

enter image description here

( I accidently made this dashboard so it's in y,x pattern instead of x,y srr)

where pink is hero (1,1) red are collisions, gold is the target (4,4) and greens are around the target (gained from above code snippet)

Now it's pretty simple to say which green is closest if it would be without red tiles (collisions):

const realClosest = {
  x: hero.x > closest.x
    ? closest.x + 1
    : closest.x - 1,
  y: hero.y > closest.y
    ? closest.y + 1
    : closest.y - 1
};

console.log('real closest is:', realClosest, 'but it is not within coordsAournd:', coordsAround, 
           'so next closest coord is 3,4 or 4,3 but 3,4 is not within coordsAournd as well' +
            'so closest coord is 4,3');

but as far as I have this red tiles I don't know how to tell which is second best, third best and so on..

Solution

  • Sort the tiles with a custom function so that coordsAround[0] is the tile that is the closest to the hero, coordsAround[coordsAround.length - 1] is the tile that is thefarthest:

    function dist2(a, b) {
    let dx = a.x - b.x;
    let dy = a.y - b.y;

    return dx*dx + dy*dy;
}

coordsAround.sort(function (a, b) {
    let da = dist2(a, hero);
    let db = dist2(b, hero);

    if (da < db) return -1;
    if (da > db) return 1;
    return 0;
})

    The auxiliary function dist2 calculates the square of the distance. The sorting rder will be the same, because sqrt(x) < sqrt(y) when x < y (and both values are non--negative). Given that your range is reates a square, not a circly, you could also use dist = Math.max(Math.abs(dx), Math.abs(dy)).