First, start with a small source image. Let's use this 9x9 pixel image of an island

Adjacency

Next, we need to look at each pixel in the image and use code to generate a list of rules for which pixels are allowed to go next to other pixels. For example, in this image, water pixels can only touch water and sand, but never touch grass. Conversely, grass can touch other grass and coast, but never water. This is where techniques often differ - do we just check adjacent tiles, or a larger region? How do we store this information?

In our session, we'll be focusing on the Overlapping Model. We start by looking at a specific 3x3 pixel region of the image, called a tile

Now we need to pick a direction. Let's start with East - we will eventually check every direction. Based on the rightmost two columns in this selection, which other 3x3 pixel regions in the image overlap with their leftmost two columns? It's a little confusing, so let's start with an example that doesn't work.

In our program, every tile gets a turn being the origin tile, and it will check for overlaps with every other tile in every direction.

Yes this does take a lot of time! Yes there are many ways to optimize it! No I won't be teaching them because they're more conceptually complicated and time consuming! Look it up!

Entropy

Okay, now every possible pattern of tiles knows whether or not it can be placed next to any other tile. How do they get placed? Well, we start by defining an output size - we can use the patterns generated from the original image to generate a much larger one! In that output image, every pixel is currently empty, and therefore any of our tiles can be placed at any location. We'll pick a random one to start.

Once the first pixel has been placed, suddenly the pixels immediately surrounding it can only support a small handful of tiles, since there are only so many valid pixels that can be placed next to that original one based on our rules. Since these spots have fewer possibilities, they are prioritized for selection when we place another tile. This is the concept of Entropy - if a pixel has fewer posibilities, we need to place (or "collapse") it first. This reduces the risk of generating an image where not every pixel can be placed due to positions where the neighbors do not allow for any valid tile placement.

Maybe it will help to just see it in action...

This particular model with this particular image never fails to generate an image. As source images increase in complexity, and we implement methods of generating more accurate outputs, the possibility of generating invalid tile states becomes increasingly more likely. Here's an abandoned implementation that uses a higher resolution input to generate much more convincing islands