Algorithm to place x items equidistantly on an n by m wrapping grid

Question

I'm creating a simple grid based browser game where I would like to place players and target cells (think king-of-the-hill) equidistantly. Ideally this would be done in such a way that each player would also be equally distant from the nearest target cell.

Here are the requirements:

• The game needs to support 2 to 20 players.
• The n by m grid can be any size, but the more 'square-like' the better. (The principle behind 'square-like' is to reduce the maximum required distance to travel across the grid - keep things more accessible)
• The number of target cells is flexible.
• Each player should have equal access to the same number of targets.
• The minimum distance between any player or target and any other player or target is 4.

Note that each cell has 8 immediate neighbors (yes diagonals count as a distance of 1), and edges wrap. Meaning those at the bottom are logically adjacent to those at the top, and same for left/right.

I've been trying to think of a good algorithm to place players and targets in varying distributions without having to create a specific pre-determined grid for each number of players. I discovered k-means clustering and Lloyd's Algorithm, but I'm not very familiar with them, and don't really know how to apply them to this specific case, particularly since the number of target cells is flexible, which I would think should simplify the solution a bit.

Here's a snippet of vastly simplified code creating a pre-determined 6 player grid, just to show the essence of what I'm aiming for:

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';    }    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();  };    // Pre-set player and target cells for 6 players as an example  var playerCells = ['0-0', '8-0', '16-0', '0-8', '8-8', '16-8'];  var targetCells = ['4-4', '12-4', '20-4', '4-12', '12-12', '20-12'];  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';      }      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();    }  }

It creates a grid that looks like this:

Where blue cells are players and red cells are targets.

Does anyone have any suggestions for how to go about this?

Links to helpful material would be greatly appreciated.

Are there any gurus out there who can drum up an awesome placement algorithm which satisfies all of the above conditions?

It would be AMAZING if the solution also allows the number of target cells and/or minimum distance to be configurable for any number of players and still satisfies all of the conditions, although that's not strictly necessary.

EDIT

After some other game design considerations, I changed the minimum distance between player & target to 4 instead of 2. The text, code, and image above have been changed accordingly. At the time of this edit, no solutions were constrained by that requirement, so it shouldn't affect anything.

EDIT 2

If you are proposing a solution, please provide JavaScript code (or at least pseudo-code) outlining the detailed steps of your solution. Also please explain how the solution meets the requirements. Thank you!

Answer 1

Are you constrained to a flat plane? If you can move to 3D, then you can use the Fibonacci Spiral to generate an arbitrary number of equidistant points on a sphere. There's a really nice processing sketch of this at work at http://www.openprocessing.org/sketch/41142 (with the code to go with it). The image below shows what it looks like. One benefit is that you automatically get the 'wrapping' included.

If you have to stick to 2D, then you could try the above followed by a spherical to planar projection that preserves the mapping. This may be a bit more complicated than you're looking for though...