¿Cómo dividir la cuadrícula hexadecimal de manera uniforme entre n jugadores?

15

Estoy haciendo un juego simple basado en la cuadrícula hexadecimal, y quiero que el mapa se divida equitativamente entre los jugadores. El mapa se crea al azar, y quiero que los jugadores tengan aproximadamente la misma cantidad de celdas, con áreas relativamente pequeñas. Por ejemplo, si hay cuatro jugadores y 80 celdas en el mapa, cada uno de ellos tendría unas 20 celdas (no tiene que ser preciso). Además, cada jugador no debe tener más de cuatro celdas adyacentes. Es decir, cuando se genera el mapa, los "fragmentos" más grandes no pueden tener más de cuatro celdas cada uno.

Sé que esto no siempre es posible para dos o tres jugadores (ya que esto se parece al problema de "colorear el mapa"), y estoy de acuerdo con hacer otras soluciones para ellos (como crear mapas que resuelvan el problema). Pero, para cuatro u ocho jugadores, ¿cómo podría abordar este problema?

Manábreak
fuente
El autómata celular es una forma simple, similar a esto: un mapa simple, cuatro biomas y cómo distribuirlos
MichaelHouse

Respuestas:

3

Esto es lo que haría:

  1. Asigna todas las celdas a jugadores aleatorios. En los mapas grandes, es muy probable que esto produzca un número bastante par de fichas para todos los jugadores, en mapas más pequeños probablemente tendrá que hacer algunas correcciones.
  2. Rompe trozos que sean demasiado grandes. Lo más fácil sería tomar todos los mosaicos en fragmentos y nuevamente asignarlos al azar.
  3. En el caso de un número desequilibrado de celdas (por ejemplo, el jugador A tiene 24 celdas, el jugador B tiene 16), reasigne un par de celdas de jugadores sobrerrepresentados a jugadores subrepresentados.
  4. Verifique nuevamente si hay trozos. Si el paso 3 introdujo nuevos fragmentos, vuelve al paso 2. Si no, ¡buen mapa!
Junuxx
fuente
PD: No creo que este problema sea imposible, el problema de color del mapa es bastante diferente (por un lado, es al revés, formas-> colores en lugar de colores-> asignaciones de mosaicos).
Junuxx
Me gusta bastante este enfoque, pero ¿no existe la posibilidad de que se ejecute durante mucho tiempo, tratando de equilibrar los tamaños de área?
Manabreak
1
@manabreak: hice algo para probarlo. Con un pequeño cambio en el paso 2 (reasignar recorriendo todos los jugadores en lugar de reasignar al azar) funciona bastante bien. Intentaré escribirlo cuando tenga tiempo.
Junuxx
1
Eso se ve exactamente lo que estaba buscando. :)
manabreak
1

Suponiendo que tiene un mapa hexadecimal de nceldas en total y pjugadores, donde p <= n, la mejor manera de abordar esto es a través de la distribución por turnos mediante autómatas celulares (CA).

Inicialización

Aleatoriamente (y / o usando alguna u otra heurística, como la distancia desde el centro del mapa) elige una celda inicial para cada jugador. Desde entonces p <= n, esto no debería ser un problema.

Autómata celular

Necesita una conectividad completa entre sus celdas hexadecimales. Sugeriría una matriz de 6 vecinos por celda:

class Cell
{
   //... other members...
   Cell[6] neighbours = new Cell[6];
}

El uso de matrices de tamaño fijo permite que exista el concepto de direcciones topográficas entre celdas, lo que no existiría en una lista o vector. Recomiendo esto, ya que puede facilitar ciertas operaciones de navegación.

También puede almacenar su mapa hexadecimal en una matriz 2D, con desplazamientos por fila. Sin embargo, esto puede ser un poco menos intuitivo que almacenar una matriz vecina por celda, solo debido al desplazamiento geométrico en cada otra fila.

Asegúrese de que cada celda esté conectada a todo lo que sea vecino. Puede hacerlo fila por fila, celda por celda a medida que genera el mapa hexadecimal completo. PD Si finalmente desea un mapa hexadecimal acotado no rectangularmente, simplemente puede eliminar celdas individuales y referencias a esas celdas, para formar espacios negativos, lo que le permite crear un esquema de mapa orgánico.

Distribución round-robin

Pseudocódigo:

count number of neutral cells in entire map, minus those starting cells taken by players
while neutral cells remain (or while true)
   for each player
      if player has not yet reached expected territory size in cells
         for each cell already constituting this player's territory
           if territory can grow by one cell into a neutral neighbour
              grow into neighbour
              reduce neutral cell count for entire map by one
              if no more neutral cells remain in map
                 break out of outermost while loop immediately
              else
                 continue to next player immediately
begin game

Este algoritmo le dará a cada jugador la oportunidad de hacer crecer su territorio en uno, en una forma de todos contra todos, siempre que el territorio del jugador todavía tenga un espacio de crecimiento válido. Si ciertos jugadores están bloqueados aumente aún más, el algoritmo a pesar de esto seguirá creciendo los territorios de los jugadores que no todavía tienen espacio de crecimiento válida. Podrías restringir fácilmente a cada jugador a la misma cantidad de celdas tan pronto como una de ellas llegue al límite, pero eso debería ser lo suficientemente fácil para que lo descubras, si lo deseas.

