Operaciones morfológicas

Operaciones Morfológicas

> Programación

¿Por qué no divertirse probando operaciones morfológicas en el mapa?

¿Qué es una operación morfológica?

Las operaciones morfológicas son elementos del campo de la morfología matemática. ¡No huyas! Es extremadamente simple. Básicamente, se trata de usar un conjunto (una "lista" de objetos) para modificar otro conjunto. En nuestro caso, el conjunto a utilizar es el mapa, y la "lista" de objetos es... ¡una lista de celdas! Y es todo !

Entonces, en resumen, como entrada tenemos un conjunto (un mapa) y generaremos un conjunto (otro mapa).

Las operaciones más comunes (¡y fáciles de implementar!) son dilatación y erosión, que modifican el valor de una celda en relación con el estado de sus vecinas. La elección de "qué es un vecino" es otro tema, pero para LeekWars, decidí usar los 4 vecinos de una celda.

Es muy simplificado, pero esa es la idea general.

Operaciones en el mapa

Para realizar operaciones morfológicas sobre el mapa, comenzaremos representando nuestro mapa en memoria. ¡Haz lo que sientas! No necesita tener una representación detallada, solo 0 y 1 para empezar.

Para empezar, comenzaremos marcando todos los obstáculos con el valor 1. Esto nos mostrará las siguientes celdas (mapa utilizado: 304026719):  Aquí los obstáculos son de color verde, porque son los únicos con valor 1.

Comenzaremos implementando una dilatación: cada celda con al menos un vecino en 1 también verá su valor cambiar a 1. Simplemente pruebe cada vecino de cada caja y pase el valor de la caja a 1 cuando encuentre un vecino con el valor 1. Deberíamos obtener el siguiente resultado:  Aquí consideré que los bordes del mapa son obstáculos, no es una obligación. Notamos que los obstáculos aparecen dilatados, como camembert derretido.

Luego aplicaremos una erosión a este mapa. La erosión es lo contrario de la dilatación: cada celda con al menos un vecino en 0 irá a 0. Una dilatación seguida de una erosión es una operación morfológica llamada Cierre: Esta operación crea un "pasaje" entre obstáculos cercanos. La operación inversa se llama Apertura, y consiste en realizar una erosión y luego una dilatación.

En la imagen de abajo, las celdas en rojo son las que serán eliminadas por la erosión: 

El resultado final (sin los glóbulos rojos) es el siguiente:  ¡Luego observamos que aparece un mapa que identifica los pasajes estrechos cerca de los obstáculos! Simplemente.

Para eliminar los obstáculos, podríamos implementar otras operaciones, como AND y NOT. Un algoritmo que aplica, por ejemplo, un NOT (inversión de 1s y 0s) en el mapa con los obstáculos en 1 nos dará un mapa lleno de 1s con los obstáculos en 0. Entonces podemos aplicar un AND (si hay dos casillas tiene 1, devuelve 1, de lo contrario devuelve 0) en este mapa completo y nuestro mapa obtenido previamente con el cierre, que pasa todos los obstáculos a 0. Tadam!


Se obtiene una lista de celdas cercanas a los obstáculos. Podría utilizarse para detectar lugares donde hay poco movimiento posible, callejones sin salida, posibles escondites,... Intente hacer dos dilataciones seguidas de dos erosiones, o alternar las dos, observará resultados interesantes.

Si este método está bien implementado, apenas consume operaciones: lo implementé con un mapa en forma binaria (ver Mapa en forma binaria), que solo consume alrededor de 68 operaciones por operación morfológica.

Por lo tanto, el uso de operaciones morfológicas permite realizar rápidamente un análisis del mapa y extraer información de él. Otras operaciones son fácilmente programables y pueden proporcionar resultados interesantes. ¡Tus teclados!