Procedural World

Going off-grid

2013-05-20T02:19:00.000-04:00

Here is a teaser of a series of screenshots and videos to come very soon:

This is not Minecraft on LSD.

Once you have a voxel system that is capable of representing surfaces in any direction and curvature, the real challenge becomes UI mechanics. Creating content has to be simple and rewarding. It has to feel like a game. You cannot expect players to pickup a manual or become experts in full voxel edition systems like Z-brush or 3D Coat.

But the potential is definitively there. Going off-grid allows for more interesting creations. If the system is intelligent enough to adapt to whatever is already there, you could be creating all sort of angled and curved content without busting any veins in your forehead.

What is even more interesting: there is no reason why you would limit this only to cubes. These elements you place could be anything: column disks, rocks, crystal shards, archways, statues. They could be even portions of stuff you or someone else has done before.

I'll leave it there for now. Hopefully you will be intrigued enough to come back later checking for more.

Covering the Sun with a finger

2013-05-07T23:27:00.000-04:00

The oldest optimization in real-time graphics is to avoid rendering what you don't see. When you explain this to people who are not in the field, they usually shrug and say something in the line of "Duh, Sherlock".

It is easier said that done. Well, actually a big part of it is quite easy. The first trick you see in all graphics books is to render only what's inside the field of view. While the scene surrounds entirely the camera, the camera only captures a narrower slice of it. Anything outside this slice, which is usually 90 degrees along the horizontal, does not need to render. For a mostly horizontal scene, only 90 degrees out of 360 need to be rendered. This simple optimization reduces scene complexity four times. Another way to put it is, now you can have four times more detail without a performance drop. This technique is called Frustum Culling.

Frustum Culling is a no-brainer for small objects that are scattered around the scene. As scene complexity rises you must batch as many objects together as possible. The need for aggressive batching apparently has relaxed a bit recently, but there is no question that batching is still necessary. This goes against Frustum culling. What if there is an entire batch that is only partially in the field of view? You would still need to render it all. So, the more you batch, the more you can loose from the frustum culling optimization... unless your batches are somehow compatible with the scene slices you need to render. More to that later.

Even if you were able to perfectly cull all the information outside the field of view, there is usually a lot of polygons being rendered in a scene that never make it to the screen as pixels. This is because they become hidden later by a closer polygon.

Imagine a huge mountain with a valley behind it. If the mountain was not there you would see the valley. With the mountain in front of you, all the efforts rendering this valley go to waste. If we could somehow detect we can skip this valley, we would save a lot of rendering. We could have a much nicer mountain.

This technique is called Occlusion Culling. It is in principle a difficult problem, as the final rendering is the ultimate test of what is really visible and what not. Obviously some sort of approximation or model has to be used. A simpler model of the scene allows to estimate what portions of the final rendering will become hidden so it is safe to skip them.

And then again, if you had the occlusion problem perfectly solved, you would still have the issue with batching. It is not that different than with frustum culling. Maybe just a small clip of a large batch is visible, still that would require the entire batch to render... unless your batches are somehow compatible with the scene volumes being occluded.

I wondered that maybe there was a single approach that would help with all these issues at once. Yes, some sort of silver bullet. I set out to look for one, and did find something. Well maybe it is not a silver bullet, but it is quite shinny.

It is about the geometry clipmaps. I have covered them many times in the past. The idea is somewhat simple: if your world can be represented as an octree, you can compute any scene from this world as as series of concentric square rings. Each ring is made of cubic cells. The size of these cells grow exponentially as the rings are farther from the viewer.

The image above shows a projection of a clipmap in 2D.

You can see right away how this helps with batching and frustum culling. Each cell is an individual batch, which can contain a few thousand polygons. It is quite simple to determine whether a cell is inside the field of view. Also, cells go out of the field of view quite efficiently as their size is constrained by their very definition.

The clipmap turned to be very friendly for occlusion testing as well. Imagine you could identify some cells as occluders in one specific direction of the clipmap. It becomes fairly simple to test if more distant cells are occluded or not.

