Ok, so I’ve gotten my terrain generator spitting out a single chunk of terrain. However, I’ve run into a problem that has had me stuck for a while. The problem is this - How do you get infinite generation of terrains, while still keeping theterrains you’ve passed by permanent? It seems pretty simple - just make an array of terrains and add on as you go, right? There’s a couple reasons this won’t work:
First, arrays are finite size, and you can’t resize them without a lot of effort (on the computer’s part, of course). Not much way getting around that.
Illustration of the problem when using arrays. Everything must be shifted over to make room for new terrains on the left.
Second, how do you manage the “origin?” Obviously, you’re going to need some way to refer to the terrains you want to display. For example, say you’re on some block of terrain 1 block right and 2 blocks up from where you started on. We’ll refer to this as terrain (1, 2). Then, you walk left 3 blocks, ending on terrain (-1, 2). Obviously, you can’t store this in array index [-1][2], because there is no such thing as a negative array index. You’d have to shift everything over before generating this new terrain at (-1, 2), causing a lot of overhead. Additionally, you’d have to have some coordinate stored in the origin that would shift every time you go into negative coordinates, adding additional complexity. To get around this, maybe you’d say, well, make these arrays-of-terrain-blocks fixed size, say, 64x64. Keep the origin at the top left corner of the array-of-terrain-blocks going up and right, and just add another array-of-terrain-blocks when you walk to the left, so that you don’t have to shift anything. Well, then you have the same two problems all over again, just macro-sized.
Using an STL vector solves the first problem, but not the second. Using an STL list solves both problems, but introduces another, albeit smaller, one. Traversing through the list, when you get to large numbers, is going to be a lot of work. Vectors and arrays are nice for traversal - say you want element 101. you just say hey, I want the terrain at 101, give it to me, and the computer does. In a list, however, you say hey, I want the terrain at these coordinates, and the computer has to labor through all the terrains zero through 100 to get to terrain 101. This is because in a list, only terrain 100 knows where terrain 101 is, and only terrain 99 knows where terrain 100 is, and so on back down the line. A vector or an array doesn’t have this dependency because they’re both exactly sequential. Lists just take space wherever they can find them.
Well, enough with the data structures. Obviously they weren’t going to cut it. I probably would have chosen the list, though, just because it had the least downsides. Then I found this paper. (Actually, I’m dramatizing it a little bit. I found this paper a while back, and used some of the concepts from it. Props to the guy who wrote it; it gave me a lot of good ideas. Anyway.) The paper suggests using the terrain location as the seed to generate each terrain. Essentially, when loading the next terrain, just feed the terrain’s location to the random seed and run the generation algorithm. Ok, sounds simple enough.
Turns out it’s… not quite. It would work perfectly fine for generating a single line of terrains - just use the number of the terrain you’re on as the seed, with the one you start on as terrain 0. As you walk right, feed the random number generator more and more positive values, and the opposite as you walk left. However, in the case of 2D terrains, what you need to do is map a one-to-one relationship the 2D plane to the 1D number line. What’s that mean? Well, take this image:
Disclaimer: I’m drawing with a mouse.
Essentially, you want to get a unique number from each pair of numbers. It’s harder than it sounds - if you just add the x and y coordinates, you’re inevitably going to end up with duplicates, like 1+2 = 3 and 2+1 = 3, generating the same terrain twice in two different places. You can’t just go across the rows, adding one each time, as I did in the picture, because there’s infinite terrains for every row - what would I use for (1, 4)? Or (100, 300)?
I thought about it for a while, and then I gave up and asked my dad (who is a mathematician). He told me an ingenious solution. It’s basically this:
Still drawing with a mouse.
Instead of going across the rows, you go diagonally. This way, there’s always a finite amount of coordinates across each pass of the diagonal.
No wait, this is wrong. I need negative numbers too. I sat and thought for a while, and then went to see my dad again. As always, he comes up with a solution - multiple solutions, in this case:
Wish I didn’t leave my tablet at my apartment for the break.
With the box and the triangle, first you start with 0 at (0, 0). Then, picking an arbitrary side or corner on the box, go clockwise or counterclockwise. It’s an arbitrary decision. As for the spiral method, it’s self explanatory - start with 0, and count up as you go around the spiral.
The problem with this method is that every time you want to grab a terrain, you have to go through the arduous task of going around the spiral, or going around a box - and then the next, and the next, and the next, incrementing a counter, until you find the coordinate you wanted and thus spawning the terrain. Essentially, it’s no better than the list method - perhaps even worse, for larger numbers. However, If I can think of some formula that describes one of these patterns, then I’ll be set. That means finding some relation between the 1D number line representation and the two coordinates, like z = Cx + Ky, or z = x^y, or somesuch. I haven’t thought of it yet, but I’ve still got a part 2.