Golem Interview

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

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

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

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.

A System of Caves

A true exploration and adventure game-world needs a decent system of caves.

Caves are exiting. You do not know what lies next. It could be that motherload you have been tracking for hours, it could be a band of nasty creatures.

Caves are also beautiful and interesting. I like it when caves surface and create openings in the face of mountains, or when a large portion of ground has collapsed and you can see part of the cave's profile like a giant ant farm.

Over the past few weeks I did many attempts on creating a good cave system. It is a lot more difficult than it seems, especially if you want to generate them in real time.

I tried different solutions until I hit what I thought it was the winning formula. The key wast think of the cave system more like a dungeon in a castle, pretty much like roguelikes do in ASCII. You end up with a system of narrow tunnels that connect in meaningful ways and often lead to large interior spaces. It is then possible to give an interesting rhythm to the system. You can count on the system to reward the explorer with awesome crypts after enough tunnels have been explored.

Another challenge was to create the connections between the caves and the surface. I wanted caves to be fun and beautiful, and actually help you get around the world. For instance they often serve as shortcuts below mountains.

I also had to pay close attention on how the caves played with the rest of the terrain. If you had all the time in the world this would be hardly a problem. To generate this on-the-fly and make sure there are no odd floating bits, it is kind of tricky.

I leave you with a series of screenshots showing some caves I have encountered in my travels. At the end you will find a wireframe video that shows the profile of a cave system. I hope you like them.

Here is the video:

Into the sandbox

This is a follow up on my earlier post, where I announced a new take on my engine so it could be used for games like Minecraft.

Here is a video of me building a nice house on a hillside. The video is a bit long (38min) even if it plays at double the speed. You may want to get some snacks.

Here is one shot of the house, it is far from finished, but I really like the view out of the bedroom:

Here is the video:

The video shows how anything from the world can be removed. You can also add new blocks, which are all square, pretty much like Minecraft.

But unlike Minecraft, you can use tools to smooth out the blocks creating nice curves and slopes. The idea is to work initially in squares, then smooth it out as needed. Smoothness and slopes comes in a second phase. Otherwise it would be too difficult to place them and control the resulting shapes. I think it is the best approach possible. It combines the simplicity of square blocks with the rich appearance you can find everywhere else in this virtual world.

Something else about the video. Right at the beginning you can see a green progress bar. This is how long it takes to get into the world, no matter if you are starting it from scratch.

This video was taken from a i5 with 4 cores, running a Radeon 4770.

I continued to work on the house after I stopped recording. The save data for the entire world is around 300K.

As usual I look forward to you opinions and questions.

What if I told you...

Yes, I know I said I would not do it. But it was hard to resist the temptation. After all I had all the required pieces, so why not?

All the videos I have posted recently were captured from this new engine, codenamed "VoxelFarm Realtime". It means all you see here is generated on-the-fly, as the viewer moves. It takes less than 15 seconds to boot an entirely new world, which can be larger than Planet Earth.

You can also carve, dig, and build into everything you see. You are not restricted to square shapes anymore. The blocks you can add are no different that the same blocks you already see in trees, rocks. Organic and all kind of angled surfaces are very much possible.

Now the cat is out of the bag, more on this to come.

Snow, Biomes

Last week's video was about adding variety to foliage.

Here are three new videos that show something similar but at a larger scale. The first two show transitions from snowy terrain to green terrain. The last one goes from green to some kind of rocky desert.








Do not pay too much attention to the sound, you will hear chipping birds no matter if it is snow or desert.

I did some improvement on the LOD switches. They are still happening pretty much on your face, but in general should be smaller.

Fall colors

Here is a video showing the new skylight feature. Trees now can have different foliage. Adding fall colors was a nice way to test this. These trees share the same foliage texture, it is colorized on-the-fly by the shaders.

Realtime global illumination, sort of

I just added skylight to the realtime renderer. I am very happy with the results. In my opinion it adds a lot of depth, and it is quite fast to compute. You can see it here in two series of screenshots I took for a forest setting.

In each series, the first image is the final results, the second image is the contribution from the skylight and the third is the direct sunlight illumination:

Second series:

This is already looking good, and it runs in realtime. If there was some large character moving around in the scene, you would see its contribution to the shadowing.

The skylight is a standard shadow map, but it is sampled taking a lot of neighbors into consideration. This creates nice soft transitions between areas of light and penumbra.

