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

Question

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

10

我有一个大小可变但平均约为500x500的矩形网格，在其中只有少于5个x、y点。我需要找到一种算法，返回一个与任何其他点距离最远的x、y对。

上下文: 应用程序屏幕（网格）和一组x、y点（敌人）。玩家死亡后，我需要一个算法将它们重生得尽可能远离敌人，以便他们不会在重生后立即死亡。

目前已有的解决方案: 我编写的算法能够工作，但在较慢的手机上效果不佳。我基本上将网格分成正方形（就像井字游戏一样），并给每个正方形分配一个数字。然后我检查每个正方形与所有敌人之间的距离，并记录每个正方形最近的敌人是谁。具有最高数字的正方形是拥有最远敌人的正方形。我还尝试了对现有点求平均值并执行类似操作的方法，虽然性能可以接受，但该方法的可靠性却不高。

- Julian

1

如果你还没有这样做，尝试用deltax加deltay替换squareroot(deltax^2 + deltay^2)，这样应该会稍微提高你的性能。 - Roy Shahaf

1

一种方法可能是设置一些最小距离阈值，使新玩家必须远离所有敌人才能重新生成，然后生成随机点，直到其中一个满足该阈值。这不是最优的，但它会很快，并且可能足够好。 - Tony Tuttle

最近的敌人距离是否非常重要，或者如果其他敌人都远离自己，那么相对靠近一些是否可行？ - m69 ''snarky and unwelcoming''

@huck_cussler 那是个好主意，请把它发布为答案，因为它可能正是我正在寻找的。m69 是的，这很重要，因为这是一个快节奏的游戏。Roy Shahaf，还没有结果，谢谢！ - Julian

1

敌人最好的策略是组成一个半径为125*sqrt(2)的圆圈，围绕中心点收缩网格，然后在玩家生成到陷阱时将其紧缩。 - Colonel Panic

显示剩余2条评论

6个回答

0

这种方法从中心点查看所有敌人，检查它们所在的方向，找到最空的区域，然后返回通过该区域中心的一条线上的一个点，距离中心250个单位。
结果并不总是完美的，安全点也不在中心（虽然可以添加），但也许已经足够好了。

该算法在我的i5桌面上每秒运行超过一百万次，但手机可能无法处理三角函数。该算法对于每个敌人使用3个三角函数：atan2()、cos()和sin()。这些函数可能对执行速度产生最大影响。也许你可以用查找表替换cos()和sin()。

运行代码片段以查看随机位置敌人的示例。

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>

- m69 ''snarky and unwelcoming''

0

三角化敌人（少于5个？）；并将网格的每个角与最接近它的一对敌人进行三角化。其中一个三角形的外心应该是一个不错的重生点。

以下是JavaScript的示例。我使用了m69答案中的canvas方法进行演示。绿色点是测试候选项，以得出蓝色建议。由于我们正在三角化角落，因此它们在这里不作为解决方案提供（也许随机更接近的解决方案对玩家来说更令人兴奋？或者，也可以测试角落..）。

// https://dev59.com/BW855IYBdhLWcg3w3Ibr
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>

- גלעד ברקן

也许你应该稍微减慢动画速度；有时候安全点的选择似乎不太理想，但需要更多时间来真正判断，特别是绿点使图像变得更加复杂。 - m69 ''snarky and unwelcoming''

0

这与您已经在做的类似，但需要两次遍历，其中第一次遍历可以相当粗略。首先降低分辨率。将500x500网格划分为10x10个网格，每个网格为50x50。对于每个结果为100个子网格的子网格 - 确定哪些至少有一个敌人，并找到距离包含敌人的子网格最远的子网格。在此阶段，只需担心100个子网格。一旦找到距离敌人最远的子网格 - 增加分辨率。该子网格具有50x50 = 2500个正方形。使用这些正方形进行原始方法。结果是要处理的2600个正方形，而不是500x500 = 250,000个。（根据情况调整数字，如果没有500x500但采用相同的基本策略）。

这是Python3实现。它使用两个函数：