The following image shows how this principle works:

Here four cells have been identified as occluders. They show as vertical red lines. Thanks to them, we can safely assume all the cells painted in dark red can be discarded. These batches are never sent to the graphics card.

In my case I am performing the tests doing software rasterization. It is very fast because the actual cell geometry is not rendered, only cell aligned planes. So far a depth buffer of 64x64 provides sufficient resolution.

Not bad!

Video Update for April 2013

2013-04-28T11:07:00.002-04:00

An update about clouds and a surprise topic for the second part.

Making these recordings feels a bit weird. I love talking to real audiences, but this feels more like leaving a message in someone's answering machine.

The Unity plugin is looking good!

2013-04-24T21:29:00.001-04:00

Here is an update on the Unity front. Let's see if a screenshot is worth a thousand words:

This is the same terrain generation you see in other screenshots and videos I have posted. This image in particular was not created by me, but by some very talented guys who took the Voxel Farm engine and are using it from Unity.

The sky and clouds in the screenshot is a box with a static image on it, it is not related to the clouds and sky streak of posts I had earlier. The thing is, once you are in Unity there are several plugins that will do real-time skies for you. Actually there are plugins that will do real-time anything for you. That is the point. We are hoping to become another one.

Some Clouds

2013-04-15T03:28:00.001-04:00

Clouds come in many forms. When it comes to generating them it seems there is no silver bullet method. Part of the problem is we call clouds to just one aspect of a more general process: water particles suspended in air. This could also be fog, or the misty breath coming out of trees and plants in a jungle. This is what the initiated in this occult science call "The Participating Media".

I decided to tackle this problem by having different layers working together. Which layer to do first? Even in the highest places in Earth, it is likely to find a layer of clouds over your head. I did some experiments over the weekend on how this particular layer could be rendered.

Here are a couple of early screenshots for your consideration:

It is a very simple and fast method that allows clouds to animate and evolve over time. You can go from a clear sky to a very cloudy one as well. It takes into account the sun's position and does some basic scattering and self shadowing.

These clouds are rendered in the same skydome that performs the day-night cycle, so they do not add any new geometry. This is also the problem with this method: This is a flat layer. There is the impression of volume thanks to how the light is computed, and this trick holds as long as the clouds do not move too fast. If you make them sprint over your head it becomes obvious it is a flat layer. You cannot also come too close to these clouds, that also kills the illusion.

For what it does, I think the method is quite neat, especially if you don't have much GPU cycles to spend in clouds. It does not use any textures or any other resources. This is 100% GPU so it would run nicely in demos or WebGL frames. I think it deserves a future technical post on its own, that of course assuming you guys like how they look.

Let me know what you think by dropping a comment.

The sun rises in ProcWorld, again

2013-04-10T10:31:00.000-04:00

Last week I posted some early screenshots of the nigh-day cycle. There was a lot going wrong in them and you guys were very helpful in pointing out solutions.

I did another iteration on this, while not everything is as it should, I think there was some improvement. This time I have captured a video. The transitions are better appreciated like this. Again let me know what you think.

The main issues with the previous iteration were the brightness of the sky (or lack of it), and how the distant features failed to blend with the sky. This time I made sure there was enough atmosphere so more light was trapped between the horizon and the eye. The distance to the sky is also consistent with the terrain dimensions, now the colors in terrain and sky match better.

A few comments in the previous post suggested a different method called "Precomputed Atmospheric Scattering". It certainly produces better results than the method I am using here, which is the one from O'Neil in GPU Gems 2.

I had a quick look at the method and saw that in its vanilla form it could run slower than what I have now. While the method uses precomputed tables as textures to accelerate rendering, all the work is done in the fragment shader. That means every pixel on screen now had to perform two or three additional texture fetches.

The method from O'Neil does all the heavy lifting in the vertex shader. Consider this scene:

The sky, even if it appears softly shaded, has only a few vertices:

I think in this case it makes a big difference.

The precomputed method could also run in the vertex shader, but then it would take some time to port the tables, which now are in pixel formats that cannot be read by the vertex shader.

