|
Yeah this wasn't covered well in the article. Go back to the article and look at the section just below the first mention of Maximum-Length LFSR. Take a look at that list of numbers and notice something; every number from 1-15 is output once and only once. That's a property of Maximum-Length LFSRs; they output each number in their range once and only once. So, for example, a 17-bit Maximum-Length LFSR will output every number from 1-131071, just in random order. The Wolfenstein code separates the output of the LFSR into X and Y coordinates. Since the LFSR will visit every possible number exactly once, it will visit every possible combination of X and Y coordinates exactly once. You can look at the 4-bit Maximum-Length LFSR again. Split each number it outputs into 2-bit X and Y: 0001 | 0,1
1000 | 2,0
0100 | 1,0
0010 | 0,2
1001 | 2,1
1100 | 2,0
0110 | 1,2
1011 | 2,3
0101 | 1,1
1010 | 2,2
1101 | 3,1
1110 | 3,2
1111 | 3,3
0111 | 1,3
0011 | 0,3
You'll see that it hits every point on a 4x4 screen exactly once, in random order.The caveat is that it doesn't seem to hit 0,0. This is because an LFSR can't go to 0, otherwise it gets stuck there. However, I believe the ASM code was incorrectly translated by the article author. For example the author seemed to forget to translate the "dec bl" instruction into the C equivalent, which would subtract 1 from the y coordinate and allow visiting 0,0. |