First off, thanks goes to wpmathpub for the math markup plugin I’m using. It isn’t perfect, but it does the job. Ed. 1/11/2014: Post now uses latex.
Honestly, this series should not even be called Infinite Terrain Generation. We’ve just about stopped even talking about how all this applies to terrain generation, and instead just focused on “how to map the 2D integer space to the 1D number line such that there is a one-to-one relation.”
But, of course, this title would be too long to place in the title.
Anyway, this should be the last post describing all theory. I’ve got the groundwork - all that’s left is the implementation. Yesterday, I explained a method to get a unique integer seed assigned to each coordinate in an infinite 2D plane. It basically goes like this:
- Decide on some method of mapping the 2D plane to the 1D number line. It can be using boxes, diamonds, a spiral, or something else.
- Determine a point, consistent across all the boxes/diamonds/sides of the spiral, to use as a reference point.
- Determine a way to get this reference without needing to follow the pattern.
- Determine a way to easily obtain the 2D point from the nearest reference point.
In the previous part I was stuck on #4, and couldn’t decide on a good way to do #3. After mulling it over, this is the fruit of my efforts:
What is this I don’t even
Now, if that monstrosity of a steno pad page didn’t scare you away, open that image up in another tab or window - I’m going to be referring to it a lot in this article. I’ll going to call it the main image.
The top right and center pieces you might recognize - they’re from the previous post. The top right describes the scheme I’m using. The top-center point of each box, or the left-most point in the unrolled box displayed there, serves as my reference point. The offset is the distance from the reference point on a box to any given point on that box. To obtain a seed, I take the reference point’s seed (which, as we’ll see, is easily obtained) and add it to the offset. The center piece is simply a graphical representation of what I’m doing, on a 2D plane.
There are three other things I added. We’ll get to the pseudocode-looking thing on the right side in a little bit. First, let’s start with the left side.
On the very, very bottom left, we have me writing out the sequence of reference points for the first seven boxes. The first reference point is 1, arbitrarily. I could make it zero. I don’t think it matters that much, except to make the sequence neater maybe. Above that (yes, I know I’m writing bottom-to-top, bear with me) I write out, more explicitly, the first four reference box sequences (this time from bottom-to-top). Reiterating previous points, the first reference point is one. Then, the second reference point is two - 1+1 + 40. The third is 10 - 1 + 1 + 42. The fourth is 26 - 1 + 1 + 44 + 42. There is a pretty obvious pattern being established here. First, just take the first two points as given - one is 1, and two is 2. From then on, you take the current box number, subtract it by two, multiply by two, and add it on to the previous box’s reference point.
For example, if you’re on box 5 and want to get its reference point’s (which is (0, 5), following the (0 , \(\max(\|x\|, \|y\|)\)) rule from the previous post) seed, you
- Take the current box number: 5
- Subtract it by 2: 3
- Multiply it by two: 6
- Add it on to the previous box’s reference point: Obtained by repeating the above three steps.
This doesn’t go on forever; once you get down to two, we know the previous box’s reference point is 1, and you stop.
I didn’t just pull this 4*x sequence out of nowhere, by the way. Think about it this way; when you move up the box ranks, you’re keeping the corners and moving each of the four sides out, as illustrated here:
Left: Here’s the original box. Center: Imagine shifting all the points outward. Right: Then, Fill in the gaps with new points (marked with asterisks).
There will always be 8 new points, no matter the size of the original box. Do it for yourself with a larger one. So, every time you add on 8, or 42, points. Then, you’ve got to add that onto what’s already there - the points you moved outward, or the 4x2 in the picture above: 42 + 42 = 44. Finally, you have to add that onto the previous reference point’s seed value to get the current one.
Now that I think about it, it would have been more logical to use 8*x rather than 4*2x. I may end up changing it to that in the code, but for now, let's just stick with what we have on the paper.
At the top-left of the picture (following the upshot arrow from the bottom left), we have the mathematical notation representation of what we’ve accomplished. (To be rigorous, I should have added on a b > 1 at the end - if we try to use the formula on the first box, we end up with a negative value, not 1).
Ok, so we’ve got #3, “Determine a way to get this reference without needing to follow the pattern,” now. We still have to determine #4.
After staring at the diagram at the top left for at least an hour, I started remembering something called the Hamming Distance. Essentially, it’s a concept in computer science you use to determine error. I don’t remember everything about it, but I do remember that it simply involves checking each bit of a binary string against every other, like so:
Hamming Distance: just the number of digits that are different between two binary strings.
It doesn’t really work here, because we’re not working in binary. However, I discovered something interesting when thinking about this. If you look closer at the box drawing at the center of the main image, you’ll see that I drew a bunch of little numbers next to each of the seed values corresponding to each point. These numbers I obtained by finding the sum of the absolute value of the difference of the x and y coordinates of the point and the reference point. If you didn’t quite follow that, here’s an example: Take (2, -1). Its reference point is (0, 2). Then, you take the x and y coordinates and subtract them: \(2 - 0 = 2\), and \(-1 - 2 = -3\). Finally, take the absolute value of each and add: \(2 + 3 = 5\).
Ed. 1/11/2014: Almost exactly two years later, going back and editing this post since the math markup is broken, I realize that this is actually the $$L_1$$ distance of the coordinate from its reference point, and it's obviously going to be broken for the left and bottom sides of the box. I'm going to keep the original text for posterity, though; it's interesting going back and seeing how different my thought process was.
If you actually look at (2, -1) on the graphic, though, you can see that for this point, this magical, fairy, made-up “distance” (I’m going to call this the Asdf distance, because I have no clue where this comes from or why it works) is indeed the offset from its reference point. However, this method only works up until you pass the bottom-right corner of the box. After that, you start getting some bad numbers. After some further observation, though, you can see that for the points left of the reference point, you can subtract the Asdf distance from the next box’s reference point to get the seed value. For example, take (-1, 2). Its distance is \(]\|-1 - 0\| + \|2 - 2\| = 1\). The next box’s reference point is (0, 3), whose corresponding seed is 26. \(26 - 1 = 25\), the seed value for (-1, 2).
There’s still one part of this entire thing that subverts this rule though, and it’s the bottom side of the square (not including the corner vertices), where \(\|y\| < \|x\|\) For example, (-1, -2)’s Asdf distance is 5, which is a duplicate of (-2, -1)’s. They’re on the same side, left, of the reference value, so they’d get assigned the same seed according to our rules. So, we’ve got to have some special rule for these vertices. Looking at the main graphic again, you can see that for the bottom side, I wrote some “+x”s, denoting what their Asdf distances should be. These pluses follow a 2*x rule, with the x being the distance from either the bottom-left or the bottom-right corner vertex - whichever is closer (in the case of the vertex directly below the reference point, it doesn’t matter which corner vertex you choose). So, all you’ve got to do is take the current box number and subtract the point’s x value from it, multiply it by 2, and add onto the Asdf distance - if it’s on the bottom corner. To tell if the point’s on the bottom corner, you first make sure the y value is negative. Then you compare: if abs(x) < abs(y), then the point is on the bottom side. “Moar examples!” you say, and I say, ok, fine. Take the point (1, -2). The y coordinate is negative, and \(\|-2\| = 2 > \|1\|= 1\), so the point is on the bottom side. The box number it’s on is 2. Its Asdf distance is 5. Its true Asdf distance, however, is \(5 + (2 - 1) * 2. (1, -2)\) is on the right side of the reference point (denoted by its positive x value) so you add 7 to the reference point’s seed, 10, to obtain the seed, 17.
So, now, the right side algorithm becomes clear. Summarizing all the information in this entire article, we get this (which is also scribbled on the right side of the main image):
- Get the Asdf distance.
- If y = -box and abs(x) != abs(y) «– Checking for bottom side, non-corner vertex
- Add (box*(abs(y) - abs(x)) to the Asdf distance
- If the x value is positive or zero «– Checking for left side of reference point
- Get the current box’s reference seed value
- Add the Asdf distance to that to obtain this point’s seed value
- If the x is negative «– Checking for right side of reference point
- Get the next box’s reference seed value
- Subtract the Asdf distance from that to obtain this point’s seed value
And we’re done.
Next time we work on actually implementing this algorithm. While this seed calculation was tough to come up with, it will be very easy to implement - it’s just a bunch of if statements and math calculations. Integrating the diamond-square algorithm between squares of terrains will be the harder part, code-wise.