与其他点相比,找到网格中的最远点

Question

与其他点相比,找到网格中的最远点

我有一个可变大小的矩形网格,但平均为500x500,其中包含少量的x,y点(小于5).我需要找到一个返回x,y对的算法,该算法距离任何其他点最远.

上下文:应用程序的屏幕(网格)和一组x,y点(敌人).玩家死了,我需要一种能够远离敌人重新生成它们的算法,以便它们在重生后不会立即死亡.

到目前为止我所拥有的:我编写的算法有效但在较慢的手机中表现不佳.我基本上将网格划分为正方形(很像tic tac toe),并为每个正方形分配一个数字.然后我检查每个方格对抗所有敌人并存储每个方格最近的敌人.数量最多的广场是距离最近的敌人最近的广场.我也尝试对现有点进行平均并做类似的事情,虽然性能可以接受,但方法的可靠性却没有.

Answer 1

m69*_*g'' 2

这是我能想到的最简单的算法，但仍然给出了很好的结果。它只检查 9 个可能的位置：角、边的中间和中心点。大多数时候，玩家都会陷入角落，但显然你需要比敌人更多的位置。

该算法在我的 i5 桌面上运行时间为 0.013 毫秒。如果将 Math.pow() 替换为 Math.abs()，则时间会降至 0.0088ms，但结果显然不太可靠。（奇怪的是，这比我使用三角函数的其他答案慢。）

（重复）运行代码片段将在画布元素中显示随机定位的敌人的结果。

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();
}

Run Code Online (Sandbox Code Playgroud)

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

Run Code Online (Sandbox Code Playgroud)

归档时间：	10 年，2 月前
查看次数：	869 次
最近记录：	10 年，2 月前