Thursday, January 10, 2013

Tile Genetics

This is a continuation of an earlier post which was some kind of introduction to Wang tiles. These tiles allow you to cover an infinite plane using a small set, and you can do it in a way that makes repeating patterns a lot less noticeable.

I was recommending everyone to learn about them because there are many problems in procedural generation that lend very well to aperiodic tiling. But the approach in vanilla Wang tiles was only the beginning  This same principle can be applied in many different ways. For instance, here is a brilliant approach to doing rooms using what the author has called Herringbone Wang Tiles. Here you can see how they were used to generate a system or corridors and rooms.


You can find a description of the method here.

There is also a quite popular improvement over classic Wang tiles which uses colored corners instead of colored edges. It results in smaller sets, more diversity and of course their main claim, which is to solve the "corner problem" in Wang tiles. This problem arises from the fact Wang tiles constrains which tiles can be placed along the edges, but says nothing about the corners, that is, the diagonal directions: NW, NE, SE and SW. This often creates noticeable artifacts in the tiling. Corner tiles still suffers from this. The discontinuities are now pushed to the middle of the edges but the problem is somewhat smaller since only two tiles meet there, compared to four tiles in the corner for vanilla Wang.

And there is this very popular adaptation of the Wang algorithm to the GPU in GPU Gems 2. I found this nice tutorial about how to create textures for it. This is from the game Path Of Exile, which appears to use Wang tiles extensively with great results.

As I was saying in my earlier post, the real challenge with all these methods is to come up with the content for the tiles. One approach is to synthesize the content of the tiles entirely. This way you are always in control of what happens at the connection points (corners, edges, etc. depending on which tile flavor you have picked).

This is how I built the cave system for the realtime engine. The crypt profiles, along with narrow tunnels, are drawn by a program. This program makes sure everything connects properly. Here is an example of the output;



The dots inside the large space are massive columns. These are in the tiles as well.

This is not difficult and provides good results as long as you are targeting simple shapes, something you can synthesize. Problem is, in most cases like with textures, you want to use samples you have taken from the real world and use them for the tiles.

If you read the Path Of Exile tutorial I linked before, you will see that this is not a simple task. A lot of work and skill was needed to produce good looking tiles. And this method is only for two colors, that is, the simplest set possible. Imagine if you wanted to have 10 different colors. It would be madness.

There are ways to automate this. If you have an original sample that is large enough, you can take different portions of it and assemble the texture set. Here is a fairly good description of the method (PDF). There is a lot of Frankenstein-esque ingenuity involved, as you must stitch different parts together, hoping the texturing discontinuities will remain small. This produces fairly good results if the original texture is homogeneous, but in most cases "hoping" is not good enough.

I tried this method for terrain synthesis. As a source I used a heightmap with some dramatic features in it. Here you can see a sample:


As the original sample was far from homogeneous, which is after all what you want in interesting terrain, I quickly saw that just one iteration of the method was not enough. This was an optimization problem, somehow I had to minimize the discontinuities produced by the tiles. It is the kind of problem you could solve using genetic algorithms.

You may feel you are entering the mad scientist realm, growing human ears out of mice, playing God with bits, and in fact you are.

The fist step was to design a DNA sequence. Each possible solution (an individual) can be defined as the border and tile coordinates within the sample bitmap. I was doing a set of 200 tiles, with 10 borders in each direction. That resulted in a few hundred bits of DNA.

Next I would do the first population of individuals, which I kept at a thousand. Each individual was randomly generated, just by flipping bits in the DNA.

Next a "fitness" coefficient is computed for each individual. This is a number that indicates how good the individual is as a solution. In my case it was simple, as I could compute the amount of discontinuities the solution had. I also threw in a histogram comparison with the original source, just to make sure all the tones in the original were kept. Adding these two errors gave me a direct measure of the quality of the individual.

Using this measure I could rank the entire population and throw some kind of sexy party. The hot individuals got to reproduce the most, but even the not-so-good ones got their chance to immortalize their seed. This makes sense because a very undesirable trait could become the base of a very nice feature in a future generation. Even the Great Mutato could be the beginning of something beautiful.

I used a very specific way of mixing the DNA, which is called "one-point crossover". It gets a random portion of the father's DNA and the remainder space is copied from the mother's DNA.


This way a new generation is formed. But only 80% of the new members are descendants of existing individuals. The remaining 20% is generated randomly generated, just to make sure there will be enough genetic variety. And of course there is mutation. Each children would have some of its DNA bits randomly flipped.

Watching these things evolve and get better over time is mesmerizing. But it was kind of slow. I realized a needed a massive approach to it. I split the logic into two sections. The part keeping track of the population, doing crossovers and mutations ran in a single process. Then the part that evaluated the fitness of an individual, which was the time-consuming part, ran in a little army of processes over a LAN. (I used good old TCP/IP for distributing the work, ZeroMQ evangelists please go away)