There are no light bounces here, however. I have been toying with the idea of a screen-space radiosity solution. I think it is possible. If you know of any papers on the subject, please drop a link in the comments section.

As usual I look forward to your comments and criticism.

Realtime Shadows

I decided to give dynamic shadows a quick try. I used a shadow map with percentage-closer filtering to smooth shadow boundaries. The results are quite fast and smooth. The main trick was to run the shadow evaluation on the vertex shader. I realized I had enough vertex density for consistent results. The shadow interpolation between vertices would make the shadows even smoother.

Here are the results.

 

If you wait to the end of the video you will see there is some kind of mysterious object rising from the ground. This is unlike anything you have seen in my videos before. It certainly means something, a sign of things to come...

Voxels in the wind

Fall is here and it is getting windy. It is a good time to finally add some animation to grass blades and tree branches.

 Here you can see some results:

   

There is nothing fancy going on here. The post title is deceiving since no voxels were animated, just traditional polygonal billboards. The motion is a few sine waves overlapping at different frequencies. The next step is to feed wind vectors to the vertex shader. This will create turbulence near cliffs and some other nice effects.

And then some leaves and other particles flying around for increased realism.

Talk Points

I just found out the audio for my talk at the Mont Royal Game Society was very poorly recorded. It seems the only way you will hear this presentation is you invite me for beer. Anyway for what it is worth here are the slides. They were designed to go with the talk so there is a lot missing.

Come see me!

Do you live in Montreal? Do you like beer?

The Mount Royal Game Society has invited me to give a talk about procedural things. It is happening next week. Here are the coordinates:

WHEN
Wednesday, September 5th, 19h30

WHERE
Brasserie Artisanale l’Amère à boire
2049 rue Saint-Denis, 3rd floor

I will be covering everything I have learned over these years. If you have any non-Minecraft related questions, I will be delighted to take them.

More Grammar Screenshots

Here is another series of screenshots. These are also from the Canyon City grammar.

I really need to improve the lighting in this preview. I normally export the final mesh to 3ds max and render it with nice global illumination. The meshes I get out of this are so large 3ds max cannot deal with them anymore.

The mesh complexity is a problem only at this stage of the grammar edition. Once this is voxelized and optimized back to polygons, it will be fast enough even for realtime rendering.

Over the weekend I will see if I can load this into 3ds max to produce better previews and share them with you.

Canyon City Teaser

In the past few days I have been writing a grammar for a massive structure. It is some sort of water collector for desert areas. It is so big that there are buildings on top of it and acts as the center of a small, parasitic city.

I did a couple of concept sketches for it. This was painted with my fingertips on an iPad (using the Paper app). Don't expect too much detail here:

The grammars for this structure are not difficult, but there are a lot of special cases. Since it is taking so long, I thought it would be nice to post some partial progress.

Here is a preview of what I have so far. The screenshots are taken straight from Voxel Studio.

This is a teaser so I won't be showing much. You cannot fully appreciate the scale here, but this thing is so large it will have an entire forest under the main dome. The towers, which are for cooling, are hundreds of meters high.

I am building this so I can finally show all elements of the procedural world coming together.

Producing complex shapes

Architecture L-Systems deal with fairly simple shapes: boxes, tubes, cylinders, prisms, some times loft and revolution operations. They define the bounding volumes where you can instance actual geometry samples, like columns, windows, doors, bricks and tiles.

These basic shapes alone can get you far. The problem arises when you need these constructs to intersect each other. In most cases they produce complex shapes for which we don't even have names, let alone a unique mathematical formula. For instance, you can create a nice dome by doing a loft operation on a tube or a cylinder. Now, if you needed to blend two domes, you would be facing an increasingly difficult problem.

In other fields this is usually solved by "Constructive Solid Geometry" (CSG), which is about combining multiple shapes into bigger or smaller shapes by subtraction, addition, intersection and other similar operations. The problem with CSG is that it outputs a soup of triangles. The little boxes, cylinders, prisms we used to have disappear in this soup. This matters a lot for  architecture grammars. The rules you write are designed for these basic elements, not flat triangles.

I encountered this problem while building grammars for a Mosque. The base of the building is square, the top of the building is a dome which has a circular base. There is some kind of roof that transitions from the square into the circle. This is an element also found in Roman and Byzantine buildings.

In the next image you can see a red arrow pointing to it:

If you isolate this element, this is how it looks like:

