与其他点相比，找到网格中最远的点
Finding the furthest point in a grid when compared to other points
我有一个大小可变的矩形网格，但平均为 500x500，其中包含少量 x,y 点（少于 5 个）。我需要找到一种算法，该算法 returns 一个 x,y 对，它离其他任何点都尽可能远。
上下文： 应用程序的屏幕（网格）和一组 x、y 点（敌人）。玩家死了，我需要一个算法让他们在远离敌人的地方重生，这样他们就不会在重生后立即死亡。
我目前所掌握的： 我编写的算法有效，但在较慢的手机上表现不佳。我基本上是将网格分成正方形（很像井字游戏），然后为每个正方形分配一个数字。然后我检查每个方格是否有所有敌人，并存储每个方格最近的敌人。数字最大的方格是距离最近的敌人最远的方格。我还尝试对现有点进行平均并做类似的事情，虽然性能可以接受，但该方法的可靠性却不行。
这与您已经在做的类似，但是有两遍，其中第一遍可能相当粗糙。首先降低分辨率。将 500x500 网格划分为 10x10 网格，每个网格为 50x50。对于生成的 100 个子网格中的每一个——确定哪些子网格至少有一个敌人，并找到距离包含敌人的子网格最远的子网格。在这个阶段，只有 100 个子网格需要担心。一旦找到离敌人最远的子网格——增加分辨率。该子网格有 50x50 = 2500 个正方形。用这些方块做你原来的方法。结果是要处理 50x50 + 100 = 2600 个方块，而不是 500x500 = 250,000 个。 （没有 500x500 但基本策略相同的情况下适当调整数字）。
这是一个 Python3 实现。它使用两个函数：
1) fullResSearch(a,b,n,enemies) 这个函数需要一组敌人，一个角位置 (a,b) 和一个整数，n，并在 nxn 个方格中找到一个点，其上-left hand corner 是 (a,b) 并找到该方格中与敌人具有最大最小距离的点。假设敌人不在这个 nxn 网格中（尽管他们肯定可以）
2) findSafePoint(n, enemies, mesh = 20) 此函数采用一组假定位于从 (0,0) 开始的 nxn 网格中的敌人。 mesh决定子网格的大小，默认为20。整个网格被分割成mesh x mesh个子网格（如果mesh没有，则沿着边界稍微变小divide n) 我认为是领土。如果其中有敌人，我将其称为敌方领土。我创建了一组敌方领土并将其传递给 fullResSearch，参数 n 除以 mesh 而不是 n。 return 值给出了距离任何敌方领土最远的领土。这样的领地，也算是比较安全的了。我将该区域反馈给 fullResSearch 以找到该区域中最安全的点作为整体 return 函数。结果点要么是最优的，要么是接近最优的，并且计算速度非常快。这是代码（连同 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）实际上是这些敌人的最佳选择）
这是一个有趣的解决方案，但我无法测试它的效率。对于每个敌人，根据每个数字制作一行数字，从 1 开始，随着距离的增加而增加 1。四个初始线将来自四个边缘，每次你再往外走一条，你就会创建另一条以 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++;
}
}
}
这是我用来绘制整个网格的代码。这样做的好处是，数字 checked/written 的次数不太依赖于屏幕上敌人的数量。使用计数器和随机生成的敌人，我能够得到这个：124 个敌人和 1528537 个检查，68 个敌人和 1246769 个检查，15 个敌人和 795695 500 个敌人和 1747452 个检查。与您之前的代码相比，这是一个巨大的差异，后者会处理敌人数量 * 空格数。
对于 124 个敌人，您已经完成了 31000000 次检查，而这却做了 1528537 次，不到正常检查次数的 5%。
此方法从中心点查看所有敌人，检查他们所在的方向，找到最空的扇区，然后 returns 通过该扇区中间的直线上的一个点，250远离中心。
结果并不总是完美的，安全点永远不会在中心（尽管可以添加），但也许已经足够好了。
该算法在我的 i5 台式机上每秒运行超过一百万次，但 phone 可能不适用于三角函数。该算法对每个敌人使用 3 个三角函数：atan2()、cos() 和 sin()。这些可能对执行速度的影响最大。也许您可以用查找 table 替换 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>
Triangulate 个敌人（少于 5 个？）；并用离它最近的一对敌人对网格的每个角进行三角测量。这些三角形之一的外心应该是重新生成的合适位置。
下面是 JavaScript 中的示例。我使用 m69 的答案中的 canvas 方法进行演示。绿点是经过测试以得出蓝色建议的候选人。由于我们对角进行三角测量，因此此处不提供它们作为解决方案（也许随机接近的解决方案对玩家来说可能会令人兴奋？或者，也只是测试角..）。
//
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>
这是我能想到的最简单的算法，但仍然能给出很好的结果。它只检查 9 个可能的位置：角、边的中间和中心点。大多数时候，玩家最终会被困在角落里，但显然你需要的位置比敌人多。
该算法在我的 i5 台式机上运行时间为 0.013 毫秒。如果将 Math.pow() 替换为 Math.abs()，则可以减少到 0.0088 毫秒，但显然结果不太可靠。 （奇怪的是，这比我使用三角函数的其他答案慢。）
运行 代码片段（重复）将显示 canvas 元素中随机放置的敌人的结果。
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>
你可以在网格上选择一些随机点，然后从敌人那里迭代移动它，这是我在 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
我有一个大小可变的矩形网格，但平均为 500x500，其中包含少量 x,y 点（少于 5 个）。我需要找到一种算法，该算法 returns 一个 x,y 对，它离其他任何点都尽可能远。
上下文： 应用程序的屏幕（网格）和一组 x、y 点（敌人）。玩家死了，我需要一个算法让他们在远离敌人的地方重生，这样他们就不会在重生后立即死亡。
我目前所掌握的： 我编写的算法有效，但在较慢的手机上表现不佳。我基本上是将网格分成正方形（很像井字游戏），然后为每个正方形分配一个数字。然后我检查每个方格是否有所有敌人，并存储每个方格最近的敌人。数字最大的方格是距离最近的敌人最远的方格。我还尝试对现有点进行平均并做类似的事情，虽然性能可以接受，但该方法的可靠性却不行。
这与您已经在做的类似，但是有两遍，其中第一遍可能相当粗糙。首先降低分辨率。将 500x500 网格划分为 10x10 网格，每个网格为 50x50。对于生成的 100 个子网格中的每一个——确定哪些子网格至少有一个敌人，并找到距离包含敌人的子网格最远的子网格。在这个阶段，只有 100 个子网格需要担心。一旦找到离敌人最远的子网格——增加分辨率。该子网格有 50x50 = 2500 个正方形。用这些方块做你原来的方法。结果是要处理 50x50 + 100 = 2600 个方块，而不是 500x500 = 250,000 个。 （没有 500x500 但基本策略相同的情况下适当调整数字）。
这是一个 Python3 实现。它使用两个函数：
1) fullResSearch(a,b,n,enemies) 这个函数需要一组敌人，一个角位置 (a,b) 和一个整数，n，并在 nxn 个方格中找到一个点，其上-left hand corner 是 (a,b) 并找到该方格中与敌人具有最大最小距离的点。假设敌人不在这个 nxn 网格中（尽管他们肯定可以）
2) findSafePoint(n, enemies, mesh = 20) 此函数采用一组假定位于从 (0,0) 开始的 nxn 网格中的敌人。 mesh决定子网格的大小，默认为20。整个网格被分割成mesh x mesh个子网格（如果mesh没有，则沿着边界稍微变小divide n) 我认为是领土。如果其中有敌人，我将其称为敌方领土。我创建了一组敌方领土并将其传递给 fullResSearch，参数 n 除以 mesh 而不是 n。 return 值给出了距离任何敌方领土最远的领土。这样的领地，也算是比较安全的了。我将该区域反馈给 fullResSearch 以找到该区域中最安全的点作为整体 return 函数。结果点要么是最优的，要么是接近最优的，并且计算速度非常快。这是代码（连同 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）实际上是这些敌人的最佳选择）
这是一个有趣的解决方案，但我无法测试它的效率。对于每个敌人，根据每个数字制作一行数字，从 1 开始，随着距离的增加而增加 1。四个初始线将来自四个边缘，每次你再往外走一条，你就会创建另一条以 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++;
}
}
}
这是我用来绘制整个网格的代码。这样做的好处是，数字 checked/written 的次数不太依赖于屏幕上敌人的数量。使用计数器和随机生成的敌人，我能够得到这个：124 个敌人和 1528537 个检查，68 个敌人和 1246769 个检查，15 个敌人和 795695 500 个敌人和 1747452 个检查。与您之前的代码相比，这是一个巨大的差异，后者会处理敌人数量 * 空格数。 对于 124 个敌人，您已经完成了 31000000 次检查，而这却做了 1528537 次，不到正常检查次数的 5%。
此方法从中心点查看所有敌人，检查他们所在的方向，找到最空的扇区，然后 returns 通过该扇区中间的直线上的一个点，250远离中心。
结果并不总是完美的，安全点永远不会在中心（尽管可以添加），但也许已经足够好了。
该算法在我的 i5 台式机上每秒运行超过一百万次，但 phone 可能不适用于三角函数。该算法对每个敌人使用 3 个三角函数：atan2()、cos() 和 sin()。这些可能对执行速度的影响最大。也许您可以用查找 table 替换 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>
Triangulate 个敌人（少于 5 个？）；并用离它最近的一对敌人对网格的每个角进行三角测量。这些三角形之一的外心应该是重新生成的合适位置。
下面是 JavaScript 中的示例。我使用 m69 的答案中的 canvas 方法进行演示。绿点是经过测试以得出蓝色建议的候选人。由于我们对角进行三角测量，因此此处不提供它们作为解决方案（也许随机接近的解决方案对玩家来说可能会令人兴奋？或者，也只是测试角..）。
//
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>
这是我能想到的最简单的算法，但仍然能给出很好的结果。它只检查 9 个可能的位置：角、边的中间和中心点。大多数时候，玩家最终会被困在角落里，但显然你需要的位置比敌人多。
该算法在我的 i5 台式机上运行时间为 0.013 毫秒。如果将 Math.pow() 替换为 Math.abs()，则可以减少到 0.0088 毫秒，但显然结果不太可靠。 （奇怪的是，这比我使用三角函数的其他答案慢。）
运行 代码片段（重复）将显示 canvas 元素中随机放置的敌人的结果。
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>
你可以在网格上选择一些随机点，然后从敌人那里迭代移动它，这是我在 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