以下是要求:
- 游戏需要支持2到20名玩家。 - n * m 网格可以是任何大小,但越“正方形”越好。 (“正方形”的原则是减少横跨网格所需的最大距离-使事物更易访问) - 目标单元格的数量是灵活的。 - 每个玩家应具有同等数量的目标的平等访问权。 - 任何玩家或目标与任何其他玩家或目标之间的最小距离为4。
请注意,每个单元格都有8个即时邻居(对角线也计算为距离1),并且边缘会包装。 这意味着底部的单元格在逻辑上与顶部的单元格相邻,左/右也是如此。
我一直在思考一个好的算法来在不需要为每个玩家数量创建特定预定网格的情况下,将玩家和目标放置在不同的分布中。我发现了 k-means clustering 和 Lloyd's Algorithm,但我对它们不是很熟悉,也不知道如何将它们应用到这个特定案例中,特别是因为目标单元格的数量是灵活的,我认为这应该会简化解决方案。
以下是一个大大简化的代码片段,创建一个预定的 6 个玩家网格,只是为了展示我要实现的目标的本质:
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();
}
}
有没有人对如何解决此问题有什么建议?
欢迎提供有用的材料链接。
是否有大师可以设计出符合所有条件的精彩放置算法?
如果该解决方案还允许配置任意数量的玩家的目标单元格和/或最小距离,并且仍然满足所有条件,那将是非常棒的,但这不是必须的。
编辑:在考虑其他游戏设计因素后,我将玩家和目标之间的最小距离从2改为4。上述文本、代码和图像已相应更改。在进行此次编辑时,没有任何解决方案受到该要求的限制,因此不会影响任何内容。
编辑2:
如果您提出了解决方案,请提供JavaScript代码(或至少是伪代码),详细说明解决方案的步骤。同时请解释该解决方案如何满足要求。谢谢!