Morphological Operations

Morphological Operations

> Programming

Why not have fun trying morphological operations on the map?

What is a morphological operation?

Morphological operations are elements of the field of mathematical morphology. Don't run away! It is extremely simple. Basically, it's about using a set (a "list" of objects) to modify another set. In our case, the set to use is the map, and the "list" of objects is... a list of cells! And that's all !

So in summary, as input we have a set (a map) and we will output a set (another map).

The most common (and easy to implement!) operations are dilation and erosion, which modify the value of a cell relative to the state of its neighbors. The choice of "what is a neighbor" is another subject, but for LeekWars, I decided to use the 4 neighbors of a cell.

It's very simplified but that's the general idea.

Ops on the map

To perform morphological operations on the map, we will start by representing our map in memory. Do as you feel! You don't need to have an in-depth representation, just 0s and 1s to start with.

To start, we will start by marking all the obstacles with the value 1. This will show us the following cells (map used: 304026719):  Here the obstacles are colored green, because they are the only ones with a value of 1.

We will start by implementing a dilation: each cell with at least one neighbor at 1 will see its value change to 1 as well. Just test each neighbor of each box and pass the value of the box to 1 when you encounter a neighbor with the value 1. We should get the following result:  Here I considered that the edges of the map are obstacles, it is not an obligation. We notice that the obstacles appear dilated, like melted camembert.

We will then apply an erosion to this map. Erosion is the inverse of dilation: every cell with at least one neighbor at 0 will go to 0. A dilation followed by an erosion is a morphological operation called Closure: This operation creates a "passage" between nearby obstacles. The reverse operation is called Opening, and consists of performing an erosion then a dilation.

On the image below, the cells in red are those that will be removed by erosion: 

The end result (with the red cells removed) is as follows:  We then observe a map appear which identifies the narrow passages close to the obstacles! Simply.

To remove the obstacles, we could implement other operations, such as an AND and a NOT. An algorithm that applies, for example, a NOT (inversion of 1s and 0s) on the map with the obstacles at 1 will give us a map full of 1s with the obstacles at 0. Then we can apply an AND (if two boxes are has 1, return 1, otherwise return 0) on this full map and our map obtained previously with the closure, which passes all the obstacles to 0. Tadam!


A list of cells close to the obstacles is obtained. It could be used to detect places where there is little possible movement, dead ends, possible hiding places, ... Try to do two dilations followed by two erosions, or to alternate the two, you will observe interesting results.

If this method is well implemented, it hardly consumes any operations: I implemented it with a map in binary form (see Map in binary form), which only consumes around 68 operations by morphological operation.

The use of morphological operations therefore makes it possible to quickly carry out an analysis of the map, and to draw information from it. Other operations are easily programmable, and can provide interesting results. Your keyboards !