Generar regiones iguales en un mapa hexadecimal

Tomando, por ejemplo, un mapa de hexágono grande (X por Y), ¿cómo puedo dividirlo en N regiones de hexágonos conectados para simular países?

El objetivo es generar un mapa hexadecimal que se vea como un mapa de la vida real con países con diferentes formas pero de igual tamaño.

¿Has probado el algoritmo de Lloyd ? El procedimiento es bastante simple y generará regiones de aspecto bastante regular (dependiendo de cuántas iteraciones ejecute).

1. Mosaico del mapa con hexágonos en blanco para comenzar.
2. Elige N hexes al azar. Estos representarán el "centro de masas" para cada país.
3. Etiquete cada hexágono con el hexágono central más cercano ( Diagrama de Voronoi ). El país i es el conjunto de todos los hexágonos más cercanos al i-ésimo hexágono central.
4. Calcule el nuevo centro de masa para cada país.
5. Repita los pasos 3 y 4 tantas veces como desee para suavizar las regiones generadas.

No tiene que ejecutarlo mucho tiempo para producir un mapa bonito. Este ejemplo requirió solo tres iteraciones.

Una forma sencilla de probarlo.

1. Selecciona al azar nhexágonos. Cada uno comenzará un grupo.
2. Para cada grupo, intente expandir el hex inicial en una dirección aleatoria.
3. Si todos los hexes alrededor del hex elegido están ocupados, marque como girado, cambie el hex.
4. Repita hasta que cada grupo tenga 20 hexágonos de largo o no tenga más espacio para expandirse (todos los hexágonos giraron).

No lo probé, pero esto debería generar islas y, de alguna manera, evitar llaves largas y delgadas. Además, lo más probable es que haya fronteras vecinas, pero no necesariamente cada una estará en contacto con la otra, esa densidad dependerá del valor de n.
Algunos grupos también pueden ser arrinconados por otros y alcanzar un tamaño inferior a 20, puede asegurar el espacio crecido al generar los hexes iniciales a una distancia mínima entre sí.
Pruebe y ajuste según sea necesario.


Además, no está relacionado con este problema pero es muy, muy útil para trabajar con hexes, visite esta página: http://www.redblobgames.com/grids/hexagons/#basics
Agrega un montón de información hexadecimal en un solo lugar con Un buen visual.

Definitivamente creo que algún tipo de estructura gráfica lo haría posible. Básicamente crea un borde entre dos nodos Hex si están uno al lado del otro para simular todo el mapa. Sin embargo, no estoy seguro del algoritmo exacto para generar un "país" dentro de ese mapa. La cuestión es que, dependiendo de cómo quiera que se "vea" el país, necesitaría diferentes algoritmos.

Desde la parte superior de mi cabeza, recomendaría elegir un punto y moverse hacia afuera desde allí, eligiendo un mosaico aleatorio dentro de su "país en crecimiento" que tiene un mosaico adyacente que no es parte del país.

Se podría usar un patrón de estrategia para cambiar los algoritmos según el tipo de país que desee. http://en.wikipedia.org/wiki/Strategy_pattern, es decir, ¿quieres un país de costa delgada como Chile? ¿O quieres algo más redondo y contenido?

Las propiedades del gráfico también pueden permitirle ajustar cómo desea que se vea el "país" final: http://en.wikipedia.org/wiki/Eccentricity_(graph_theory)

¿Quieres un país grande? Ajusta las propiedades del gráfico y obliga al país generado (que es solo un gráfico) a tener las propiedades que le dan un "aspecto" que querrás.

Por último, pero no menos importante, los gráficos también serán muy útiles para definir fronteras entre países. Podría crear un gráfico que tenga una conexión entre dos nodos si los países se limitan entre sí. Esto podría ser útil para algún tipo de partición en su juego y le permitirá posiblemente optimizar ciertas cosas más adelante en el desarrollo.

Una pequeña nota: usted dice 'parece un mapa de la vida real con países de diferentes formas pero de igual tamaño), pero los países' reales 'son muy diferentes en tamaño incluso dentro de ciertas regiones, incluso los países' grandes 'de Europa pueden variar enormemente, con, por ejemplo, Francia más del doble de Italia. Dicho esto, obviamente hay regiones de juego para tratar de mantener los tamaños más o menos iguales, ¡solo ten en cuenta que una pequeña variación aquí es probablemente algo bueno !

Mi enfoque inicial del problema sería 'evolucionar' (en lugar de 'crecer') sus regiones:

• Comience con una división concreta del mapa en trozos aproximadamente del mismo tamaño por líneas rectas (por ejemplo, si quisiera 6 países, entonces podría dividir el mapa en tres sectores horizontales y luego dividir cada uno de esos sectores 'en diagonal' en dos piezas) Obviamente, esto es fácil de hacer mediante programación, especialmente porque no tiene que ser muy exacto (de hecho, probablemente no debería ser muy exacto).
• Haga un pase inicial sobre la división, construyendo una estructura de datos 'límite': un conjunto de hexes que tienen algún vecino que actualmente pertenece a un país diferente. Este también sería un buen momento para contar la cantidad de hexágonos que hay en cada país.

Ahora, durante el tiempo que desee, ejecute el siguiente pseudocódigo:

Pick a random hex A from the boundary list;
Pick a random neighbor B of this hex from a different country;
if (A's country has more hexes than B's country has) {
  change hex A to belong to B's country;
} else if (B's country has more hexes than A's country has) {
  change hex B to belong to A's country;
} else {
  flip a coin to decide which to change;
}
if ( the changed hex's old country has become disconnected ) {
  undo and reject this move;
} else {
  update the boundary list around the changed hex and its neighbors;
}

Esto mantendrá un equilibrio aproximado entre el tamaño de cualquiera de los dos países vecinos, y el control 'desconectado' (que se puede hacer con un simple algoritmo de relleno de inundación) asegura que ningún país se separe en pedazos. La actualización de la lista de límites es una operación de tiempo constante: el hexadecimal modificado siempre seguirá estando en el límite, y puede verificar sus seis vecinos para ver si alguno de ellos se ha convertido en una celda de límite (porque su vecino ahora está en un país diferente) o dejó de ser una celda de límite (porque su vecino está en el mismo país ahora), modificando el conjunto de límites según sea necesario.

Para un refinamiento de este enfoque, incluso puede hacer que la condición de qué hexágono cambie un poco al azar, en lugar de siempre 'equilibrar' los dos países, siempre puede hacer el intercambio con una cierta probabilidad, e incluso disminuir gradualmente esa probabilidad sobre tiempo (similar al proceso de enfriamiento en un algoritmo de recocido simulado ) para comenzar a forzarlos a tener aproximadamente el mismo tamaño.

Tenga en cuenta que esto no garantizará que todas las áreas tengan exactamente el mismo tamaño (lo cual es imposible a menos que N divida perfectamente el tamaño de su cuadrícula de todos modos), y ni siquiera garantizará que todos los países estén dentro de un hexágono entre sí en el área; Sin embargo, debe garantizar (ejecutar suficientes iteraciones) que cada país no sea más de un hexágono más grande o más pequeño que cada uno de sus vecinos inmediatos.