Я создаю простую сетчатую браузерную игру, в которой я бы хотел разместить игроков и целевые ячейки (подумайте, что на вершине холма) на одинаковом расстоянии. В идеале это было бы сделано таким образом, чтобы каждый игрок также был одинаково удален от ближайшей целевой ячейки.
Вот требования:
- Игра должна поддерживать от 2 до 20 игроков.
- Сетка
nчерезmможет быть любого размера, но чем больше "квадрат", тем лучше. (Принцип "квадратный" заключается в уменьшении максимального требуемого расстояния для перемещения по сетке - держите вещи более доступными). - Количество целевых ячеек является гибким.
- Каждый игрок должен иметь равный доступ к одному и тому же числу целей.
- Расстояние минимальное между любым игроком или целью и любым другим игроком или мишенью 4.
Обратите внимание, что каждая ячейка имеет 8 ближайших соседей (да, диагонали считаются расстоянием 1) и обрезает края. Значения тех, что внизу, логически смежны с теми, что расположены вверху, и то же самое для левого/правого.
Я пытался придумать хороший алгоритм для размещения игроков и целей в разных дистрибутивах, не создавая определенную предварительно определенную сетку для каждого количества игроков. Я обнаружил k-означает кластеризацию и алгоритм Ллойда, но я не очень хорошо знаком с ними и не знаю, как применять их к этому конкретному случаю, особенно потому, что количество целевых ячеек является гибким, что, по моему мнению, должно немного упростить решение.
Вот фрагмент значительно упрощенного кода, создающего предварительно определенную сетку из 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 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();
}
}