Now this thing ran in eight machines, averaging 3 cores. That is roughly 24 instances of the fitness evaluator. After a week running, I started seeing solutions that I could use. For instance, this image is the result of tiling one of these individuals:


This may seem like a success story, but to me it does not feel like that. The amount of effort and energy that goes into producing tilesets may not justify the advantages you get out of them. Even after weeks of running, most of the individuals still produced noticeable discontinuities.

I know in my case there is a lot of room for improvement. The cutting strategy for mixing tiles with borders can be improved a lot. One thing I want to try it to use patterns in the texture to govern the cutting path. This should mask the transitions even more natural.

The bottom line for me is, Wang tiles are amazing things until you try to use them seriously. They work great for stuff you can synthesize from the ground up. If you are trying to mix samples from real life, get ready for some trouble.



12 comments:

  1. This just gets more and more interesting, now evolution starts playing a role! Cant wait to see whats next =D.

    ReplyDelete
  2. The part about genetics is a bit confusing but i guess it was about generating a few hundreds of tiles based on the source image in order to get enougth stuff to use the wang technique. The source image beeing a heightmap, it could be replaced with any image you want to use as a texture.
    If i'm correct, you could even go as far as to expanded it to any type of data (dungeons, buildings, ...).
    The problem beeing that it's too expensive right ?

    ReplyDelete
    Replies
    1. Yes, it can be used for textures too.

      Like you say the problem is you do not get immediate results. If you are texturing an entire world, you will try many textures to see what looks good. Imagine that before trying a single texture you had to preprocess it for an hour or so. Not very fluid.

      Delete
    2. If you want a genetic algorithm demo to play with, try this: http://www.sea-of-memes.com/LetsCode45/LetsCode45.html

      Delete
  3. So is this a feature that will stay in your engine? Or are there more techniques you are looking into?

    Was your population size static or did some generations have better years than others?

    How is progress with water coming?

    ReplyDelete
    Replies
    1. Yes, this feature stays but remains optional.

      I kept the population size fixed at 1000. All the parents die, except for a 5% top elite. I did not mention the elite in the post, but the actual breakdown of a new generation is roughly:

      5% Elite
      80% Crossovers
      15% Random

      Water is coming along nicely. I got river and lake generation, but only the rough data. Still a long way to go.

      Delete
    2. Really interesting!

      Could you precise how you calculated discontinuity for you fitness function? Also, what are you're reason to choose a genetic algorithm over other optimization methods?

      Delete
    3. Each tile contains four cuts so the center of the tile transitions into the borders. The cut is done finding the path of minimum difference between the contents of the tile center and the border. As the cut is never a perfect match, you can compute an error for each pixel, which is just the difference in value for the same pixel in both the center tile and the border source. The sum of these differences along the path gives you the error for that cut. Adding the errors for the four cuts will give you the error in that tile. And then you can add the errors for all tiles to evaluate the tileset.

      I have no proof genetic algorithms would do best, just a gut feeling. There were a lot of 2D variables involved and the function was very chaotic. Do you have anything specific in mind that would have worked?

      Delete
    4. Thanks for the explanation!

      In my experience, genetic algorithms work best when you don't have any idea of the shape of energy landscape you are exploring except that there is probably a lot of local minimal. this is quite a big hypothesis, and I would have tested a monte carlo exploration first (take a starting set, mutate it, accept it if the fitness improve or use a metropolis criterion to accept or reject the change).

      You could also use elitism (keep some of the best individuals in the next generation) as it generally improve the performance of GA.

      perhaps there is some way to devise a simpler fitness function as a first filter (you could generate a larger population and only evaluate the first 1000 for example).

      you could also use a tournament selection to avoid calculate the fitness for every individuals.

      Finally there is apparently some heuristic on the problem, you could probably use them to improve your initial and mutated set.

      Delete
    5. Yes, there is a lot of local minima. Also there is no way to predict how the function will behave. A shift of one pixel can throw a huge jump.

      I do keep an elite of 5%.

      Delete
  4. I found the height map synthesis interesting. Although not genetics, I did experiment with some fast (and not so fast) synthesis methods for texture during my thesis. You can find technical details (likely one or two errors, you know how that goes : ) here:http://www.dissertations.wsu.edu/Thesis/Spring2010/m_persons_041210.pdf
    You can also find an implementation of the primitive (yet fast) synthesis in the Texture Tiles android app by Mirsaes.

    ReplyDelete
  5. We could store the generated combinations as textures for each model or face or such.

    ReplyDelete