将x项等距放置在n×m包裹网格上的算法

它创建一个如下所示的网格:

蓝色细胞是球员,红色细胞是目标.

有没有人对如何解决这个问题有任何建议？

非常感谢有用材料的链接.

是否有任何专家能够制作出满足上述所有条件的精彩放置算法？

如果解决方案还允许目标小区的数量和/或最小距离可以为任何数量的玩家配置并且仍然满足所有条件,那将是惊人的,尽管这不是绝对必要的.

经过其他一些游戏设计考虑后,我将玩家和目标之间的最小距离更改为4而不是2.上面的文本,代码和图像已相应更改.在编辑时,没有解决方案受到该要求的约束,因此它不应该影响任何事情.

如果您提出解决方案,请提供JavaScript代码(或至少伪代码),概述解决方案的详细步骤.另请说明解决方案如何满足要求.谢谢!

你被限制在一架平面上吗？如果可以移动到3D,则可以使用Fibonacci Spiral在球体上生成任意数量的等距点.在http://www.openprocessing.org/sketch/41142上有一个非常好的处理草图(带有代码).下图显示了它的外观.一个好处是你自动获得"包装".

如果你必须坚持使用2D,那么你可以尝试上面的方法,接着是一个保持映射的球面到平面的投影.这可能比你想要的要复杂一点......

一个直观的解决方案是根据玩家的数量对称地划分平面,随机放置一个玩家及其目标,然后在其他部分中对称地反映位置.理论上将网格绑定在一个圆圈中(反之亦然),然后划分和反射.

在(理论)无限分辨率网格中,以中心为极坐标系的中心,我们可以先放置一个玩家和它的目标(顺便说一下,这些可以放在网格上的任何位置,对称性仍然可以保持),然后放置其他n - 1玩家和目标/ s,360° / n每次增加初始程度,保持相同的半径.但是,由于您的网格将具有实际大小限制,因此您需要以某种方式保证反射单元格存在于网格上,可能是通过限制初始生成和/或修改网格大小/奇偶校验的组合.

有点像:

var numPlayers = 6;
var ts = 2;
var r = 8

function convertFromPolar(cs) {
  return [Math.round(cs[0] * Math.cos(cs[1] * Math.PI / 180)) + r
         ,Math.round(cs[0] * Math.sin(cs[1] * Math.PI / 180)) + r];
}

var first = [r,0];

var targets = [];
for (var i = 0; i < ts; i++) {
  var _first = first.slice();
  _first[0] = _first[0] - 4 - Math.round(Math.random() * 3);
  _first[1] = _first[1] + Math.round(Math.random() * 8);
  targets.push(_first);
}

var playerCells = [];
var targetCells = [];

for (var i = 0; i < numPlayers; i++) {
  playerCells.push(convertFromPolar(first).join('-'));
  first[1] = (first[1] + 360 / numPlayers) % 360;
  for (var j = 0; j < ts; j++) {
    targetCells.push(convertFromPolar(targets[j]).join('-'));
    targets[j][1] = (targets[j][1] + 360 / numPlayers) % 360;
  }
}

var cellSize = 20;
var canvas = document.createElement('canvas');
var ctx = canvas.getContext('2d');
document.body.appendChild(canvas);

function Cell(x, y) {
  this.x = x * cellSize + cellSize / 2;
  this.y = y * cellSize + cellSize / 2;
  this.id = x + '-' + y;
  this.neighbors = [];
  this.type = null;
}

Cell.prototype.draw = function() {
  var color = '#ffffff';
  if (this.type === 'base') {
    color = '#0000ff';
  } else if (this.type === 'target') {
    color = '#ff0000';
  } else if (this.type === 'outOfBounds') {
    color = '#000000';
  }
  var d = cellSize / 2;
  ctx.fillStyle = color;
  ctx.fillRect(this.x - d, this.y - d, this.x + d, this.y + d);
  ctx.rect(this.x - d, this.y - d, this.x + d, this.y + d);
  ctx.strokeStyle = '#000';
  ctx.lineWidth = 3;
  ctx.stroke();
};

var n = 24;
var m = 16;
canvas.width = n * cellSize + 6;
canvas.height = m * cellSize + 6;

var cellList = [];

for (var i = 0; i < n; i++) {
  for (var j = 0; j < m; j++) {
    var cell = new Cell(i, j);
    if (playerCells.indexOf(cell.id) > -1) {
      cell.type = 'base';
    } else if (targetCells.indexOf(cell.id) > -1) {
      cell.type = 'target';
    } else if (Math.pow(i - r,2) + Math.pow(j - r,2) > (r + 2)*(r + 2) ) {
      cell.type = 'outOfBounds';
    }
    cellList.push(cell);
  }
}

