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?
fuente
Respuestas:
Esto es lo que haría:
fuente
Suponiendo que tiene un mapa hexadecimal de
n
celdas en total yp
jugadores, dondep <= 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:
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:
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.
fuente
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 (limitandon
a 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?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:
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.
fuente