So this wasn’t actually a short week or anything; I didn’t delay this post because we didn’t have a fourth episode. No, I was just sick Thursday morning. I suspect Shamus might be trying to get back at me for crushing all of those sleeping pills into his tea last week.

Also, for those of you interested, Josh Plays is totally actually really coming back tomorrow. For real this time. Like, the post is (almost) all written, I just need to finish the last bit and compile all of the images for upload. And of course there will be the fourth Spoiler Warning episode next week too. And hey, Shamus might have even written an article for the Escapist this week! (But I get bonus points if Shamus only remembers that he was supposed to do that when he reads this post.)

Still, I guess we’d better get started with the actual thing and stop whinging on about technology and development platforms. First, let’s look at texture mapping…

(We don’t have a lighting system yet, so I’m just painting the sides of cubes darker than the top. That’s close enough for now.)

I’ve slapped the default stone texture from Minecraft onto this landscape so I can illustrate the thing I want to work on. As in Minecraft, flat stone can look kind of dull if you see too much of it at once, and I’ve deliberately designed this scene to show us way, way too much of it.

This texture is kind of bland. I mean, it’s a scattering of grey values that barely deviate from each other. Of course, this is by design. Notch knew what he was doing when he made his textures. Some well-meaning modders come along and try to make the textures more “interesting”, and you wind up with:

Which sends you right into quilt-world. Sometimes people try to compensate for this by bumping up the resolution. That can mitigate the problem, but it’s not a solution. The issue at hand is that textures repeat exactly one per cube-face, so looking at lots of cubes means lots of repetition. This isn’t a design flaw or anything. It’s part of Minecraft’s distinctive look.

But what if we broke from that? What if textures covered larger areas? Let me grab a random texture from Google image search and set up the texture system to stretch the texture over 16 blocks. I’ll be using this texture:

And it looks like this:

You can see that spanning many blocks lets us have large patterns. We could use this to have colored strata of rock or variations in brightness. I know my texture here isn’t ideal, but I’m content that this would look better with more suitable art.

However, this leads to some problems mapping textures. All this fancy detail will work against us if we can’t get it to line up. Think of it like hanging strips of wallpaper. We can put two strips next to each other, and their patterns will line up to create a seamless whole. But if some deformation makes one part of the wall “longer” than the other…

At the top of the wall the two strips line up, but then the one on the left has to fill an alcove, which covers 3 meters of wall instead of just 1. By the time we exit the alcove, the strip on the left has run too long and there will be an ugly seam where it meets its neighbor.

Texture mapping theory can get kind of dense. It’s basically a more convoluted version of the age-old map projection problem. Or I suppose it’s the map problem in reverse: We have a square image and we want to project it onto a complex world with as little distortion as possible. It’s not a problem you “solve”, but a series of trade-offs you juggle.

In Half-Life 2: Episode 2, Valve actually created a custom shader that would wrap a texture onto the complex topology of a cave. They did this so that an artist wouldn’t have to drive themselves mad trying to get rectangles to line up on stalagmites and other topologically difficult items. It just smears a generic rock texture all over everything.