Of course there is a chance I am reading this wrong. If you have worked in this area before and see what I am missing please let me know.

The sun rises in ProcWorld

2013-04-03T22:55:00.001-04:00

So I finally added some proper light scattering to the sky atmosphere in the realtime demo.

I am using the classic approach devised by O'Neil, which produces great results but it is also very sensitive to any change in the input parameters. A lot of tweaking is still required.

Here is a series of shots, keep in mind this is a work in progress but any early comments surely will help.

Network Update

2013-03-30T15:01:00.002-04:00

Here is a new video I recently captured. It shows the networking and storage components in action.

When it comes to networking this is the smallest test possible, you cannot really go below two connected clients. I have tested this same server code with nearly a hundred clients performing queries and changes at rates many times higher than what humans would do. Network tests are good at showing why some stuff does not work. But when the results are good it does not really mean anything. The real network is so complex you cannot replace it by any model. In this case results are as good as any network test can be at this stage. There is very little overhead from the thread and connection management, which is what I was looking for.

While this is good news and by all means necessary, the real bottleneck comes from how any application using this engine chooses to store and process information. So again what you are seeing here is just a brick. You could create many different houses with it.

You could do it like Minecraft servers do, have everything including procedural generation run in the server. You could do like this particular demo does, where user-created content is stored in a server and everything else remains client-side. And you could have solutions in-between, for instance have some custom server-side generation which is merged later with the rest of the client-side generation.

This is a fascinating subject to me, I will be covering some of these approaches in the future.

Storage Matters

2013-03-27T19:51:00.000-04:00

Imagine you were creating a massive persistent world where everyone would be able to change anything at will. It is a simple, powerful idea that eventually has occurred to everyone ever exposed to a game. Why there aren't many of these worlds out there? Well, this very simple idea is quite difficult and expensive to execute. Not only you need to store the information, you have to be able to write it and read it in a timely fashion.

Then how about your own personal world, something you can run in your PC and invite some friends to play over. How much of your PC's performance are you willing to sacrifice, how many people could you actually invite before you would see the quality of your gameplay begin to suffer?

I began wondering whether all the above could be manifestations of the same problem. What if you could have a storage solution that is lightweight so enthusiasts could run at home, and if you pieced enough of them together you could scale it so it would run massive worlds the size of planet Earth?

As it turns out it was possible. I have now a shinny new database system that does exactly that. The main trick is it aligns with the same other concepts of the voxel world. So this is mainly a voxel database. It won't do any SQL queries, XPath evaluation or any other form of traditional DB interaction. It just stores and retrieves voxel data very fast.

How fast? Over a 10 minute period, a machine with six-year-old Intel processor (T2500 at 2GHz) and an equally crappy HD was able to serve 10 Gigabytes worth of individual queries while another 10 Gigabytes worth of queries were being written. Each query ranged from 500 bytes to 100KBytes worth of data.

That would translate into a lot of friends sharing your server. To give you a better idea, a volume of 40x40x40 worth of player voxels compresses to 2K as an average. Here is how you would compute how much space 10 GB of voxel data would be:

1 chunk = 40x40x40 voxels = 12x12x12 meters
1 chunk = 2K
10 GB = 5,242,880 chunks = 2048x2048x2048 meters

How many people can create this amount of voxel content in 10 minutes? I have no idea, but I bet it will be an entire army. At this point the DB is the least of your concerns. The bottleneck is in the network.

The twist comes now: While this rate was sustained for 10 minutes, it was not meant to push the system to the limit. The DB process CPU usage never went up 1% and the memory usage for the process remained at 3 MB. The system was responsive and usable (well as usable as a six year old PC can be), showing no big difference in behavior.

Here is some evidence:

For most of you who are more artistically or design inclined this is certainly the most boring screenshot I have ever posted. But if you are into programming this kind of thing, this is process porn.

Of course the system is doing real work. The main clue is in a different column not displayed by Task Manager: Virtual memory, which was hovering all the time below 20 Megs. Even then the virtual memory was lower than what Google Chrome was using, which was a whooping 99 Megs.