It is some kind of curved square with a round hole in it. Not only this element is special. The side walls of the square base must be properly cut so it fits. Here you can see them:

These images, as usual, are the output of my architecture system. Which means these shapes entirely possible. They are quite easy to produce as well.

The trick again is in the occlusion rules. This time they can be combined with the recursive nature of L-Systems to great advantage.

The starting point is to define these shapes ignoring the weird cuts we will make later. This is what you get from a square base and a cone-shaped tube, both basic shapes:

Here comes the first trick. In reality, these shapes are made of smaller ones. I have reduced them just so you can see:

Using occlusion rules, we can hide the elements that are outside the box and above the roof. This produces a very coarse approximation to the shape we want:

Now comes the really important bit. The elements that are completely occluded will remain hidden, but those elements that are partially occluded we will subdivide them into smaller elements instead of just hiding them.

This produces a new set of elements. To this set we apply the same rule as before. Some will be entirely visible, some will be entirely occluded and some will be partially occluded. Once again, those that are partially occluded will be subdivided into a smaller set. Eventually the elements will be small to a point where it is not practical to subdivide again. This is where the process ends.

Here you can see the output of this method. Note that all the elements are boxes:

Obviously the cuts are not completely smooth. You still get these microscopic boxes. In my case this is not a problem at all. These volumes are sent to a voxelization phase. The tiny boxes are smaller than the voxel resolution so they are blended into straight features which later optimize very well.

I thought this was a nice technique. For sure you could use it to produce really bizarre objects. We may see some of that later.

Building Unimaginable Shapes

This is a very nice TED talk by architect Michael Hansmeyer. It goes straight into procedural generation. Here is some of his work:

I like what he says about "start thinking about designing the process, not the object". Here is the video. You can find a direct link here.

The desert, one last screenshot and video

I took this one last weekend. The location seemed nice to me.

Here is a short walk over the same area:

 

There are a few issues in this video. Some of the LOD switches are too visible. There are some noticeable discontinuities in the lighting that show in some distant cells. I'm working on fixing these issues, hopefully you can see past them.

Another desert video

Here is another video taken from the same desert.

 

You don't see far into the horizon because I only rendered an area of 2km by 2km. Also this particular walk happens on the top of massive mountains. I will capture one last video from the mountain base over the weekend.

Through the desert

Over the last few weekends I rewrote some of my 3D layers. I was bothered by the synthetic look of the Perlin and Worley functions I was using. It was not only that, it was becoming increasingly difficult to obtain different looks out of these functions.

The new functions are a lot simpler to use, they use real samples from nature. Here is one screenshot:

Some of these large rock formations would be a real headache if you only had generic noises. There are still a couple of Worley layers in there, actually those produce the features I like less about this terrain. I did not have enough time to replace them.


Here is a video:

   

Both video and image were captured from Sputnik, so please disregard the texturing. The mesh resolution is intentionally low. What you see is streamed over HTTP, bandwidth never goes over 400K/sec.

The Uncanny Valley of Procedural Generation

As a developer of procedural worlds, what worries me most is not failing spectacularly at my goals. My biggest fear is to produce something that looks believable, but still is somehow off. Even a seemingly perfect world could be rejected by your subconsciousness. You may not be able to put it into words, or point your finger at it, but you feel there is something wrong. 

To make matters even worse, it seems we can be collectively hypnotized into liking something just because it is a new way of doing things. Soon the novelty wears off and we realize the Emperor was naked all the time. 

We want to believe things look better that they do. For instance we know 3D graphics are a developing field so we are ready to forgive a lot, until something better appears and sets a new standard.

Remember this beauty?

This is Peter Gabriel's "Kiss That Frog". You can see the video here. It won a MTV award for special effects in 1994. I remember loving this video. It is hard to watch now.

This is not specific of procedural techniques. Humans are equally able to generate uncanny, ugly things. The problem is proceduralism makes it a lot easier. The world is not crafted by hand, any aberration in the algorithms will be mindlessly multiplied. It also depends on the degree of realism you want to achieve. If you are trying to fake nature, odds are your creation is some form of monstrosity that will not stand the pass of time.

I often wonder whether any sort of synthetic reality is doomed in the long term. At this point I don't know for sure, but I have two simple ideas to guide me across this maze:

1. Global rather than Local

Procedural methods can be divided into two large families, global methods and local methods. In local methods content generated for a given point in space does not depend on the content of neighbor points.

