Menu
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.
408
Main Idea. The main idea behind this approach is that the most distance pair of points will be from the vertices of the convex hull of the given set of points, and the maximum distance we could get is equal to the diameter of that convex polygon.
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>If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
