I've been researching on the Diamond-square algorithm and I came across this website which pointed me to the source code of Notch's Minicraft, and does a conversion of the algorithm as was implemented by Notch.
For the most part I understand the algorithm, but I can get my head around the specific expression found in these two functions:
private double sample(int x, int y) {
return values[ (x & (w - 1)) + (y & (h - 1)) * w ];
}
private void setSample(int x, int y, double value) {
values[ (x & (w - 1)) + (y & (h - 1)) * w ] = value;
}
I do understand x + y * w, but not (x & (w - 1)) + (y & (h - 1)) * w, and the article doesn't explain this besides stating that it serves to wrap-around.
I'm coding in python, but I don't think there's any difference between Java's bitwise & and python's, so I fiddled with it a bit but I still can't get it. One of the things I did was a loop that simulates varying x and y values and feeds them to that calculation:
import random
w = h = 257 # 2^8 + 1
for i in xrange(10):
x = int(random.uniform(0, 1) *255)
y = int(random.uniform(0, 1) *255)
print x, y, '|', (x & (w-1)) + (y & (h-1)) *w
# I used a less readable right-aligning version of the above to display the output:
# print str( x ).rjust(3), str( y ).rjust(3), '|', str( (x & (w-1)) + (y & (h-1)) * w ).rjust(3)
Output:
112 213 | 0
181 117 | 0
1 105 | 0
216 223 | 0
170 185 | 0
158 32 | 0
124 225 | 0
62 153 | 0
90 147 | 0
196 69 | 0
Unless I'm doing something fundamentally wrong here, it always gives me zero, unless x and/or y are equal to w-1, in which case:
256 15 | 256
21 256 | 65792
256 256 | 66048
In the actual algorithm the value of x and y seems to always be (if I understand correctly) somewhere between 0 and halfStep, where halfStep = stepSize/2, stepSize = featureSise which seems to be (in Minicraft's code) always hardcoded as 16 or 32. So according to my current understanding that expression would always evaluate to 0.
So I'm confused. I don't see how this is useful or how it actually works in practice... I know it works, but it seems like sorcery...
I understand how the bitwise & works, but that doesn't seem to help.
w and h must be powers of 2 (and represent the local bounds for x and y, respectively).
Then, w-1 and h-1 are sequences of ones. One for each bit of information which could possibly contribute to a value lower than w and h (and still be >= 0), respectively.
When you now evaluate the bit-wise and (&), e.g. x & (w-1), this will actually yield x % w, where % is the modulo operation in python, for x >= 0.
Thus, x is mapped to x if w > x >= 0 and otherwise x is truncated (zeroing higher bits), such that w > x >= 0 is satisfied.
The same applies to y and h.
Consequently, these logical operations are nothing more than evaluating mod on a bit-level.
For your code: Set w=h=256 and everything should work out.