javascript - todos - Algoritmo para colocar x elementos equidistantemente en una cuadrícula de envoltura n por m
punto equidistante entre 2 puntos formula (5)
Estoy creando un simple juego de navegador basado en la red en el que me gustaría ubicar jugadores y células objetivo (pensar en el rey de la colina) de forma equidistante. Idealmente, esto se haría de tal manera que cada jugador estaría igualmente distante de la celda objetivo más cercana.
Aquí están los requisitos:
- El juego debe ser compatible con 2 a 20 jugadores .
- La cuadrícula de
npormpuede ser de cualquier tamaño , pero cuanto más "cuadrada", mejor. (El principio detrás de ''cuadrado'' es reducir la distancia máxima requerida para viajar a través de la cuadrícula - mantener las cosas más accesibles) - La cantidad de celdas objetivo es flexible.
- Cada jugador debe tener el mismo acceso a la misma cantidad de objetivos.
- La distancia mínima entre cualquier jugador u objetivo y cualquier otro jugador u objetivo es 4 .
Tenga en cuenta que cada celda tiene 8 vecinos inmediatos (sí, las diagonales cuentan como una distancia de 1 ) y que los bordes se envuelven . Lo que significa que los que están en la parte inferior son lógicamente adyacentes a los de arriba, y lo mismo para los de izquierda / derecha.
He estado tratando de pensar en un buen algoritmo para ubicar jugadores y objetivos en diferentes distribuciones sin tener que crear una grilla predeterminada específica para cada número de jugadores. Descubrí el clúster k-means y el algoritmo de Lloyd , pero no estoy muy familiarizado con ellos, y realmente no sé cómo aplicarlos a este caso específico, sobre todo porque el número de células objetivo es flexible, lo que creo que debería simplifica la solución un poco.
Aquí hay un fragmento de código simplificado que crea una cuadrícula predeterminada de 6 jugadores, solo para mostrar la esencia de lo que estoy buscando:
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();
}
}
Crea una grilla que se ve así:
Donde las celdas azules son jugadores y los glóbulos rojos son blancos.
¿Alguien tiene alguna sugerencia sobre cómo hacer esto?
Los enlaces a material útil serían muy apreciados.
¿Hay gurús por ahí que puedan utilizar un increíble algoritmo de ubicación que satisfaga todas las condiciones anteriores?
Sería INCREÍBLE si la solución también permite que el número de celdas objetivo y / o la distancia mínima sean configurables para cualquier número de jugadores y aún así cumpla con todas las condiciones, aunque eso no es estrictamente necesario.
EDITAR
Después de algunas otras consideraciones de diseño del juego, cambié la distancia mínima entre el jugador y el objetivo a 4 en lugar de 2 . El texto, el código y la imagen de arriba se han cambiado en consecuencia. En el momento de esta edición, ninguna solución se vio limitada por ese requisito, por lo que no debería afectar nada.
EDIT 2
Si está proponiendo una solución, proporcione código JavaScript (o al menos pseudocódigo) que describa los pasos detallados de su solución. También explique cómo la solución cumple con los requisitos. ¡Gracias!
¿Estás obligado a un plano plano? Si puede pasar a 3D, puede usar la Espiral de Fibonacci para generar una cantidad arbitraria de puntos equidistantes en una esfera. Hay un bosquejo de procesamiento muy bueno de esto en el trabajo en http://www.openprocessing.org/sketch/41142 (con el código para ir con él). La imagen a continuación muestra cómo se ve. Una ventaja es que automáticamente se incluye el ''envoltorio''.
Si tiene que apegarse a 2D, puede probar lo anterior seguido de una proyección esférica a plana que preserve la asignación. Esto puede ser un poco más complicado de lo que estás buscando ...
Como ya se dijo, probablemente no haya una solución perfecta que cumpla con todos sus requisitos exactamente sin gastos de cálculo exorbitantes. 1
Enfoque
Mi enfoque sería reemplazar la misma distancia a todos los requisitos de objetivos por una condición más flexible.
En el siguiente ejemplo, introduje una propiedad de calor para cada celda, que debe representar intuitivamente la disponibilidad / proximidad de los objetivos. Se calcula sumando calor en relación con cada objetivo en el mapa. El calor de en relación con un objetivo es simplemente 1 dividido por la distancia (manhattan en mi ejemplo) entre ellos. Tal vez querrás usar diferentes implementaciones para las funciones de heat y distance .
Posicionamiento del jugador
Para distribuir jugadores, hacemos lo siguiente:
- Mantenga una lista de todas las celdas, ordenadas por calor
- Comience en alguna celda (actualmente seleccionada por el usuario), búsquela en la lista ordenada y use sus vecinos (con valores de calor similares) para las posiciones de los jugadores.
Esto asegura que los valores de calor para las celdas de jugador estén siempre lo más cerca posible. Una solución aún mejor sería buscar una secuencia de valores de calor similares a los posibles en la lista ordenada y usarlos.
Código de ejemplo
Recargar para tener diferentes posiciones de destino
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 = $(''<tr>'');
$(''#heat'').append(tr);
for (var j = 0; j < gridSize; j++) {
var heatVal = heatMap[i][j];
var td = $(''<td> '' + heatVal + '' </td>'');
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;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<h2>Click a cell to distribute players</h2>
<table id="heat">
</table>
Lo mismo en JSFiddle para jugar con las variables
Extremos abiertos
Este ejemplo ha sido cosido bastante rápido. Notará que hay varios extremos abiertos y casos de esquina descubiertos. Acabo de llegar para delinear mi idea.
Descubierto:
- Envoltura en los bordes: esto probablemente solo afecte a la función
dist - Distancia entre los objetivos: simplemente son lanzados al azar en algún lugar del mapa
- La selección de posiciones simplemente busca hacia abajo la lista de
heat: esto podría hacerse de manera más inteligente, por ejemplo, la distancia más corta a la celda seleccionada original - Distribución automática de jugadores (sin hacer clic): es posible que desee tomar uno al azar para comenzar con
1 Quiero decir, teóricamente podrías probar todas las variaciones posibles y verificar si son correctas (si tienes un gran grupo en tu patio trasero).
Creo que la distancia no puede ser exactamente la misma para cada jugador en cada combinación, por lo que desea crear una configuración que minimice las injusticias entre los jugadores.
¿Conoces la ley de Hooke para cuerdas? Me imagino una situación en la que todos los jugadores y objetivos están conectados con cadenas comprimidas que se desplazan proporcionalmente a la distancia actual (con wraps). Deje que el sistema evolucione desde una configuración inicial particular, incluso si no es la más bella, sino solo una conjetura inicial. La ventaja es que no necesitarás fuerza bruta, simplemente deja que se ajuste solo.
Para aumentar las posibilidades de convergencia, deberá implementar fricción / arrastre. He estado trabajando con simulaciones de física, es por eso que escribí esta respuesta.
La desventaja es que tal vez exija demasiado esfuerzo de investigación antes de la implementación, que usted estaba tratando de evitar ya que mencionó que no estaba familiarizado con dichos algoritmos.
Tal vez me esté perdiendo algo, pero ¿no puedes simplemente hacer la cuadrícula como N copias de una ubicación aleatoria dentro de los límites ( N es la cantidad de jugadores)?
Define `p = (x,y)` as first player location
Make target/s randomly for `p` at least 4 cells away and
within either a horizontal or vertical rectangular limit
Now define the grid as (N - 1) copies of the rectangle with space added
so as to make the regtangles form a square (if that''s the final shape you want),
and observe minimum distance from other players
Como cada rectángulo es exactamente el mismo, cada jugador tiene el mismo acceso a la misma cantidad de objetivos.
Una solución intuitiva que viene a la mente es dividir el avión simétricamente de acuerdo con la cantidad de jugadores, colocar un jugador y su objetivo / s aleatoriamente y luego reflejar la ubicación simétricamente en las otras secciones. Enlaza teóricamente la cuadrícula en un círculo (o viceversa), luego divide y refleja.
En una cuadrícula de resolución infinita (teórica), con su centro como el centro de un sistema de coordenadas polares, primero podríamos ubicar a un jugador y sus objetivos (por cierto, estos se pueden colocar en cualquier lugar de la cuadrícula y la simetría seguirá siendo válida) ), luego para colocar los otros n - 1 jugadores y objetivo / s, incremente el grado inicial 360° / n cada vez, manteniendo el mismo radio. Sin embargo, dado que su cuadrícula tendrá un límite de tamaño práctico, deberá garantizar de alguna manera que las celdas reflejadas existen en la cuadrícula, tal vez mediante una combinación de restricción de la generación inicial y / o modificación del tamaño / paridad de la cuadrícula.
Algo como:
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();
}
}