Esto proporcionará "territorios de origen" de tamaño máximo para cada jugador. Si quieres tener territorios de "islas" además, para cumplir con la cuota de conteo de células para ese jugador, una vez que un jugador se queda sin espacio local para crecer, puedes elegir una nueva celda de inicio de la lista de celdas neutrales y proceder con el mismo proceso de "crecimiento", a partir de ahí. De esta manera, terminarás con conjuntos de islas coherentes de buen tamaño para cada jugador, en lugar de ruido aleatorio.

Ingeniero
fuente
Si bien proporciona una excelente documentación y pseudocódigo para su algoritmo, no estoy seguro de que coincida con lo que pregunta el interrogador. La pregunta menciona que "los" fragmentos "más grandes no pueden tener más de cuatro celdas cada uno", mientras que su algoritmo crea un grupo conectado tan grande como sea posible.
fnord
@fnord No, no lo hace. No leíste mi respuesta correctamente. Puse explícitamente un límite en el pseudocódigo: "si el jugador aún no ha alcanzado el tamaño de territorio esperado en las celdas". Por favor, elimine su voto negativo. No dude en consultar el historial de revisiones de la pregunta para asegurarse de que este fue el caso desde antes de su comentario y voto negativo.
Ingeniero
La pregunta pide tener "no más de cuatro celdas adyacentes", pero que cada usuario tenga una porción esperada del mapa. Esto, para mí, implica que vamos por algo más parecido a cómo los juegos de Riesgo distribuyen aleatoriamente el mapa para todos los jugadores. Su respuesta divide el mapa en "territorios de origen" de tamaño máximo ". Es cierto, su algoritmo se detiene cuando se alcanza el límite de tamaño de territorio esperado, pero no veo una manera para que ese jugador obtenga nuevas "islas", aunque lo menciona en un texto posterior.
fnord
@fnord Tu lógica tiene la culpa. En su oración final, admite que mi algoritmo se detiene en el tamaño de la isla n, y luego se contradice diciendo que "no ve un camino" pero que sí "menciono [cómo obtener islas] en el texto posterior". ¿He respondido o no he respondido la pregunta? Este algoritmo generalizado puede usarse para dispersar celdas (limitando na 1) o para crear islas (configurando n> 1). Entonces, en un solo algoritmo, no solo tiene la capacidad de dispersarse, sino también de agrupar. ¿Cómo no responde esto a la pregunta del OP? ¿Cómo es digno de un voto negativo?
Ingeniero
Editaría mi comentario anterior, pero es demasiado tarde. "No veo una manera en su algoritmo ". aunque mencionas el concepto en un texto posterior.
fnord
0

Otro enfoque sería comenzar con una distribución que sea `` justa '' pero regular, y luego usar un método similar al Recocido Simulado para romper la regularidad sin perder la equidad:

  • Comience asignando colores a todas las celdas de su cuadrícula en un patrón regular (por ejemplo, tenga un patrón '123412341234' repetido en la primera fila, seguido de '341234123412' en la siguiente, etc.). Esto puede conducir a una distribución no uniforme de colores si su mapa tiene una forma particularmente pobre, pero supongo que está comenzando con un mapa fijo, por lo que debería poder encontrar un color regular equidistribuido.
  • Luego repita lo siguiente para todos los pasos que desee (no existe un criterio real de "cocción", por lo que la experimentación le dirá cuál es un número mínimo razonable de pasos):
    • Elige dos elementos de la cuadrícula al azar
    • Si tienen el mismo color, inténtalo de nuevo (de lo contrario, no tiene sentido, ya que el intercambio no será operativo. Solo tienes una probabilidad de 1/4 de golpear el mismo color y una probabilidad de 1/16 de golpear el mismo color dos veces seguidas, por lo que nunca debería volver a intentarlo demasiado)
    • Intercambia provisionalmente los colores de esos dos elementos.
    • Pruebe los tamaños de las regiones recién formadas en las ubicaciones de los elementos después del intercambio:
      • haga un simple relleno de inundación hacia afuera desde el nuevo punto de cada elemento para determinar qué tan grande sería la región de ese color que haría el intercambio.
    • Si cualquiera de estas dos regiones es mayor que su umbral, deshaga el intercambio provisional; de lo contrario, 'finalice' el intercambio de los colores de los dos elementos.

Las claves aquí son que el hecho de que estás intercambiando dos puntos significa que nunca desequilibrarás los colores, y de la misma manera la prueba que haces antes de finalizar tu intercambio asegura que nunca crees regiones que sean demasiado grandes. Si tiene algún medio para mostrar su cuadrícula, incluso podría visualizar este proceso para ver cómo 'construye' sus regiones a través de los intercambios repetidos.

Si, por cierto, no puede comenzar con una coloración regular equidistribuida, entonces aún debería ser capaz de hacer algo similar para distribuir la coloración: mientras su coloración no está equidistribuida, elija un elemento al azar; luego, si es uno de los colores sobrerrepresentados, establezca provisionalmente su color en uno de los colores subrepresentados y luego verifique que no se cree una región demasiado grande del nuevo color.

Steven Stadnicki
fuente
Los enfoques estocásticos son ineficientes. Para un enfoque como el mío que toma pasos considerados, el tiempo de ejecución se aproxima a O (n) para n celdas de mapa. Para su algoritmo, es O (n * m), donde m es el número de celdas deseadas por isla (en realidad, para cada isla potencial). Siempre es mejor apuntar a algoritmos que tengan un tiempo de ejecución fácilmente estimable. En lugar de arreglar un mapa generado al azar, es mejor generar un mapa que no esté roto o al azar en primer lugar, en n pasos, manteniendo así un proceso controlado y eficiente.
Ingeniero