// Give each cell a list of it's neighbors so we know where things can move
for (var i = 0; i < cellList.length; i++) {
  var cell = cellList[i];
  var neighbors = [];

  // Get the cell indices around the current cell
  var cx = [cell.x - 1, cell.x, cell.x + 1];
  var cy = [cell.y - 1, cell.y, cell.y + 1];
  var ci, cj;

  for (ci = 0; ci < 3; ci++) {
    if (cx[ci] < 0) {
      cx[ci] = n - 1;
    }
    if (cx[ci] >= n) {
      cx[ci] = 0;
    }
    if (cy[ci] < 0) {
      cy[ci] = m - 1;
    }
    if (cy[ci] >= m) {
      cy[ci] = 0;
    }
  }
  for (ci = 0; ci < 3; ci++) {
    for (cj = 0; cj < 3; cj++) {
      // Skip the current node since we don't need to link it to itself
      if (cellList[n * ci + cj] === cell) {
        continue;
      }
      neighbors.push(cellList[n * ci + cj]);
    }
  }
}

drawGrid();

function drawGrid() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  for (var i = 0; i < cellList.length; i++) {
    cellList[i].draw();
  }
}

var numPlayers = 4;
var numTargets = numPlayers;
var gridSize = numPlayers * 4;
var minDistance = 4;

var targetPositions = [];
for (var i = 0; i < numTargets; i++) {
	// TODO: Make sure targets don't get too close
  targetPositions[i] = randomPos();
}

var heatMap = [];
for (var i = 0; i < gridSize; i++) {
  heatMap[i] = [];
  for (var j = 0; j < gridSize; j++) {
    heatMap[i][j] = heat(i, j);
  }
}
printHeat();

function heat(x, y) {
  var result = 0;
  for (var i in targetPositions) {
    var pos = targetPositions[i];
    result += 1 / distance(x - pos.x, y - pos.y); // XXX: What about zero division?
  }
  return result;
}

function distance(l1, l2) {
  // manhattan distance
  return Math.abs(l1) + Math.abs(l2);
}

function randomPos() {
  return {
    x: random(gridSize),
    y: random(gridSize),
    toString: function() {
      return this.x + '/' + this.y
    }
  };

  function random(max) {
    return Math.floor(Math.random() * max);
  }
}

function printHeat() {
  for (var i = 0; i < gridSize; i++) {
    var tr = $('');
    $('#heat').append(tr);
    for (var j = 0; j < gridSize; j++) {
      var heatVal = heatMap[i][j];
      var td = $(' ' + heatVal + ' ');
      if (heatVal > numTargets) // hack
        td.addClass('target');
      td.attr('data-x', i).attr('data-y', j);
      td.css('background-color', 'rgb(' + Math.floor(heatVal * 255) + ',160,80)');
      tr.append(td);
    }
  }
}

var cellsSorted = $('td').sort(function(a, b) {
  return numOfCell(a) > numOfCell(b);
}).toArray();
$('td').click(function() {
  $('.player').removeClass('player');
  var index = cellsSorted.indexOf(this);
  // TODO: Don't just search downwards, but in both directions with lowest difference
  for (var k = 0; k < numPlayers; k++) {
    var newIndex = index - k; // XXX Check against outOfBounds
    var cell = cellsSorted[newIndex];
    if (!validPlayerCell(cell)) {
      // skip one
      k--;
      index--;
      continue;
    }
    $(cell).addClass('player');
  }
});

function validPlayerCell(cell) {
  var otherItems = $('.player, .target').toArray();
  for (var i in otherItems) {
    var item = otherItems[i];
    var xa = parseInt($(cell).attr('data-x'));
    var ya = parseInt($(cell).attr('data-y'));
    var xb = parseInt($(item).attr('data-x'));
    var yb = parseInt($(item).attr('data-y'));
    if (distance(xa - xb, ya - yb) < minDistance)
      return false;
  }
  return true;
}

function numOfCell(c) {
  return parseFloat($(c).text());
}

body {
  font-family: sans-serif;
}

h2 {
  margin: 1ex 0;
}

td {
  border: 1px solid #0af;
  padding: 0.5ex;
  font-family: monospace;
  font-size: 10px;
  max-width: 4em;
  height: 4em;
  overflow: hidden;
  text-overflow: ellipsis;
}

td.target {
  border-color: #f80;
}

td.player {
  border-color: black;
}

td.player::after {
  font-family: sans-serif;
  content: "player here";
  position: absolute;
  color: white;
  background-color: rgba(0, 0, 0, 0.5);
  font-weight: bold;
  padding: 2px;
}

Click a cell to distribute players