This works because “rock walls” don’t have an expected orientation, and are very forgiving with regards to stretching. (Nobody’s going to look at the wall and think the rocks are “sideways” or “too big”. If you tried this with a brick texture it would look ridiculous.

We are not going in that direction. We’re aiming for low tech. We’re aiming for simple. We want something that will produce working results on shapeless rock and dirt, and also on non-rotatable stuff like bricks.

So here is my super-secret ninja technique:

int u = x + y;
int v = z;

I know, right? Brilliant. I’ve already filed for the patent and everything.

This is as simple as it gets. The texture follows the world coordinates. If you move one unit in the world, you’ll move one texture frame. Here, let me apply a test texture:

I suggest using a texture like this one whenever you’re dealing with texture mapping problems. It’s orient-able. (You can tell if it’s backwards or upside-down, which doesn’t matter in our case but can be a problem if you’re working on something where textures need to face a certain way.) The letters form a clear progression from left to right, so if your texture doesn’t line up you’ll see the letters stop following natural order. Same goes for the rainbow color-shift: If you see purple next to green, then you’ve botched something. If the textures are working right, both the lettering and color-change should progress naturally.

Let’s apply it to our world:

We’re just worried about walls right now, so I’ve made the floor solid color just to avoid confusion.

You can see the rows I’ve highlighted here. They line up whenever they meet, even though the walls have different shapes. You can see there’s a hole in the wall on the right, where an “N” block is missing. This means that row is longer than the other two, yet even then it lines up. The texture can wrap around a mountain, or a continent, or a one-meter pillar, and you’ll always be able to walk all the way around it without seeing a seam.

Here’s the backside of the hill:

Sure, the letters are backwards, but in the case of terrain textures this generally doesn’t matter.

The rule is simple: When we move east or north, increase the texture by 1 section. Corollary: If we move west or south, decrease the texture by 1. The only downside is:

Let’s assume we’re looking at a really big pillar from above. (Note also that the vertical arrow should point UP, assuming the top of the image is north. No big deal. The principle is the same.)

The problem areas are where you’ve got a wall running up one axis but down the other. It moves east, goes forward one letter, then it goes south, and goes back a letter, then forward, backward. It looks like this:

We we end up looking at repetition and mirroring. See what I mean about trade-offs? We’ve left behind the drawbacks of Minecraft’s texture system and are using a new set of drawbacks.

Lemme put a really busy texture up. Also, we’ll put a different texture on all of the surface blocks so we have even more contrast. Here are some high-contrast textures at work:

And here is the same hill from the “bad” side:

I’d say the texture itself is more ugly than the mirroring and repetition, so maybe this wasn’t an ideal test. Anyway. You get the idea.

Next up is something I’ve wanted to do for over a decade. Since my time at Activeworlds, I’ve always wanted to make a borderless tiling world. A world where you can go off one edge of the map and seamlessly enter on the other, where if you travel in a straight line you’ll eventually end up back where you started. The last time I saw that in a game was in Magic Carpet in the mid 90′s.

I like borderless environments so much better than games like Fallout 3 or Oblivion where it just puts an invisible wall around your playpen and tells you “NO!” when you try to leave. I also like it because it lets you walk around the world, which is kind of neat.

Let’s try it:

I guess… I guess you can’t show this off in screenshots. Oh! Unless I make the world really, really tiny. Let me adjust the size down, and build some distinctive landmark:

And if we look up:

The world map is 32×32 meters. Just enough space for a suburban house with a modest yard, I think. Our view reaches 144m in every direction. Keep in mind those question marks in the distance are the exact same question mark I have in front of me. They’re not copies. Those are the same polygons and blocks. If I break a block in front of me, I see it vanish from the pattern in the distance.

All three of my kids saw this in turn, and each one asked: Will you be able to see yourself like this?

Well, keep in mind that right now there IS no concept of a “self” model. Or any kind of model. There are cubes. That’s all we have, and there aren’t even any systems in place for drawing other sorts of stuff. (Items, foes, NPC’s, space marines, etc.) But if I keep with this project and if I follow the plan in my head, then looking all the way “around” the world like this would cause you to see everything except yourself. (Because your character model isn’t usually drawn in a first-person game.)

But this is academic. The point isn’t to make a bizzaro world where you can see things tile. The point is to make a borderless world, and this little stunt proves that it works.

And we almost made it through a whole episode without fighting any darkness-related creatures. Damn.

Oh well. At least we have coffee.

(Nerd!)

If you remember from last time, we’re taking tables of random white noise and expanding them to create “interesting” patterns. Stuff like this:

Now, I really don’t want to have the next bunch of images be black & white scramble squares. That’s boring and it’s actually hard to see the effect I’m talking about. So I’ve altered my program to output example images that will use color-blending to make the gradients more clear. So the above image now looks like this:

Just remember we’re not really dealing with color data right now. We’re actually just generating heaps of numbers between zero (dark blue) and one (red) and this color-fade makes it easier to see what we’re doing. Okay? Great.

In the image above we’re looking at around 16×16 pixels, give or take the partials on the edges. We need to be able to expand this data and come up with values between these points.

In the previous entry, I put in a system based on cutting a quad (rectangle) into a pair of triangles and blending across it. Doing so yields this:

(Am I the only one who thinks that circle with a tail in the middle of the image looks kind of like the Mandelbrot set?)

I’ve been using this snippet of code for years. It wasn’t until I posted the last entry that I even questioned it. Someone asked why I wasn’t using bilinear filtering and I realized I didn’t have a good reason. There might be a good reason, but I hadn’t even considered the question. I’ve been using the quad-fade code for so long I just sort of take it for granted.

See, the quad code has two important features:

1. It is fast. This is probably the fastest possible method that won’t create nasty seams.
2. It breaks things into triangles.

The triangles thing is important in certain cases. Like, in collision detection. It’s handy if the player is standing on a square of terrain and I want to see if they’re ankle-deep, or floating above it, so that I can nudge them up or drop them down according to the long-understood rules of gravity and… walking up hills. If they’re walking on a triangle (and you are always walking on triangles in a 3D game) then I don’t want to treat the surface like it’s rounded. That will not look right.

So I used this code out of habit. I saw a blend-four-values problem and pulled out the hammer I always use on four-value problems. But is that the right choice to make here?

The quad blending begins with four values. Say you’ve got four pixels you want to blend together:

We take this square and divide it into a pair of triangles. We can do this by cutting from upper-right to lower-left, or from upper-left to lower-right. Whatever. It’s best to alternate your cuts in a checkerboard pattern to avoid ugly artifacts. (Alternating our cuts will lead to the “diamond” pattern you see in the earlier image.)

If the point we’re trying to generate falls in the lower triangle, then we blend between those three points. If it falls in the upper triangle, we use the corners of the other triangle. If I’m generating point X on the image above, then I create a value that is 1/4 cyan (upper left) and 3/4 orange (lower left) because we’re about 3/4 of the way down the image. Then I take that blended value and mix it half and half with dark blue (lower right) because we’re halfway across the image. It might sound confusing, but the code to accomplish this is actually a good bit smaller than this paragraph and only slightly less readable.

The downside of this is that the points aren’t given equal weight. The two points that form the right angles can’t effect the middle. The exact center is a blend of the two blues, without any weighting from the orange or green. (Please don’t correct me and explain that these are peach and avocado or whatever artists call these colors. I’m making polygons, not a salad. I’m an engineer, and the only color names I know are the ones from the Crayola 8-box. Doghouse Diaries and XKCD have already slain this horse and gave it a good pummeling afterward. (Insert “pummel horse” joke here.) Let’s move on.)

Instead, let’s try bilinear filetering. (“bi” meaning two-way. Yes, just like the sex thing, you complete juvenile. “linear” meaning in a straight line. So, a couple of lines? Let’s try it.)

Bilinear filtering gives the values a more equitable distribution. To solve for the same x as before, we would blend halfway between the top two pixels for point A. Then we blend halfway between the bottom two for point B. Then we blend 75% of the way from A to B for x. Clear? I hope so, because I want to move on.

Oh, the same square with biliner filering looks like this:

Note that we needed to do three blending operations to get this value, as opposed to two blends for the cheapo blend I’ve been using. Now, a single blend is nothing. A few math operations. But remember what we’re doing with this data. We need to do three blends per pixel. But we’re doing this in three dimensions, so we need to generate two pixels and blend those together for a single octave of noise. And we generally want to combine about 8 octaves to make our noise interesting. So…

That’s per cube. Oh, and most cubes need 2 bits of noise. (One to shape hills and one to dig caves, for example.) And a single 16-meter block of the world needs 4,096 cubes. And in a scene, even at the lowest possible visibility settings you’ve probably got around 400 such blocks rolling around in memory. (I think Notch calls them chunks. I’ve taken to calling them nodes.)

So even a crappy low-visibility scene needs to perform 183,500,800 blend operations. Also keep in mind that a single blend operation is…

inline float Lerp (float n1, float n2, float delta)
{
  return n1 * (1.0f - delta) + n2 * delta;
}

Looks like a subtract, a couple of multiply operations, and an add. We need to do that, one hundred and eighty-three million times. That will wipe the smug off the face of your quad-core 4Ghz processor in a hurry. Your machine is going to work for this scenery, kiddo. So no, increasing the number of blends we need to do by 50% is not something to be done lightly. We need a really good reason before we start dumping more CPU juice on the problem. We need something important, like marginally better graphics or something.

Anyway. So this is what we have now:

And here is the same thing generated with bilinear filtering:

So… is it worth it? It’s hard to tell. Obviously it looks better in RAINBOW VIEW, but that’s not what the data is used for. In our program, the data is used to make caves. Does it make better caves?

True story bro: As of writing this paragraph, I have yet to try it. I honestly don’t know, 1,200 words into this post, if this is a complete waste of time or not. Let’s find out.

That didn’t take long. Okay, so I made a huge volume of noise caves with the threshold set at 0.5. (In English, it should be a roughly even 50-50 mix of air and solid… block stuff.) First, I take a screenshot of a nice bit of cave using the discount triangle-interpolation blending:

And now the exact same location, but generated with bilinear whatsits:

Is one of these really better than the other? It’s hard to say. What’s “better”? More visually interesting? More fun to explore? More realistic? Is the slow one really 50% slower?

This sounds like a decision to make later, when one of these variables matters. I’ve got both systems sitting side-by-side and can flip between them as I need. I guess for testing it makes sense to stick with the faster system anyway. If I stick with this project then eventually I’ll have to add a bunch of timers to keep track of where all the CPU is going, and that would be a good time to come back to this.

Also, in the process of writing the new filter, I managed to mess up and make this:

(I was blending between the wrong corners.) It’s useless, but kind of pretty in a strange way. I like it because it looks like one of those shuffle puzzles. I suppose it would be considered evil to present this as a shuffle puzzle and let someone drive themselves insane trying to get things to match up?

So that’s what we accomplished today… nothing! This riveting series will continue in the next entry unless there isn’t one.

I’ve done it! I finally got rid of Shamus! Now I rule Twenty Sided! Mwahahahaha!

Good thing Rutskarn was able to hire those Algerian terrorists. Even though they might not have actually been terrorists. Or Algerians.

Or people.

Okay, so Shamus might have just gotten sick and didn’t make it to the recording session. Which means he could recover and be back to posting on this blog any day now. Cherish the Shamelessness while it lasts!

Note that in the context of this project I’m going to discuss Perlin in terms of 2D images, but I’m using it in 3D. It’s just easier to show you what we’re doing in 2D.

We begin with a basic image of really random noise, which I will depict as a 2D greyscale image. The more random the better. We want areas of light, dark, and medium brightness. We want it to be really diverse overall, but have small local clusters of bright or darkness. We don’t want large areas to be homogeneous, and we don’t want the small areas just just be a scatter of white and black pixels. We can accomplish this a lot of ways. I could churn out a bunch of values in a random number generator, for example. Or, we can just open up a new image in your Photoshop of choice, crank up the noise filter on a blank image, and hit save.

Awesome, right?

No. Obviously pure noise is boring.

To make Perlin noise…

…we have to sample this image at different resolutions. Massive resolutions. Bigger than we would want to bother keeping in memory, really. What we do is take this noise and kind of zoom in on it. For example, here are the four pixels in the upper-left of our noise image.

Blending between these four values, we can come up with values in between. If it asks for the value 20% of the way across and 80% of the way down, we get this:

To be clear: We’re not calculating ALL of these values. It only creates the one pixel that was requested. I’m just showing you how it arrives at that value.

The neat thing is, I already had 90% of the code needed for Perlin Noise. For those of you reading through Project Frontier, check out MathInterpolateQuad (). It has everything you need for doing the above.

The terrain generator is feeding us coordinates. We’re dividing those values by a thousand, so that it would require a thousand samples (a thousand meters of scenery) to cover the gradient from one edge of this four-pixel square to the other. Of course, if we stopped here we would have some really boring, super-flat scenery.

So we take another sample. Instead of ¹/_1,000, this one is taken at ¹/₅₀₀. Then we take another sample at ¹/₂₅₀, and another at ¹/₁₂₅. Each level of noise is at twice the frequency of the one before. Then we add all of these samples together, giving them all equal weight. We average them.

The upshot of all of this is that we get this large pattern of interesting noise.

This might not look terribly useful, but we can use this to generate interesting topography. Obviously we could use this to make hills where brighter = taller. But we can also use it to generate underground scenery. Let’s say we set a threshold. Everything above a certain brightness will be hollow, and everything below that threshold will be solid rock.

Which gives us a system of caves. If we set the threshold higher, then instead of large caves we’ll get little pockets, like Swiss Cheese.

If we take a narrow range of values above one point and below another, then we get a bunch of passages, all twisty-like.

So let’s take this noise and feed it into our cube-world and see how it looks:

This is just raw Perlin output. I’m not doing anything fancy with it at this point. Eventually it might be worthwhile to combine different sets of noise. (Perhaps one to make hills, and another to bore tunnels in the hills.) Or to set up different ways of deciding what’s solid and what’s empty. (Mess with the thresholds.) Maybe I’ll stretch noise along one axis to make tall or long caves. Or flatten out the bottoms to make Star-Trek style caves with lumpy walls and floors level enough for championship billiards. (A classic trope. Actually, is it a trope? I’ve never seen it officially listed.)

One of the things I wanted for this project was to experiment with noise like this, and see what other sorts of shapes and places one can make.

So now we have a foundation for making scenery. I’m sure we’ll come back to this when it’s time to work on the output.