¿Cómo puedo encontrar un muro procesal que separe dos o más puntos en un mapa basado en cuadrícula?

8

Estoy tratando de generar muros que corten un punto dado de otros puntos dados. La imagen adjunta muestra el tipo de cosas que busco:

ingrese la descripción de la imagen aquí

  1. Azul separado del rojo.
  2. Azul separado del rojo y amarillo.
  3. Azul separado del rojo con obstrucciones de azulejos.
  4. Múltiple Azul separado de Múltiple Rojo.

¿Alguna idea de como hacer esto?

IanLarson
fuente
1
Esto es un poco demasiado amplio ... ¿desea minimizar el área azul, o tal vez desea un área igual, o tal vez el área no importa, pero desea minimizar la longitud de la pared, o tal vez todo lo que sea irrelevante? y lo que realmente importa es encontrar una solución rápida ... etc
Theraot
1
Para darle a usted, u otros, una posible dirección, esto suena relacionado con una variante de "manhattan distance voronoi" dependiendo de la apariencia que esté buscando o simplemente voronoi regular.
Sirisian
De acuerdo con los otros dos comentarios, mi primer pensamiento fue "hay un número infinito de soluciones". Donde "infinito" puede no ser infinito por arbitrariamente grande. No hay restricciones sobre lo que permite esto y no esto .
Draco18s ya no confía en SE
Perdón por no ser más específico. Realmente, el único requisito estricto era que la pared separara los puntos dados, lo que sí sé que tiene soluciones casi infinitas. Las imágenes que proporcioné en realidad no tenían la intención de ser algo más que una idea general de lo que estaba tratando de hacer, por lo que su edición, Draco, sería un resultado perfectamente válido para mis propósitos. Estaba buscando el tipo de métodos que producirían ese tipo de resultados, incluso si hay una gran cantidad de resultados.
IanLarson

Respuestas:

8

Presentaré un concepto general y tres soluciones usando ese concepto.

El concepto es un mapa de influencia : para cada ubicación en el mapa, va a almacenar un número que representa la distancia a cada punto de color. De esa manera, para cada posición puede consultar qué tan lejos está del azul, rojo, verde, etc. El resultado es el mapa de influencia.

Para obtener más detalles sobre la motivación, la creación y el uso de mapas de influencia en los juegos, consulte: La Mecánica del Mapeo de Influencia: Representación, Algoritmo y Parámetros .

No tengo idea de para qué es este muro, mi canon principal es que estamos hablando de un juego de estrategia, y la IA está decidiendo dónde colocar los muros. Para hacer eso, hay muchos enfoques además de los presentados aquí. Un enfoque simple sería colocar paredes a una distancia fija de los puntos de color y combinar las áreas cuando se superponen, y, por supuesto, no construirlas sobre obstáculos. Las ventajas de este método son que garantiza que las paredes no estén demasiado Lejos de enviar tropas para defenderlos y es muy barato computacionalmente. Supongo que quieres algo más complejo.

Solución 1 :

Para encontrar una manera de envolver el azul, encuentre la diferencia entre la distancia al azul y a cualquier otra cosa, para cada punto. Anexo : El área donde la diferencia es positiva es el dominio de influencia para el azul. Si toma los dominios de influencia para cada punto de color, puede construir un Diagrama de Voronoi . Gracias a Sirisian por mencionarlos .

Podemos argumentar que para un punto cercano al azul, la diferencia será positiva, y para un punto cercano a otro punto de color, la diferencia será negativa. Dado que la distancia es una función continua, según el teorema del valor intermedio, podemos argumentar que al menos un punto en el medio la diferencia se acercará a cero. Una solución sería trazar un muro que minimice la distancia entre todos los mosaicos donde la diferencia se aproxima a cero.

Lo que sea o no que la solución tenga en cuenta los obstáculos depende de la función de distancia. Si solo usa las distancias de Manhattan o Euclidiana sin considerar posibles caminos, entonces el muro resultante no aprovechará los obstáculos existentes en el mapa.

Nota: esta solución se acerca al área igual para el azul y al resto en un escenario plano.

Solución 2 :

En resumen, puede encontrar puntos de estrangulamiento entre el área de influencia del azul y los demás, y luego colocar las paredes allí. Hacer esto colocará paredes en lugares donde la influencia no está en equilibrio (las paredes están más cerca de un lado) pero minimizará la longitud de las paredes.

Un enfoque útil para encontrar puntos de estrangulamiento es dividir el escenario en nodos convexos y crear una red que represente el escenario. Comenzará a suponer que colocará muros alrededor de los nodos que tienen azul directamente, y luego comenzará a avanzar a través de la red (siempre aumentando la distancia del azul) y considerará la longitud del muro si lo colocó alrededor de lo que ha avanzado hasta ahora. Su solución es la posición que tenía una longitud mínima (y las ubicaciones de las paredes son los puntos de estrangulamiento).

En la práctica, el algoritmo es un poco más complicado que eso porque puede haber ramificaciones en el escenario. Solo necesita considerar cada ramificación una vez, y elegir la mejor posición para el muro para esa ramificación.

Solución 3 :

La primera solución tiene el problema de que puede conducir a un muro que es demasiado largo. La segunda solución tiene el problema de que podría conducir a paredes demasiado alejadas del azul.

Observe que trabajar con píxeles, mosaicos o trabajar con una red es válido y útil el concepto del mapa de influencia, como una representación de la distancia a los puntos de color. Por lo tanto, es posible aplicar la solución 1 sobre la red de nodos convexos.

Mi tercera solución es combinar los enfoques anteriores. Una vez que esté trabajando a través de la red, puede considerar la longitud del muro y la diferencia de influencia, y cualquier otra métrica que desee, como un indicador único de "costo" que puede optimizar.

Theraot
fuente
1
Esto es super útil. Usar un mapa de influencia suena exactamente como lo que necesito. Gracias por los enlaces y la respuesta detallada.
IanLarson