Randomly placing name table tiles

[noattack]

I'm fooling around with a random-number generator (used to randomly fill the background) and I'm running into a frustrating problem. Here's the RNG subroutine, adopted from here:

Code: Select all

Rand:
  LDA seed		; get seed
  ASL A
  BCC NoEOR		; branch if no carry
  EOR #$CF		; else EOR with #$value
NoEOR:
  STA seed		; save number as next seed
  RTS

And then I'm doing a basic nested loop to fill the background (using count1 and count2 in RAM instead of X or Y - for testing purposes, not for code elegance):

Code: Select all

LoadBackground:
  LDA $2002 ; read PPU status to reset the high/low latch
  LDA #$20
  STA $2006 ; write the high byte of $2000 address
  LDA #$00
  STA $2006 ; write the low byte of $2000 address
  STA count1 ; reset count indices
  STA count2
LoadBackgroundLoop:
  JSR Rand             ; run RNG
  STA $2007            ; write tile to PPU
  INC count1           ;Background is 32x30 ($20 x $1E) sprites, so use nested loops to fill 960 bytes
  LDA count1
  CMP #$E0
  BNE LoadBackgroundLoop
  INC count2
  LDA #$00
  STA count1
  LDA count2
  CMP #$01
  BNE LoadBackgroundLoop
  RTS

As you might note from the comment, I was originally doing a count compare for $20 and $1E, but I was getting a noticeable pattern repeat from the RNG. When I eliminate the nested loop, all of the tiles are random. I can't figure out what's resetting the RNG when I branch back to LoadBackgroundLoop after resetting count1. It's likely I'm not understanding what's going on in the RNG code. Any suggestions?

FYI, the seed var is set to #$01 prior to LoadBackground, which is only called once. And I'm using NESASMv3.1

[rainwarrior]

count2 is initialized to 0, then it is incremented before it is tested the first time against 1, so as far as I can tell from reading the code it isn't doing anything. You will get through the loop once with count1 and then it'll end.

The PRNG you're using has a repeating cycle of 255 possible values. This is obviously going to have to repeat across the screen, since there are a lot more than 255 tiles. (You might consider a 16 bit version of the PRNG.)

Also, consider doing your counting with X and Y, load the number of iterations into X then you can DEX, BNE and you won't have to access RAM to increment or load or perform a separate compare (since DEX will update the zero flag). Edit: oh, I see you mentioned it, but I would suggest you make it a habit-- efficiency aside, it will make less code to read, and is the common way to do loops when writing 6502 assembly. Just to show what I mean:

Code: Select all

LoadBackground:
  LDA $2002 ; read PPU status to reset the high/low latch
  LDA #$20
  STA $2006 ; write the high byte of $2000 address
  LDA #$00
  STA $2006 ; write the low byte of $2000 address
  LDX #(960/4) ; break 960 byte update into 4 pieces
  LDY #4
LoadBackgroundLoop:
  JSR Rand             ; run RNG
  STA $2007            ; write tile to PPU
  DEX
  BNE LoadBackgroundLoop
  LDX #(960/4)
  DEY
  BNE LoadBackgroundLoop
  RTS

[Bregalad]

If you want a 8-bit PRNG, you should use more bits for the sequence (I'd say at least 16) and only use the lower 8.

[noattack]

@rainwarrior - Thanks! I should have been clearer that I knew that nested loop was doing nothing. I was only running the first count so I could see how many values the RNG was outputting. But once you mentioned that it was producing the same 255-byte series, I realized I needed to adjust the EOR value each time through the (second) loop. I had misread the RNG documentation.

And yeah, I was previously using X and Y for the loop indices, but I took them out of the equation for debugging purposes. Silly in retrospect, but I was willing to try anything at that point.

[tepples]

Greg Cook's implementation of CRC16 is a pretty fast RNG with a period of 65535 bytes. The alternate version shown there, which is a couple cycles slower, preserves Y so that you can use it as a loop counter.

[rainwarrior]

I would recommend using 8 bits of a 16 or 24 bit PRNG instead of trying to change an EOR mask every 255 samples or something like that. The repeating 255-step pattern will usually show through an EOR. It's actually pretty easy to modify the PRNG you started with to do 16 bits instead of just 8.

[lidnariq]

The PIClist has a 32-bit LFSR-based RNG that uses the same taps in each octet of the full word. (Also a 16-bit and 24-bit one that shares the same property). http://www.piclist.com/techref/microchip/rand8bit.htm

Converting from PIC asm to 6502 asm should be easy, although PIC's RMW XOR while the 6502's is not means there's no advantage to using the same taps in each octet.

[rainwarrior]

Also, the Galois PRNG is one of the worst random number generators in terms of predictability. It is a very good random generator for single bits, but when you're taking a byte from it, you know a lot about what the next nuber is going to be even if you are just looking at 8 bits out of 16 or more. (Imagine playing a strategy game where you know the next result has a 50% chance of being double the previous one.) If you actually want a "good" random 8 bits from a Galois PRNG, you should tick it 8 times before using the result. This kinda defeats the efficiency that probably led you to select this over a LCG or something like that. Of course, each tick doubles the entropy of your result, so 1-8 ticks will give you a sliding scale of predictability/speed to trade off; for some purposes 1 tick might be a "good enough" random number. It really depends on what you're doing with it.

[tepples]

If you actually want a "good" random 8 bits from a Galois PRNG, you should tick it 8 times before using the result.

I was using a 32 bit LFSR and passing in a number of ticks in Y in Concentration Room and Thwaite. But Greg Cook's CRC-16 is equivalent to 8 ticks per iteration, which is why I've used it in everything since Zap Ruder.

[noattack]

I would recommend using 8 bits of a 16 or 24 bit PRNG instead of trying to change an EOR mask every 255 samples or something like that. The repeating 255-step pattern will usually show through an EOR. It's actually pretty easy to modify the PRNG you started with to do 16 bits instead of just 8.

Yeah, it's not perfect, but for the purposes of what I was doing - drawing a single static image - it worked fine. I only had to update the EOR four times. But you're right - patterns still showed through.