The voxel database is so fast because it uses the same virtual memory management of the OS. So, instead of writing to files in the HD directly, all the information is mapped through the OS paging system. Only the pages that need to be altered go into memory. Also the system does a lazy write to the HD. Even after the process is gone, the OS continues to save the changes to disk.

I feel this is the stepping stone for great things. It will be fairly easy and inexpensive for people to set up their own servers. They could be hosting a lot of players and barely take a hit for it. This of course depends on how the networking is implemented, which leads into another favorite topic of mine: how to make a server that will not bring your PC to its knees. I will be covering that in the near future.

Melodive and Oveja

2013-03-15T15:45:00.000-04:00

I couple of days ago I got this game from one of the readers of this blog. It is all procedural, including the progression of music. The name is Melodive and it is available for iOS.

Even without the help of mind altering substances, the game takes you to a different dimension. I did find the control scheme a bit frustrating, but it seems there is a whole class of games using this form of tilt, rotate interface. To many of you out there the controls may seem standard.

Oveja

And there is this other non-procedural game a Russian friend did from scratch, including programming, graphics and music. He named it Oveja, which in Spanish means "sheep". (Why a Russian guy is giving Spanish names to his games, it is beyond me.) The game is fun and equally surreal, but on a different level.

It runs in Android and it is available free from Google Play:

https://play.google.com/store/apps/details?id=com.mastercluster.oveja

If you like air-traffic control games you should give it a try. It is like these games, but with sheep in it. I did not get why the black sheep needed to be segregated from the white sheep. This is 2013, those times should be over.

The next version is rumored to include sheep poop and other equally interesting gameplay mechanics.

This one is a talkie!

2013-02-25T17:50:00.001-05:00

Here are two new videos showing some new features.

I finally decided to add an audio track to a video. It does help describing what is new as it appears on screen:

Let me know if you like this format. I think I could do one of these every month.

The second video is some sort of fast steady-cam flyover:

Undergrowth

2013-02-21T07:06:00.000-05:00

Last weekend I took some time to add a new feature to the engine. It is some sort of mesh instancing system that brings additional detail on top of the geometry output. It can be used to add a new vegetation layer under trees, like the following images show:

I will be using it for rocks, pebbles, even man-made elements sticking out of the blocks you place.

Polygon counts are now escalating quickly because of this. My old 4770 still averages 40 FPS at 1080p but begins to struggle. It is still manageable, there are some polygons right now I can cut.

This one was long needed. I will be posting a video later so you guys can see how the LOD transitions are managed. I think this has improved a lot.

Unity makes strength

2013-02-18T14:01:00.000-05:00

I like writing everything from scratch, but not everyone shares this form of dementia.

Many in the past have asked whether any of this would run on mainstream game engines. I could not see a reason why not. The VoxelFarm engine outputs traditional polygons, in theory it could be plugged into any engine using polygons for rendering, physics, etc. That remained a nice theory until recently. Now we have some hard proof:

This screnshot shows the VoxelFarm realtime engine providing polygons for terrain in Unity.

Here is are a video. It shows a simple physics test and a little bit of walking. The capture speed and resolution is not good, but hopefully you will get the idea.

I understand if this tech is to be widely used, it will likely come in the form of plugins for mainstream engines. So think this is very encouraging news.

Voxel Studio Videos

2013-02-04T14:45:00.001-05:00

Here are three videos I captured from Voxel Studio to help with the AiGameDev.com interview:

AiGameDev.com Live Broadcast

2013-01-29T23:16:00.002-05:00

Next Sunday February 3rd I will be doing a live interview at AiGameDev.com

You can find the right moment to tune in for you time-zone here in this page, where the broadcast will eventually appear:

http://aigamedev.com/broadcasts/procworld/

Make sure you catch it on time. The archived version may be playable only to members of the AiGameDev community.

Don't be square!

2013-01-20T22:45:00.000-05:00

