Voxel Playset

One last post about kids and I will shut up.

It turns out I have been using my kid's toys to help me think about voxels and other algorithms. This is by far my favorite:

This thing really helps. Some of the work you do with voxels becomes a lot easier if you have a way to look around them with your eyes instead of just your mind.

Several of these cubes now have little annotations done by me with a sharpie: numbers, face indices and other stuff like that. These numbers can also be found in the source code.

Here is another time saver:

No need to waste paper if you just want a temporary drawing for something you need to understand.

Monkey Testing

It is hard to find bugs in software you have written. A developer is always conditioned to the way the software its built. The scenarios that you will test are only those you anticipated. It is like playing chess against yourself.

When it comes to a fresh point of view, nothing can rival an actual monkey. Monkeys are guaranteed to exercise every bit of interface you expose. Now monkeys are hard to come by. If you lack one the next best thing is a two-year old human.

I have two-year old twins girls, so I decided to give it a try. It was surprisingly easy to get them to play with the software. (I did tell them there was a pretty bird hiding somewhere in the trees.)

 

Did they find any bugs?

They found several bugs I had not seen before. Most were about camera collisions, and there was one really nasty synchronization bug with a garbage collector. That bug alone was worth the experiment.

And there is also proof you can advance a software project and look absolutely adorable in the process.

Google you still don't get this

Nothing to do with procedural generation, but maybe a bit about artificial intelligence.

Almost two years ago I was complaining about Google's lack of intelligence in matching ads to content. A bit later I was doing posts about tree and forest generation and Google kept serving ads about gardening and genealogical trees.

You would expect two years would have made a difference, then a week ago I started posting about T.I.L.E.S. These are the ads I get now:

Just makes no sense to me. With all the tracking and understanding they do, just a few words are enough to get them off the scent.

I'm glad they got Ray Kurzweil and all, but I begin to wonder whether the Singularity will be just sub-par intelligence at a massive scale. We are bracing for this:

When what we may be getting is this:

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.

Introduction to Wang Tiles

This is guaranteed to be a very colorful post.

Since the early days of computer graphics, texturing has been the favorite method to bring detail into 3D surfaces.

The problem with textures is they take a lot of memory. While there are some attempts to have 3D worlds uniquely textured, like Id's Rage, the traditional approach remains to tile a smaller rectangle of texture across a much larger 3D surface.

This certainly does the job, but it also brings out these repeating patterns we dislike so much. There are a number of ways to mask the repetition, sometimes by blending more than one texture, or by adding splats of unique detail in strategic places.

Another approach is to use Wang tiles. If they are new to you, once you are done reading this you should Google them up and get soaked on what they are and how they work. You will love learning about this. It will expand the way you look at problems in the future. Wang tiles are much more than just a method to avoid repeating textures. You could use them to generate terrain, geometry, architecture. If you get carried away, you'd see they are actually full fledged computing devices on their own.

You could say we have used them already without knowing, as the traditional way we tile textures is one specific case of Wang tiles.

But forget Wang tiles for a moment. The way you would normally texture a brick wall is to use a 2D image and let the GPU do the tiling. If you just take a picture of a brick wall in real life and use it, you would see there are very noticeable discontinuities where the edges meet. The colors on the North edge of the image do not connect properly to the colors in the South edge, and the same happens with East and West.

This is very noticeable in the following polka dots texture:

This is easily solved by making the texture "seamless". What it involves is to make sure the West and North edges match the East and South edges respectively. In most cases this is done manually, using a tool like Photoshop.

Here you see the fixed texture:

Problem solved. But this texture still has very noticeable repeating patterns. If you tile it long enough they are hard to miss.

Here comes the twist. We made this texture work by making sure edges connected properly. We have one edge that is shared horizontally, and another one that is shared vertically:

So what is inside the tile does not matter as long as the edges connect properly. Instead of just one texture we could use several, all sharing the same edges. Here is an example:

We could pick which tile to use randomly. This will eliminate the repeating patterns coming from the center area of the tiles. But we would still have some repetition coming from the edges.

Here enters Mr Hao Wang. He predicted what we are about to do was not possible, and for being wrong this method bears his name. In reality he did all the heavy work so it is more than deserved. Here is a picture of Hao Wang winning the 20 Km men's race in Chihuahua:

Actually that is not Wang, but it is the spirit what counts.

Wang tiles allow us to have more than just one vertical and one horizontal border. You can choose to have as many as you want. As soon as you know how many different borders there are, the method tells you how many tiles you need so you can tile them all you want without leaving any holes.

Let's say you choose to have two horizontal borders, blue and yellow, and two vertical borders, red and green. Here is a resulting set of 16 tiles:

This is what the tiling authorities call a "complete set", meaning it has all the possible tiles. It contains every combination of every combination of colors. This is how you would compute the number of tiles in a complete set:

Where N is the number of horizontal borders and M is the number of vertical ones. Hence 2 horizontal and 2 vertical make a set of 16 tiles. Now these numbers explode quickly. For 3 colors in each direction you now have 81 tiles. For 4 colors it would be 256 tiles. Four colors do not provide too much variation along the edges, still the number of tiles is huge. If you had to store this info in video memory it would be a problem.

Thankfully the math guys proved you do not need a complete set to achieve full tiling. A much more smaller set exists which can be created in the following way: For each combination of North and West colors, you need at least two tiles. Now the tile count becomes:

This is a lot more manageable. Two borders on each direction requires eight tiles. Four borders, 32.

Once you have your tile set, you can use it in different ways. When time comes to place them, there are a few simple rules to follow. You start from the top-left corner, North-West. At this point you can place any tile from the set, picking one at random will do.

The next tile you place must match the existing one. You can still pick a random tile, but its West side must match the East side of the previous tile. You can continue to do so for the first row:

When starting the second row, you will have to match the South border of the tile on top, in this case you can pick any tile in the set that has a green North.

And then for the rest of the row, you will find tiles that match both the North and West color requirements:

At this point you are ready to go on tiling forever:

While all this seems great and guaranteed to make you interesting at parties, the difficulties with Wang tiling are not in picking edge colors and using the sets. The real challenge is to come up with content for the tiles. In my case I had to resort to genetic algorithms running many instances over a LAN.

I will cover this in my next post.