1) fullResSearch(a,b,n,enemies) 这个函数接受一组敌人，一个角落位置 (a,b) 和一个整数 n，并找到在以 (a,b) 为左上角的 nxn 位置正方形中具有最大最小距离到敌人的点。这些敌人不一定在这个 nxn 网格中（尽管它们肯定可以在其中）。

2) findSafePoint(n, enemies, mesh = 20) 这个函数接受一组敌人，假设它们在从(0,0)开始的nxn网格中。 mesh 确定子网格的大小，默认为20。整个网格被分成mesh x mesh 的子网格（如果mesh不能整除n，则沿边界略小），我把它们看作领土。如果一个领土里有敌人，我就称之为敌人领土。我创建敌人领土集合，并将其传递给参数为n除以mesh的fullResSearch函数。返回值给出了距离任何敌人领土最远的领土。这样的领土可以被认为是相当安全的。我将该领土反馈到fullResSearch中，以找到该领土中最安全的点作为整体返回函数。得到的点要么是最优的，要么是接近最优的，并且计算速度非常快。以下是代码（连同一个test函数）：

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))

一个典型的运行：

>>> 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)

我通过在整个网格上使用fullResSearch验证了(271,499)对于这些敌人确实是最优的。

- John Coleman

0

这里有一个有趣的解决方案，但我无法测试它的效率。对于每个敌人，从每个数字开始，以一递增，制作一条线。四条初始线将来自四个边缘，每次向外走一步，你就会创建另一条呈90度角出现的线，同时增加每个距离的数字。如果数字线遇到已经创建的比它小的数字，它不会覆盖它并停止扩展。实质上，这使得如果线找到比它小的数字，它将不会检查更多的网格标记，消除了需要检查所有敌人所在的整个网格的需求。

<<<<<<^^^^^^^
<<<<<<^^^^^^^
<<<<<<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++;
    }
}

}

这是我用来映射整个网格的代码。好处在于，检查/写入数字的次数并不太依赖于屏幕上敌人的数量。使用计数器和随机生成的敌人，我能够得到以下结果：124个敌人和1528537次检查，68个敌人和1246769次检查，15个敌人和795695次检查，500个敌人和1747452次检查。与您之前的代码相比，这是一个巨大的差异，因为您的代码会执行敌人数量*空间数量的检查。对于124个敌人，您将执行31000000次检查，而这个代码只执行了1528537次，少于通常所做的检查次数的5%。

- firereaction

我很好奇想看看我的代码与这个有什么区别，所以我试图将你的代码转化为JavaScript进行快速比较。对于maxX和maxY，您使用哪些值？ - m69 ''snarky and unwelcoming''

maxX和maxY是网格的尺寸。如果网格是500x500，则maxX为500，maxY为500。我使用了一个500x500的网格。您还可以在网格上运行每个敌人的地图，而不仅仅是其中一个。 - firereaction

这个优点是你也可以使用更粗的网格；这样你就可以选择你想要的精度或速度，或者介于两者之间。（很难计时，因为我必须在每次运行之间用初始值填充网格。） - m69 ''snarky and unwelcoming''

JavaScript版本在100x100的分辨率下，在i5桌面上大约需要3毫秒，仍然能够得到良好的结果。然而，在完整分辨率下，它需要近100毫秒。 - m69 ''snarky and unwelcoming''

这还取决于Julian在网格上有多少敌人。如果他的敌人很少，使用其他方法肯定更好，但这种方法的好处在于它的速度并不完全取决于敌人的数量，而是取决于网格的大小。我还是一个学生，所以我并没有期望它会那么高效。 - firereaction

显示剩余3条评论

0

你可以在网格中选择一些随机点，然后迭代地将其从敌人移开。这是我的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)

输出：

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

- Aleksei Shestakov

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- m69 ''snarky and unwelcoming'' · Accepted Answer

这是我能想到的最简单的算法，它仍然能够给出良好的结果。它只检查9个可能的位置：角落、边缘中心和中心点。大多数情况下，玩家最终会处于一个角落，但你显然需要更多的位置来对抗敌人。

该算法在我的i5桌面上运行时间为0.013毫秒。如果用Math.abs()替换Math.pow()，运行时间会降至0.0088毫秒，但结果可靠性会降低。（奇怪的是，这比使用三角函数的另一个答案要慢。）

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>