Tengo una cuadrícula de mosaicos de un tamaño finito conocido que forma un mapa. Algunos de los mosaicos dentro del mapa se colocan en un conjunto conocido como territorio. Este territorio está conectado, pero no se sabe nada sobre su forma. La mayoría de las veces sería una gota bastante regular, pero podría ser muy alargada en una dirección y podría incluso tener agujeros. Estoy interesado en encontrar la frontera (exterior) del territorio.
Es decir, quiero una lista de todas las fichas que tocan una de las fichas en el territorio sin estar en el territorio. ¿Cuál es una forma eficiente de encontrar esto?
Para mayor dificultad, sucede que mis fichas son hexágonos, pero sospecho que esto no hace mucha diferencia, cada ficha aún está etiquetada con una coordenada entera x e y y, dada una ficha, puedo encontrar fácilmente a sus vecinos. A continuación hay algunos ejemplos: el negro es el territorio y el azul el borde que quiero encontrar.
Esto en sí mismo no es un problema difícil. Un algoritmo simple para esto, en pseudo-python, es:
def find_border_of_territory(territory):
border = []
for tile in territory:
for neighbor in tile.neighbors():
if neighbor not in territory and neighbor not in border:
border.add(neighbor)Sin embargo, esto es lento y me gustaría algo mejor. Tengo un bucle O (n) sobre el territorio, otro bucle (uno corto, pero aún) sobre todos los vecinos, y luego tengo que verificar la membresía en dos listas, una de las cuales es de tamaño n. Eso da una escala terrible de O (n ^ 2). Puedo reducir eso a O (n) mediante el uso de conjuntos en lugar de listas para la frontera y el territorio para que la membresía sea rápida de verificar, pero aún así no es genial. Espero que haya muchos casos en los que el territorio es grande pero el borde es pequeño debido a un área simple frente a una escala de línea. Por ejemplo, si el territorio es un hex de radio 5, es de tamaño 91 pero el borde es solo de tamaño 36.
¿Alguien puede proponer algo mejor?
Editar:
Para responder algunas de las preguntas a continuación. El territorio puede variar en tamaño, de aproximadamente 20 a 100 más o menos. El conjunto de mosaicos que forman el territorio es un atributo de un objeto, y es este objeto el que necesita un conjunto de todos los mosaicos de borde.
Inicialmente, el territorio se crea como un bloque, y luego gana principalmente fichas una por una. En este caso, es cierto que la forma más rápida es mantener un conjunto del borde y solo actualizarlo en el mosaico que se obtiene. Ocasionalmente, puede ocurrir un gran cambio en el territorio, por lo que será necesario volver a calcularlo completamente.
Ahora soy de la opinión de que hacer un algoritmo simple de búsqueda de bordes es la mejor solución. La única complejidad adicional que esto plantea es garantizar que el borde se recalcule cada vez que sea necesario, pero no más que eso. Estoy bastante seguro de que esto se puede hacer de manera confiable en mi marco actual.
En cuanto al tiempo, en mi código actual tengo algunas rutinas que necesitan verificar cada mosaico del territorio. No todos los turnos, sino en la creación y ocasionalmente después. Eso toma más del 50% del tiempo de ejecución de mi código de prueba, aunque es una parte muy pequeña del programa completo. Por lo tanto, estaba interesado en minimizar cualquier repetición. SIN EMBARGO, el código de prueba implica mucha más creación de objetos que una ejecución normal del programa (naturalmente), por lo que me doy cuenta de que esto podría no ser muy relevante.
fuente
Respuestas:
Encontrar un algoritmo generalmente se hace mejor con una estructura de datos que facilite el algoritmo.
En este caso, su territorio.
El territorio debe ser un conjunto desordenado (O (1) hash) de fronteras y elementos.
Cada vez que agrega un elemento al territorio, itera sobre mosaicos adyacentes y ve si deben ser un mosaico de borde; en este caso, son un mosaico de borde si no son un mosaico de elementos.
Cada vez que restas un elemento del territorio, te aseguras de que sus fichas adyacentes todavía estén en el territorio y ves si tú mismo deberías convertirte en una ficha de borde. Si necesita que esto sea rápido, haga que los mosaicos de borde hagan un seguimiento de su "conteo adyacente".
Esto requiere trabajo O (1) cada vez que agrega o elimina un mosaico hacia o desde un territorio. Visitar el borde toma O (longitud del borde). Siempre y cuando desee saber "cuál es la frontera" significativamente más a menudo que agregar / eliminar elementos del territorio, esto debería ganar.
fuente
Si necesita encontrar bordes de agujeros en el medio de su territorio también, entonces su lineal en el área del límite del territorio es lo mejor que podemos hacer. Cualquier azulejo en el interior podría ser un agujero que debemos contar, por lo que debemos mirar cada azulejo en el área delimitada por el contorno del territorio al menos una vez para asegurarnos de que hemos encontrado todos los agujeros.
Pero si solo le preocupa encontrar el borde exterior (no los agujeros interiores), entonces podemos hacerlo un poco más eficientemente:
Encuentra un borde que separe tu territorio. Puedes hacer esto ...
(si conoce al menos un mosaico de territorio y sabe que tiene exactamente un blob de territorio conectado en su mapa)
... comenzando en un mosaico arbitrario en su territorio, y avanzando hacia el borde más cercano de su mapa. Mientras lo hace, recuerde el último borde donde hizo la transición de un mosaico territorial a un mosaico no territorial. Una vez que llegue al borde del mapa, este borde recordado es su borde inicial.
Este escaneo es lineal en el diámetro del mapa.
o (si no sabe dónde están las fichas de su territorio por adelantado, o su mapa puede contener varios territorios desconectados)
... comenzando en el borde de su mapa, escanee a lo largo de cada fila hasta llegar a un mosaico de terreno. El último borde que cruzaste de no terreno a terreno es tu borde inicial.
Este escaneo podría ser, en el peor de los casos, lineal en el área del mapa (cuadrático en su diámetro), pero si tiene algún límite para restringir su búsqueda (por ejemplo, sabe que el territorio casi siempre cruza las filas del medio) puede mejorar esto peor. comportamiento del caso
Comenzando en el borde inicial que se encuentra en el paso 1, sígalo alrededor del perímetro de su terreno, agregando cada mosaico no terreno en el exterior a su colección de borde, hasta que regrese al borde inicial.
Este paso de seguimiento de bordes es lineal en el perímetro del contorno del terreno, en lugar de su área. La desventaja es que el código es más complicado porque debe tener en cuenta cada tipo de giro que puede tomar el borde y evitar el doble conteo de mosaicos de borde en las entradas.
Si sus ejemplos son representativos de su tamaño de datos real dentro de un par de órdenes de magnitud, entonces yo mismo buscaría la búsqueda de área ingenua: aún será increíblemente rápido en un número tan pequeño de mosaicos, y es sustancialmente más simple de escribir , entender y mantener (¡normalmente conduce a menos errores!)
fuente
darse cuenta : Si un mosaico está o no en el límite solo depende de él y sus vecinos.
Por eso:
Es fácil ejecutar esta consulta perezosamente. Por ejemplo: no es necesario buscar el límite en todo el mapa, solo en lo que es visible.
Es fácil ejecutar esta consulta en paralelo. De hecho, podría imaginar un código de sombreador que haga esto. Y si lo necesita para algo más que la visualización, puede renderizar a una textura y usarla.
Si un mosaico cambia, el límite solo cambia localmente, lo que significa que no necesita calcular todo nuevamente.
También puede calcular previamente el límite. Es decir, si está poblando el hexágono, puede decidir si un mosaico es el límite en ese momento. Eso significa que:
No use una lista para el límite. Use un conjunto si realmente tiene que hacerlo (no sé para qué quiere el límite ). Sin embargo, si hace que un mosaico sea límite o no un atributo del mosaico, entonces no tiene que ir a otra estructura de datos para verificar.
fuente
Mueva su área hacia arriba un mosaico, luego hacia arriba a la derecha, luego hacia abajo a la derecha, etc. Luego elimine el área original.
La fusión de los seis conjuntos debe ser O (n), ordenar O (n.log (n)), establecer la diferencia O (n). Si los mosaicos originales se almacenan en algún formato ordenado, el conjunto combinado también se puede ordenar en O (n).
No creo que haya un algoritmo con menos de O (n), ya que necesita acceder a cada mosaico al menos una vez.
fuente
Acabo de escribir una publicación de blog sobre cómo hacer esto. Esto usa el primer método que @DMGregory mencionó comenzando con una celda de borde y marchando alrededor del perímetro. Está en C # en lugar de Python, pero debería ser bastante fácil de adaptar.
https://dillonshook.com/hex-city-borders/
fuente
POSTE ORIGINAL:
No puedo comentar en este sitio, así que intentaré responder con un algoritmo de pseudocódigo.
Usted sabe que cada territorio tiene como máximo seis vecinos que son parte del límite. Para cada mosaico en el territorio, agregue los seis mosaicos vecinos a una posible lista de bordes. Luego reste cada mosaico en el territorio del borde y solo le quedan los mosaicos de borde. Funcionará mejor si usa un conjunto desordenado para almacenar cada lista. Espero haber sido útil.
EDITAR Hay formas mucho más efectivas que la iteración simple. Como intenté establecer en mi (ahora eliminada) respuesta a continuación, puede lograr O (1) en los mejores casos y O (n) en el peor de los casos.
Agregar un mosaico a un territorio O (1) - O (N):
En el caso de que no haya vecinos, simplemente crea un nuevo territorio.
En el caso de un vecino, agrega el nuevo mosaico al territorio existente.
En el caso de 5 o 6 vecinos, sabe que todo está conectado, por lo que agrega el nuevo mosaico al territorio existente. Estas son todas las operaciones O (1), y la actualización de los nuevos territorios fronterizos también es O (1), ya que es una simple fusión de un conjunto con otro.
En el caso de 2, 3 o 4 territorios vecinos, es posible que deba fusionar hasta 3 territorios únicos. Esto es O (N) en el tamaño del territorio combinado.
Eliminar una ficha de un territorio O (1) - O (N):
Con cero vecinos borrar el territorio. O (1)
Con un vecino, retire el azulejo del territorio. O (1)
Con dos o más vecinos, se pueden crear hasta 3 nuevos territorios. Esto es O (N).
Pasé mi tiempo libre durante las últimas semanas desarrollando un programa de demostración que es un simple juego de territorio basado en hexadecimal. Intenta aumentar tus ingresos colocando territorios uno al lado del otro. 3 jugadores, Rojo, Verde y Azul compiten para generar la mayor cantidad de ingresos colocando fichas estratégicamente en un campo de juego limitado.
Puedes descargar el juego aquí (en formato .7z) hex.7z
El control simple del mouse LMB coloca un mosaico (solo se puede colocar donde se resalta con el cursor). Puntuación en la parte superior, ingresos en la parte inferior. Vea si puede llegar a una estrategia efectiva.
El código se puede encontrar aquí:
Eagle / EagleTest
Para compilar desde el código fuente necesita Eagle y Allegro 5. Ambos compilan con cmake. El juego Hex se construye con el proyecto CB actualmente.
Ponga esos votos al revés. :)
fuente