|
Post by Malban on Sept 29, 2017 16:37:24 GMT -5
I had a look at the Random() BIOS function ... is that one of the worst pieces of software written or am I totally blind today?
edit: I WAS BLIND - SEE BELOW ANSWERS!
;-----------------------------------------------------------------------; ; F511 Random_3 ; ; F517 Random ; ; ; ; This routine generates a random 1-byte number, and places it in the ; ; A register. Random_3 runs through the random number generator ; ; algorithm three times. The random number seed is stored in the ; ; three bytes pointed to by $C87B. ; ; ; ; EXIT: A-reg contains the generated random number ; ; ; ; All other registers are preserved. ; ;-----------------------------------------------------------------------;
Random_3: PSHS B,X LDB #$02 BRA LF51A
Random: PSHS B,X CLRB LF51A: LDX Vec_Seed_Ptr LF51D: LDA 1,X ROLA ROLA ROLA ROLA EORA 2,X RORA ROL ,X ROL 1,X ROL 2,X DECB BPL LF51D LDA ,X PULS B,X,PC Not only that "LDX Vec_Seed_Ptr" is dangerous [in combination with the indexed roling] (as mentioned by Kristoff Tuts) ... what does this roling accomplish? Can the whole "Random" function above not be reduced to:
Random: LDA Vec_Seed_Ptr ROLA STA Vec_Seed_Ptr RTS Ok - or doing that 3 times...
Or am I totally blind? The other random seeds are playfull - but ultimately "A" is only loaded with seed 0 and that one is in no way influenced by any other seed...
Malban
|
|
|
Post by thomas on Sept 30, 2017 10:46:28 GMT -5
I myself thought this was a variant of a polynomial counter en.wikipedia.org/wiki/Linear-feedback_shift_registerThis is on my list of 'things to really delve into' one day - I believe the idea is used in various places back then to generate not only random no. but also entire 'worlds' by carefully selecting the function and start params (e.g. Pitfall, Boulder Dash). on the Pitfall post mortem David Crane says that he used a polynomial counter and looked for a specific start value for his random no. generator that resulted in levels that were 'easier' at the start www.youtube.com/watch?v=MBT1OK6VAIU&feature=youtu.beI'd also be interested in more info., esp. in improvements that use less cycles, if anyone has some..
|
|
|
Post by Malban on Sept 30, 2017 11:54:56 GMT -5
I again looked at the Random() function of the BIOS. In the meanwhile I think what Kristoff stated in vectorgaming.proboards.com/thread/1329/random#ixzz4fOYFbmQgis wrong. And the function is working. 1) What I missed was, that the ROL takes the carry flag into account, the ROL ,X that I falsely accused of being the only instruction that matters does take into account the other ROLs and COMs etc since it uses the carry flag. 2) I think what Kristoff missed is that in the beginning of the function "Vec_Seed_Ptr" is read which is a pointer to the Random seed(s), and is NOT supposed to be the address of the random seed. It might be confusing, that the random seed the BIOS actually uses is only two bytes behind the pointer to the seed. Malban PS I changed the title of the thread!
|
|
|
Post by Kristof on Jan 16, 2018 12:39:50 GMT -5
You are right Malban, the random function is working because the Vec_Seed_Ptr is filled in with value 0xC87D (the address just behind this Vec_Seed_Ptr 16bit-pointer). This initialization of the Vec_Seed_Ptr happens during reset by the BIOS-function initialize_OS_RAM at address 0xF16E. So, having said that my initial assumption was wrong as long as you don't tamper with the bios-ram-variables, which of course I always like to do because I needed all the RAM I could find during the Vector Pilot development and also during all other developments. So, during the Vector pilot development I reclaimed the 2 byte locations at Vec_Seed_Ptr to be used for other purposes and voilà... The random-function started to crash for previously mentioned reasons. I have no idea why the bios developers decided to introduce a pointer to the random-seed, since it is never changing (at least not by the bios functions). Conclusion: if you don't need all the RAM that you can find, leave Vec_Seed_Ptr intact.
|
|
|
Post by mikiex on Jan 18, 2018 16:07:01 GMT -5
I made use of a shorter routine it was a basic LSFR. I had issues with the vectrex ones distribution when I used it for particles.
|
|
|
Post by Peer on Dec 4, 2022 5:02:11 GMT -5
With Vector War being over, the forum seems to have gone rather quiet again. Let's do something about that: Last week, by accident, I came across the vectrex BIOS Random() routine. Again. I had been working on patching and fixing the timing of the BIOS Print_Str() for the Hitachi 6309 processor. As it happens, the code of the Print_Str() routine is immediately followed by the code of the Random_3() and Random() routines. I had successfully managed to get Print_Str() working, so I decided to have a closer look at Random() and try to finally fully understand how it works in detail and why it performs to badly in terms of "randomness", and probably to also see if there possibly exists a simple fix to improve the random number generation. I think I now do fully understand how Random() generates its numbers, and I think the routine is actually not that bad at all. I also think that the original GCE BIOS designers did their homework and research, when they decided on implementing it in the way it is. To a certain degree at least. The routine itself is not bad, but it is just not well suited to being used in they way it is used by the BIOS itself and alsonot that well suited to certain applications in game programming (see e.g. here).
If there is more interest in the specific details, I'll be happy to elaborate. But not right now, as that will likely require writing some larger text, and I am pretty tired at the moment. Many Cheers, Peer
|
|
|
Post by Malban on Dec 4, 2022 6:30:19 GMT -5
Yes please :-)!
|
|
|
Post by D-Type on Dec 4, 2022 7:21:19 GMT -5
Yeah, it's an interesting topic. My Forth to BIOS API test words print a random number of asterisks to the command line indefinitely, giving a random jaggedy line scrolling up the screen. From that, you could see lots of repeated patterns, so a somewhat compromised function, it would seem.
|
|
|
Post by Peer on Dec 4, 2022 8:59:15 GMT -5
Had not expected a request so soon 😉 Ok, here is an attempt to explain my analysis: The original GCE Random() function implements a 17-bit linear feedback shift register (LSFR). For storing the "seed", the BIOS uses 3 bytes (24 bits), located at Vec_Random_Seed. The upper 7 bits of Vec_Random_Seed+2 are not actively used and irrelevant for the random number generation. To be a bit more precise, that Random() routine uses those 3 bytes to which Vec_Seed_Ptr points, and the BIOS initializes this pointer to the address of Vec_Random_Seed. By redirecting this pointer, the programmer can, for example, use the Random() routine in combination with several different random number generators in a program (we will get back to that later). I have to admit, that I find the term "seed" a bit misleading, as the seed value is actually the current n-bit value (or the current state) of the n-bit LFSR. From this state, the next following n-bit random number is (deterministically) computed. In our case, the "seed" are bits 0 to 7 of Vec_Random_Seed concatenated with bits 0 to 7 of Vec_Random_Seed+1 concatenated with bit 0 of Vec_Random_Seed+2 (or in simpler terms bits 0 to 16 of Vec_Random_Seed). Some fundamentals: A n-bit Linear Feedback Shift Register operates by shifting all the bits of its current value one position to the right, and by filling up the now "empty" least-significant bit position with some computed entropy value. This operation is defined by a characteristic polynomial which determines the (other) bit positions which are used to compute this next pseudo-random entropy bit (as a big XOR of all the coefficient bits of the polynomial). As there are only 2 n different n-bit values, it is clear the after a certain period the thus produced sequence of n-bit values starts repeating over and over in exactly the same way. If the characteristic polynomial is carefully chosen, then the period is of maximum length (2 n – 1). Note that the n-bit zero as a seed must be avoided and excluded as it leads to a deadlock. A maximum period is desirable in order to get the best (and largest) pseudo random distribution of all n-bit numbers. For each n, there is exactly one polynomial yielding such maximum period. I tried to explain this the best I can. You can also read all this stuff here:
So why did the GCE programmers implement only a 17-bit LFSR when they had 24 bits at hand? Now, my guess is, that in order to make the Random() routine compute as fast as possible, the GCE designers settled for a maximum-period polynomial which has the fewest possible number of coefficients. For a maximum-period 17-bit LFSR, only two bits are used to compute the entropy bit, namely bit 16 and bit 13 of Vec_Random_Seed.
The corresponding polynomial is (x17 + x14 + 1). Note that the coefficients are numbered starting from 1, while we programmers usually number bits starting from 0. There are other polynomials with only two coefficients (such as for bits widths 9,10,11, and 15). The designers chose the 17 bit polynomial, because the highest coefficient (bit 16) corresponds to the least significant bit of one of the three seed bytes (bit 0 of Vec_Random_Seed+2). Why would this be good? Because that allows for computing the new entropy bit with the fewest number of 6809 shift and rotate operations. The "other" coefficient bit (bit 13) just needs to be shifted (or rotated) to bit position zero, and then the XOR can be computed. Only four ROLA instructions are need before computing the XOR. For all values of n other than 17, more shift or rotate instructions (or another register load) are needed to compute the XOR, and the routine would thus be slower. Except for a 20-bit LFSR!!!
If I am not mistaken, that one can be computed with just three ROLA instructions. I checked all polynomials, and I overlooked that possibility at first. So maybe the GCE programmers did not realize that as well? The whole Random() routine can easily be patched to function as a 20-bit LFSR while being one ROLA quicker at the same time. Not that this would change much in terms of quality of the randomness. Ok, so much for how Random() works, and why it effectively uses just 17 seed bits. Now why do we think badly of it? Well, rather than being a pseudo random NUMBER generator, a LFSR is actually a pseudo random BIT generator. It shifts all its internal bits one position to the right, and introduced just one single new entropy bit in each call. As result, Random() returns the lowest 8 bits of its seed (the byte in Vec_Random_Seed).
For each two subsequent calls of Random(), we either get the two values (x and 2*x), or (x+1 and 2*x). To be more precise we get either (x and (2*x mod 256)) or (x+1 and (2*x mod 256)). Not very random.
Large slices of the bit patterns keep repeating, or rather reappearing in higher bit positions. One can immediately see this in Malban 's Shroom example. Using subsequent calls of the same LFSR to generate pairs of data, of which the two values should be independent of each other, will never work in a "randomly" fashion (e.g. two subsequent calls of Random() to get the y and the x coordinate of an object). LFSRs are quite good in a statistical or purely mathematical sense, when it comes to considering large samples of data, but not in the common applications of game programming, like random positions of objects. Unfortunately, this "dependence" of subsequent data is pretty strong: "the subsequent value being the double of the previous value", never mind those tiny +1 entropy injections. What can we do about it? What we have always done. Complain, and use our own pseudo random number generator 😉 Or, to give the original designers credit, one could use several different 3-byte random number seeds, and adjust Vec_Seed_Ptr to switch between them. Use one generator for the y coordinates, and a different one for the x coordinates of random objects. No correlations between y and x anymore. But still within the sequence of y coordinates, and still within the sequence of x-coordinates. Or we keep in mind what I wrote above: a LFSR is a pseudo random BIT generator. A good idea is to just use only any eighth byte value generated by Random(). Then there will be no (direct) correlation anymore between two subsequent random bytes. It is interesting that there is a Random_3() BIOS routine which iterates through Random() three times, before returning a value. If it were a Random_8() routine, iterating eight times, that would be great and would actually make some sense. Of course the big drawback of this method is that is takes eight times as much time as a single call to Random(). But the results, in terms of pseudo randomness, are much better (I tried it with the Shrooms). That's for now. Hope all this makes sense. Many Cheers, Peer
|
|
|
Post by Peer on Dec 6, 2022 5:30:13 GMT -5
I followed the idea to call the LFSR 8 times in a row to improve the quality of the generated random numbers (see end of last post). A careful inspection of the characteristic polynomials yielded, that for the case of the 15-bit LFSR it is possible to implement a pseudo 8-bit random number generator that does the 8-times-successive-call of the 15-bit LFSR in a single all-at-once computation. The code is ultra-fast and small, and it seems to work nicely in terms of quality of the randomness. I will test it over the next days by patching it into the BIOS and then running several existing games with it, and I will then post the results here.
Cheers, Peer
|
|
|
Post by kokovec on Dec 6, 2022 13:24:07 GMT -5
This is all extremely interesting. The SID chip uses a 23 bit Fibonacci LFSR with taps at bits 17 and 22 to produce the noise waveforms. Also, LFSRs are heavily used in signal transmission (CRC, scrambling, etc.). I never stopped to think about 1st Gen gaming systems using LSFRs for randomness.
|
|
|
Post by Peer on Dec 7, 2022 2:24:53 GMT -5
This is all extremely interesting. The SID chip uses a 23 bit Fibonacci LFSR with taps at bits 17 and 22 to produce the noise waveforms. Also, LFSRs are heavily used in signal transmission (CRC, scrambling, etc.). I never stopped to think about 1st Gen gaming systems using LSFRs for randomness. Yes, exactly. LFSRs were introduced in the context of Error Checking Codes and Cyclic Redundancy Checks, but as far as I know, not as general-purpose (pseudo) random number generators. The earliest references I could find related to game programming are the well known examples of Pitfall and River Raid. Would be interesting to know if LFSRs were used to randomize games already before. Btw, and I probably already posted this in some other thread, "Hacker’s Delight" by Henry S. Warren Jr. is a great book about bit-level hacks and has a nice section about CRC.
|
|
|
Post by Peer on Dec 11, 2022 11:11:18 GMT -5
Hehe, originally, I had planned to test the new random generator I wrote about in my previous posts. That would have made sense. But instead I did a counter-experiment, which by itself does not make a lot of sense (or maybe only very little), but which turned out to be much more fun Yesterday evening, out of curiosity, I replaced the BIOS Random() routine by a constant zero, i.e. by a dummy function which always returns zero. I then ran several original GCE games with the customized BIOS in order to see what happens. I should have taken notes or pictures, but unfortunately I did not. For what it's worth, here is what I remember: Mine Storm - All the mines are laid out with equal distance to each other in a straight vertical line, starting at the top of the screen, reaching down about two third of the screen, and horizontally centered. When spawning, all mines move in the same direction. Ok, so position your ship directly beneath that vertical line, point upwards, and start a shooting frenzy… The explosion sound is probably also affected. As far as I know, the explosion routine uses the random generator to induce noise, but from what I heard it was hard to tell if there was any difference to the regular sound. Armor Attack - I could not detect any difference. I did not play much, but either the game does not uses any randomization, or it uses its own generator. Bedlam - Rather boring, all enemies always appear from the right. Berzerk - All rooms of the maze look exactly the same. And … they are crowded to the max with robots! Each room has 11 robots. Cosmic Chasm - The mission layout is always the same. All enemies start from the same starting position, which makes is it pretty easy to shoot them. Heads Up - I played only at level 1, and I did not notice any difference. Pole Position - Starts fine, but after a few seconds of driving the game crashes and the screen goes blank. Interesting… Rip Off - All enemies start from the middle position at the bottom of the screen. Makes the game literally a bottom-of-the-screen-shooter 😉
Solar Quest - Same as Rip Off.
Scramble - I could not detect any difference. I did not play much, but either the game does not uses any randomization, or it uses its own generator. Star Hawk - Crashes right at the beginning of a game. Star Trek - Crashes right at the beginning of a game. Clean Sweep - No difference to regular play.
|
|
|
Post by D-Type on Dec 11, 2022 12:03:44 GMT -5
Maybe if it returned one instead of zero, certain games would not crash? Can the standard RNG return zero?
|
|
|
Post by Peer on Dec 11, 2022 13:11:58 GMT -5
Yes, the standard Random() routine can return zero. It is a 17 bit LFSR, so in a complete cycle is goes through all possible 17-bit numbers, except the 17-bit zero pattern (lock-up state). But only the lowest 8 bits of these numbers are returned as the random byte. So there will be lots of such 8-bit zeros in a complete cycle. The unfortunate thing is just the not-so-random order in which it cycles through all those 17-bit numbers.
So, I am pretty sure that in my experiments the games did not crash because of "a" zero, but because there were "only" zeros.
|
|