Minecraft gets many things right, but the top in my list is how easy it is to create. Nothing is simpler than laying out boxes. Since everything is square (even the cows), being limited to boxes does not feel bad at all.

If you are doing some sort of sandbox environment going beyond just boxes is not trivial. One possible approach is to do like Blockscape, where in addition to the classic box you now have a large repertoire of prefixed angular shapes. I do not like this approach as it makes the interface very complex and frustrating. It makes you forehead veins pop.

So I chose a different approach, where you still lay boxes the same as in Minecraft, but then you can go back and alter them. I saw that a single operation was enough to produce both curved and straight angled surfaces. If you applied it gently you would get curves. If you applied it more, it would straighten out.

Here you can see a round hole and a needle, both initially created as boxes. It only takes a few clicks to shift their shapes:

I think this is the right direction. Still it is not simple to implement. While I got this thing working, there are many issues to fix.

I leave you with a video, let me know what you think:

Voxel Playset

2013-01-19T14:25:00.000-05:00

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

2013-01-16T17:05:00.001-05:00

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

2013-01-11T13:16:00.001-05:00

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

2013-01-10T11:47:00.001-05:00

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

2013-01-03T16:35:00.001-05:00

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.

Golem Interview

2012-12-13T13:44:00.001-05:00

I was interviewed recently by the Golem magazine. They were researching for an article on procedural generation. The article is in German.

http://www.golem.de/news/prozedurale-schoepfung-kuenstliche-welten-auf-knopfdruck-1212-96323.html

Only 7% of ProcWorld readers come from Germany. For the English readers I though it would be nice to post the original round of questions I got from Golem, along with the answers:

What are you working on at the moment? What are you most proud of in that regard?

Right now I am working on real-time architecture. Buildings are generated as you approach them. It is challenging for many reasons. First you need ways to teach the system how to generate interesting buildings. Then you need to make it happen really fast. It is the worst combination possible: a hard problem that needs to be solved in very little time.

I am proud of the potential. It is not obvious right now, but as the hardware continues to grow this platform could produce incredibly rich environments.

What does procedural generation mean for artists? How will it transform their job - and how will they have to adapt to benefit?

Robots are coming for our jobs everywhere, even journalism is being automated (you could be a robot for all that I know). The key question is how creative your job really is. If you perform unimaginative tasks, even as a "creator", odds are you will be replaced by some technology. Artists are no exception. How to adapt? Be more human, less robotic :)

What makes procedural generation important for the future? What will it enable?

It helps looking at the past first. I see three ages in procedural generation. The first coming was when storage and delivery was very limited, so there was an advantage in generating stuff on-the-fly. This is when games like Elite first appeared. We were very forgiving as an audience back then. You could throw a few points on screen and call it a galaxy.

Then hardware grew to a point where more realistic representations could be stored and rendered. At this point it became possible to pack quality artwork into a product. This gave us the second age, where most content was hand made. We are still in that era. Consumer grade hardware, like current console generation, is not able to produce content that is rich enough to challenge human-created content. There is some proceduralism there and there, but it is relegated to the background.

If Moore's law continues to hold, we will enter a third stage. Hardware is growing at a faster pace than artist output. The industry needs to keep moving the new hardware, but it is becoming prohibitively expensive to do it in the traditional model. Automation is the only choice.

What will be the future? You can think of a variation of the Turing's test: A human plays a game without ever realizing most of it was created by a computer.

In what way could it make gaming better? Or worse? ;-)

I think it will produce a lot of horrible games. Look at what the auto-tune has done for music. But then it will produce some unique experiences.

I also think we should not worry about that. Imagine a house is burning and the people inside are wondering whether it is sunny outside. It does not matter because they have to come out anyway. Automation is inevitable in the games industry, otherwise the whole industry will stagnate and burn like the house. Whether it will be worse or better, makes no difference.

What are the worst problems - from a programming and an artistic standpoint?

Let's say you were building a game the traditional way. You would have one guy doing the story, some guys do concept art, some other guys do the actual environments, level design, others will create and place props and so on. In theory all of these tasks can be automated.

