Basic Questions and Answers Thread

Discussion in 'Discussion & Q&A' started by Malevolence, Jul 7, 2009.

  1. MarkeyJester

    MarkeyJester ♡ ! Member

    Joined:
    Jun 27, 2009
    Messages:
    2,867
    The pseudo random number generator routine known as "RandomNumber" can help, to use simply:

    Code:
    		bsr.w	RandomNumber
    A pseudo random number will now exist in d0 as a long-word, you may manipulate that to your needs.
     
  2. Sonic master

    Sonic master Well-Known Member Member

    Joined:
    Mar 27, 2010
    Messages:
    303
    Here is a good article on the topic: http://www.maximintegrated.com/en/app-notes/index.mvp/id/4400 I quickly ported the code to the m68k. This is untested but should work. Note that you need a seed. To generate a seed you need a source of entropy. A good source of entropy is measuring how long the user took to press a button. In this example I just use a fixed value. I will leave it as an exercise to the reader to implement that yourself. The advantage of this code is that it avoids the mul instruction but I do not see it as optimal. I do not want to do all the work for you and it has been a very long time since I programmed for the m68k

    Code:
    ;Start by initializing registers please replace this to fit your needs but don't use a value of zero
    init:
    	move.l #$ABCDE,d2
    	move.l #$23456789,d3
    	bsr get_rand ;not necessary in this example but will be used in practical example
    	
    	;Do something 
    
    get_rand:
    	;Input:
    	;d2 lfsr32 please keep track of these two (see output)
    	;d3 lfsr31
    	;returns random number in d0
    	;d4 lfsr32 output
    	;d5 lfsr31 output
    	;clobers registers d1
    	move.l d2,d0
    	move.l #$B4BCD35C,d1
    	bsr shift_lfsr
    	bsr shift_lfsr ;Yes this is supposed to be duplicated
    	move.l d0,d4
    	move.l d3,d0
    	move.l #$7A5BC2E3,d1
    	bsr shift_lfsr
    	move.l d0,d5
    	eor.l d4,d0
    	andi #$FFFF,d0
    	rts
    shift_lfsr:
    	;Inputs:
    	;d0 lfsr
    	;d1 polynomial mask this register remains unchanged
    	;Output:
    	;d0 lfsr
    	btst #1,d0
    	bnz feedback
    	lsr.l #1,d0
    	rts
    feedback:
    	lsr.l #1,d0
    	or.l d2,d0
    	rts
    
    Edit I missed MarkeyJester's post by being distracted for a bit then coming back here to write a post. The functiion provided by sonic team looks faster by quickly scanning it. I wonder is the quality of the generated numbers as good. I have not done any testing on this and cannot say. Also I would like to point out the fact that these are psuedorandom numbers. A computer cannot generate a random number without special hardware and even then is it really random? To make the number more random do like I said above and do it regularlly to improve quality of your sequence. Also you could maybe utilize the HV counter (on the vdp).
     
    Last edited by a moderator: Aug 12, 2014
  3. MainMemory

    MainMemory Well-Known Member Member

    Joined:
    Mar 29, 2011
    Messages:
    922
    I added warnings to the Sonic Retro wiki pages for all the outdated utilities some time ago, unfortunately nobody downloads them from those pages.

    To increase the randomness for Sonic 2 Adventure Edition's Emerald placement, when the seed is reset at the start of each level I XOR (eor.l) the default seed value with the value of the Vint_runcount variable (essentially a frame counter), which is also saved to SRAM when a level is completed and loaded when the game boots up, so every playthrough yields different placements.
     
    Pacca likes this.
  4. Pacca

    Pacca Having an online identity crisis since 2019 Member

    Joined:
    Jul 5, 2014
    Messages:
    1,175
    Location:
    Limbo
    I don't really need anything too fancy; I'm just trying to implement a monitor with "interesting" results. It shouldn't need an extremely random value (like what would be required for a truly unpredictable series of XY coordinates). I think S1's default generator will do. I'll keep your tip in mind, though :3
     
  5. redhotsonic

    redhotsonic Also known as RHS Member

    Joined:
    Aug 10, 2007
    Messages:
    2,969
    Location:
    England
    I've done an extremely similar thing to you in both my S2R and S2TA, so that it does appear to be more "random".  But a question, is there a logical reason for why the seed is resetted at the start of each level (as well as resetted in other areas)?
     
    Last edited by a moderator: Aug 12, 2014
  6. MainMemory

    MainMemory Well-Known Member Member

    Joined:
    Mar 29, 2011
    Messages:
    922
    It could be merely a side effect of where the seed value is stored in RAM, it clears a block of data and that just happens to be there; it could be an attempt to make random elements more predictable, so that playing levels in the same way gives the same results every time.
     
  7. Sonic master

    Sonic master Well-Known Member Member

    Joined:
    Mar 27, 2010
    Messages:
    303
    The code I posted is by no means fancy. LFSR is anything but fancy. LFSR is not good alone. The article solves this by chaining multiple LFSR. Here is what is fancy https://en.wikipedia.org/wiki/Mersenne_twister
     
  8. Pacca

    Pacca Having an online identity crisis since 2019 Member

    Joined:
    Jul 5, 2014
    Messages:
    1,175
    Location:
    Limbo
    How would I make a greater than or less than comparison? I'm making a looping branch system that will subtract 10 (or "A") from the random number I get until it's equal to ten or lower, so I can make it more manageable.
     
  9. TheInvisibleSun

    TheInvisibleSun Visible Member

    Joined:
    Jul 2, 2013
    Messages:
    424
    Location:
    Western New York, USA
    BGT for greater than, and BLT for less than. However, you should be able to use AND to limit the max for the random number, without resorting to the subtraction. If you search here, an explanation for this trick was posted a couple of times (I'm on mobile, so I can't get the link, sorry).
     
    Last edited by a moderator: Aug 12, 2014
  10. nineko

    nineko I am the Holy Cat Member

    Joined:
    Mar 24, 2008
    Messages:
    1,902
    Location:
    italy
    If you're ok with a 0-15 range you can simply ANDI.b d0 with 15.
     
  11. Sonic master

    Sonic master Well-Known Member Member

    Joined:
    Mar 27, 2010
    Messages:
    303
    Well if you want a range from 0-15 you could just use a bitshift or use the and instruction (note these are not equivlant). However a range from 0-10 will create the need for more instructions. I will assume that you went with sonic's random number generator, in that case you end up with a 32bit number. You need a ratio you see. First shift to the right by 16. The multiply by 10 (shift to the left by three then add the same number shifted to the left by one) Now shift to the right by 16 again. Another alternative is to shift the the right by 13 then with that result add the same number shifted again to the right by 2 then shift the the right by 16. Also I changed an instruction in my random number generator code. bra should have been bnz.
     
    Last edited by a moderator: Aug 12, 2014
  12. Pacca

    Pacca Having an online identity crisis since 2019 Member

    Joined:
    Jul 5, 2014
    Messages:
    1,175
    Location:
    Limbo
    Two things; first simply dumping the command right after the jmp to randomnumber gives an "illegal addressing mode" error. Also, I can't figure out what the command actually does, despite my research, and I'm intensely curious!

    edit: ninja'd
     
    Last edited by a moderator: Aug 12, 2014
  13. Sonic master

    Sonic master Well-Known Member Member

    Joined:
    Mar 27, 2010
    Messages:
    303
    Why are you using jmp to call the randomnumber function? You should try using bsr and if the branch is too far try jsr. I am wondering is there a way to let the assembler choice the best instruction? That way if you move around data a lot your code will remain optimal.
     
  14. MainMemory

    MainMemory Well-Known Member Member

    Joined:
    Mar 29, 2011
    Messages:
    922
    Some assemblers (maybe all of them, idk) allow you to leave off the size for branch instructions, leaving the assembler to figure out whether a short or word branch is best. The assembler does the first pass with all branches set to short, and it's likely that several will be out of range, so the assembler will change them to word sized, and initiate another pass. The problem is that on the second pass, the increased size of those branch instructions may shift code enough that some other branches are now out of range, requiring another pass, where the same thing may happen again and again. If you add the ability for the assembler to automatically turn branches into jumps, then the problem gets even worse. And if you put in a workaround for out of range conditional branches...
     
  15. Sonic master

    Sonic master Well-Known Member Member

    Joined:
    Mar 27, 2010
    Messages:
    303
    Yes I am familar with leaving the size off. I was wondering about the possiblity of replacing a bsr with a jsr if needed. And I know there is no conditional jsr. It could insert needed code although imagine if you are doing something that needed cycle accurate timing and spend lots of time debugging only to find out that the assembler was being "clever". Well that is what listings are for I guesss but it could still cause someone to shoot themselves in the foot so to say.
     
  16. Painto

    Painto Arthurus Paintus Erinaceus Member

    Joined:
    Mar 24, 2014
    Messages:
    321
    Location:
    Lublin, Poland
    From what I know the random number is moved to d0, so all you need is

    Code:
    	; rest of code
    	[...]
    	bsr.w RandomNumber
    	[...]
    YourRoutine:
    	cmpi.w #$10,d0	; is d0 under 16?
    	ble.s YourRoutine2	; if yes, don't substract
    	sub.w #$A,d0	; substract 10
    	bra.s YourRoutine	; substract again
    YourRoutine2:
    	[...]
    	; rest of code
    
     
    Last edited by a moderator: Aug 12, 2014
  17. Sonic master

    Sonic master Well-Known Member Member

    Joined:
    Mar 27, 2010
    Messages:
    303
    Well considering that d0 will contain a long word that code may take awhile. Also you will want to do cmpi.l instead of cmpi.w
     
  18. Pacca

    Pacca Having an online identity crisis since 2019 Member

    Joined:
    Jul 5, 2014
    Messages:
    1,175
    Location:
    Limbo
    I made my code read it as a byte, so that shouldn't be an issue.
     
  19. Sonic master

    Sonic master Well-Known Member Member

    Joined:
    Mar 27, 2010
    Messages:
    303
    So in effect you are just doing and #255,d0 As a worst case senario you will do 26 subtractions plus loop overhead. That is slower than bitshifting. Did you notice my above post suggestion bitshift techinques to get the number in the range of 0-10?
     
  20. brickrick

    brickrick Active Member Member

    Joined:
    Apr 30, 2012
    Messages:
    33
    Just posting to report this worked! (I actually tried it the night after this post, but I procrastinated the reply... err...)

    It is actually one step easier than what you told me to, but you sure guided me into the right path. I only had to copy the "SK Set 1.bin", make the Sega Data Compressor extract/decompress the Special Stages from a clean SK rom (the program even has a "link" on its known adresses list, I just had to click the address) and make it output onto the "SK Set 1.bin". It turns into a 9 KB, decompressed .bin file. Now, the interesting part was, you don't have to actually insert it into the rom again. I just edited a stage, used the Sega Data Compressor to compress Kosinski onto itself, copy/pasted/replaced the 2 KB compressed "SK Set 1.bin" into the skdisasm-master folder (the "Special Stages/Layout" one) and there! So now I just have a bunch of uncompressed/raw "SK Set 1" bins, ready for edit. Thanks for your helpful advice, nineko!