Je suis en train de créer un simple jeu par navigateur basé sur une grille où je voudrais placer les joueurs et les cellules cibles (pensez au roi de la colline) de manière équidistante. L'idéal serait de faire en sorte que chaque joueur soit à égale distance de la cellule cible la plus proche.
Voici les conditions requises :
- Le jeu doit prendre en charge 2 à 20 joueurs .
- El
npormLa grille peut être toute taille mais plus elle est carrée, mieux c'est. (Le principe du "carré" est de réduire la distance maximale à parcourir à travers la grille - pour rendre les choses plus accessibles). - Le nombre de cellules cibles est flexible.
- Chaque joueur doit avoir un accès égal au même nombre de cibles.
- El minimum la distance entre un joueur ou une cible et tout autre joueur ou cible est 4 .
Notez que chaque cellule a 8 voisins immédiats (oui les diagonales comptent comme une distance de 1 ), et enveloppe des bords . Ce qui signifie que ceux du bas sont logiquement adjacents à ceux du haut, et de même pour la gauche et la droite.
J'ai essayé de penser à un bon algorithme pour placer les joueurs et les cibles dans des distributions variables sans avoir à créer une grille spécifique prédéterminée pour chaque nombre de joueurs. J'ai découvert clustering k-means y Algorithme de Lloyd's mais je ne les connais pas très bien et je ne sais pas vraiment comment les appliquer à ce cas précis, d'autant que le nombre de cellules cibles est flexible, ce qui devrait simplifier un peu la solution.
Voici un extrait de code très simplifié créant une grille prédéterminée de 6 joueurs, juste pour montrer l'essence de ce que je vise :
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();
}
}Il crée une grille qui ressemble à ceci : 
Où les cellules bleues sont les joueurs et les cellules rouges les cibles.
Quelqu'un a-t-il des suggestions sur la manière de procéder ?
Des liens vers des documents utiles seraient très appréciés.
Existe-t-il un gourou capable de créer un algorithme de placement génial qui satisfait à toutes les conditions susmentionnées ?
Ce serait AMAZING si la solution permet également de configurer le nombre de cellules cibles et/ou la distance minimale pour cualquier nombre de joueurs tout en satisfaisant à toutes les conditions, bien que cela ne soit pas strictement nécessaire.
EDIT
Après quelques autres considérations de game design, j'ai changé la distance minimale entre le joueur et la cible en 4 au lieu de 2 . Le texte, le code et l'image ci-dessus ont été modifiés en conséquence. Au moment de cette modification, aucune solution n'était contrainte par cette exigence, donc cela ne devrait rien changer.
EDIT 2
Si vous proposez une solution, veuillez fournir un code JavaScript (ou au moins un pseudo-code) décrivant les étapes détaillées de votre solution. Veuillez également expliquer comment la solution répond aux exigences. Nous vous remercions.