The Perlin noise function, for instance, can be evaluated locally. This means the output of the function depends only on the coordinates of the point, plus some constants. It also means many points can be evaluated in parallel. Since they are isolated from their neighbors, you do not need to compute any neighbors before evaluating a single point.

They are blindingly fast, but it comes at a cost: They do not have a soul. They do not produce any information. All what you see comes from a small seed of values and the specific ways these values are churned and shaken by these clever algorithms.

Because of their speed and fairly good results, they can be used in many subtle places, but they should not be the backbone of your world. Our minds are very good a discovering redundancy. All these methods are like a kaleidoscope effect, they can trick you for a moment but soon you start seeing the mirrors. And once you have seen them, the magic is gone for good.

Here is your typical multifractal Perlin terrain:

Just don't do it. We all know it is not real.

Another popular local method is L-Systems. This is when they are in their vanilla form, as context free grammars where symbols are replaced with no awareness of their surroundings. If used to produce trees, you soon have branches that intersect each other, or that go into illogical directions.

Here is one gem that illustrates this point:

Global methods, on the other hand, are closer to simulations. The value of a single point may depend on the values of very distant points. Imagine a fluvial erosion filter. A point at the base of a mountain may be largely influenced by a large streak of points uphill.

Global methods ere effective because they have cause-effect relationships built into them. This makes all the difference. It brings entropy into the world, it gives it time and history.

Here is an example showing some fluvial erosion. The patterns you see here are far more believable:

In the same fashion, most successful tree and plant generators use some sort of simulation or at least global constraints. For my trees I chose a global method that grows branches in full awareness of each other. It is a very simple algorithm and still beats the results you get from vanilla L-Systems.

The problem with simulations is they are costly to evaluate. There is information moving around so they are harder to compute in parallel. 

Consider this example. The location, shape and strength of a river will be determined by a water source many kilometers away. A visitor to the virtual world may encounter the river long before than the source, but still the source and everything between must be accounted for. For worlds that are generated on demand as the viewer moves this may be too much to handle.

Even then, you should always consider using a global method. It may make your solution complex and slower, but you will have something to show.

2. Steal from Mother (Nature)

Nature has already spent a lot of time and energy producing the patterns we accept as real. We already use them to texture 3D models, there is no reason why we couldn't go beyond that.

Here is a very interesting approach to terrain synthesis. It combines elevation samples from real sites from Earth and stitches them into new ways. This results in fairly believable scenes that can cover huge spaces without any apparent repetition.

In this case they used some samples taken from the Grand Canyon.

A similar technique can be used for smaller terrain features like rocks, cliffs and small boulders. It is possible to have a set of volumetric natural textures and map them over larger terrain features. 

The biggest issue is how to mask the repetition, but this can be done using Wang tiles. I have reworked many of my core functions to be like this and I like them better than my previous functions. I will be posting some results soon.

To sum it up, I think entropy matters. 

One last visit to the forest

Here is a slightly old video I took from the voxel forest. This one has a radiosity solution. It is still not there for me, it may be too dark, also it also has some bugs in the lighting of grass and canopies that I fixed after doing the video. Anyway I thought it could be entertaining to some of you.

Dude where is my castle?

I have been writing some new grammars lately. I realized that if my system was any good, it had to be able to do romantic castles like Neuschwanstein, Disneyland, etc. I don't really like this style, but there was no way to avoid it.

So here are a few screens of procedural kitsch:

Note there are no materials or texturing. This should help you see the grammar output clearly.

This is the same castle from different angles. It sits on top of a series of boxes which were produced by an earlier stage, when city blocks are created. It is not required for the boxes to be aligned, although they are in this particular instance.

The interior is properly connected by a system of doors and stairs. Even the round towers have spiral stairs. You could go in and fool around inside this structure.

Most of what you see here is parametric, which means very different castles can arise from the same grammar rules. The basic components that you find instanced many times over, like windows, doorways, ledges, can also be replaced.

If you have been following this blog for a while now you will realize that this castle is built out the same elements of the church I posted more than a year ago. As you can see it takes little effort on the modeling side. I have been very lazy about creating new basic components.

As usual there is a lot of room for improvement. I want to add little windows in the rooftops, gargoyles, better doors and windows, balconies, etc. I will probably revisit this style later, for now I will move to the next cliche, maybe a Mayan temple or a Japanese Castle. If you have one type of architecture that you think will prove unsolvable, please drop me a comment.