The reality is some of these tasks are a lot simpler. For instance the guy modeling rocks can be easily replaced, but what about the one doing the concept art or the storyline?

There are some tough problems there. They are on the fringe of AI and we have no solutions for them today. But then once you look at what we can do with automated translation, self-driving cars, and so on, we may not be far from that. There is also the advent of "the cloud" as a computing device. I think that changes everything.

What do you think has been the most important progress to procedural generation during the last years? An what can we expect from the future? And how important are hardware and 3D engines for the further advance of procedural content?

The hardware has evolved to a point where some cool things are now possible. We have known about them for many years. It was just too slow to try them.

There has been a lot of research in synthetic reality, for a long time now. The real bottleneck has been and continues to be the hardware. Look at the movie Avatar for example. It is a procedural world what you have there, still it costed millions to generate. This has to come to the point where an equally rich world could be generated by your home console or computer, or by cloud services you can afford.

Videos of Caves and Buildings

2012-12-03T20:34:00.000-05:00

Here is a series of videos I captured over the weekend.

The first one shows a bit of the architecture, also how a couple of useful underground passages can save you time while travelling:

The second is a trip I did to get close to a tower I saw. It seemed simple at the beginning, but the terrain had some severe accidents so I had to figure out my way. I found some caves that helped me get there, also saw I needed to do a quick bridge over a chasm. It runs at double the speed so you would not get bored by all the wandering. Also note that at the end of the video I carve some holes into the tower walls.

The next video also runs at double the speed. It shares the same beginning as the first video posted here, but goes a lot farther.

And the last video shows how the caves can sometimes go really deep underground. You often see cave openings into the surface, but also they could be right under your feet and you would not know. I cheated in this video by showing the wireframe, otherwise it would have taken an awful lot of time to find these caves.

Architecture On-The-Fly

2012-12-03T02:45:00.000-05:00

Boy this was a tough one. I always knew it was coming, tried to postpone it for as long as I could.

In the past I had succeeded creating complex buildings out of L-Systems. While it was fast, it was for a different approach to world generation. It was for static game worlds like Skyrim's. I had the luxury of time.

In a world that generates as the viewer moves, most of the time I had for generation was already taken by the terrain and trees.

Architecture is something you cannot just instance. You want buildings to be different, even if they belong to the same class. I needed the actual grammar programs to run in real time, its polygonal output voxelized and then merged with the rest of the voxel data.

You may think going from polygons to voxels then back to polygons is an awful waste of time. It had been, except for the fact I needed changes made Minecraft-style to also work over buildings. When you are wielding that pickaxe you don't really care if that rock in front is a natural formation or a cathedral wall.

At the end I did manage to make it work. As usual most of the solution went into creating indices to accelerate the actual work.

I had to make compromises. For starters, the voxel resolution in the realtime engine is much coarser than what I had for the pre-computed worlds. This meant a lot of the detail in buildings had to go. This also applied to the following levels of detail. Detail had to be removed in all levels.

I also saw I needed simpler grammars just so the system could keep up in lower-end hardware. I found it common to have thousands of different buildings in a single scene. The solution I found was to pass the LOD parameter to the building grammar at evaluation time. It made it possible, but now the building programmer has to worry about creating different views for the same building.

I am still very happy with the results of something I feared almost impossible. There is room for improvement, and this is a good thing. The hard part is over.

I leave you with some screenshots of a single tower grammar that appears scattered everywhere. Please do not mind the lack of actual cities, or the fact it is the same tower over and over again. This is rather a test for the system. I will be posting some videos later.

Come see me at Recursion

2012-11-18T16:23:00.001-05:00

There is a reboot of the demoscene going on in Montreal. A large event is planned for this weekend (Nov 23, 24 and 25) at Concordia University.

Here is the schedule: http://recursionparty.org/horraire/?lang=en

If you look closely, you'll see I will be doing a seminar Saturday 24, at 3:00 PM. As usual I will talk about procedural things. I will also show the realtime demo from the last videos and screenshots.