aboutsummaryrefslogtreecommitdiff
path: root/rand
diff options
context:
space:
mode:
Diffstat (limited to 'rand')
-rw-r--r--rand/README.md33
-rw-r--r--rand/linear.s61
-rw-r--r--rand/precalc.s55
-rw-r--r--rand/rand.s438
4 files changed, 587 insertions, 0 deletions
diff --git a/rand/README.md b/rand/README.md
new file mode 100644
index 0000000..12f8902
--- /dev/null
+++ b/rand/README.md
@@ -0,0 +1,33 @@
+## Generating pseudo-random numbers
+
+Usually there is a requirement from NES/Famicom games to have access to random
+numbers. This is not entirely possible on the NES/Famicom since there is no
+hardware-specific implementation for any of this (i.e. as it happens on modern
+CPUs). But there's this common saying: if you can't make it, fake it! That's a
+common mentality when programming on the NES/Famicom due to its shortcomings in
+comparison to modern hardware.
+
+In this case, there are quite clever algorithms for generating **pseudo** random
+numbers. That is, numbers which are not absolutely random, but they are quite
+close to it.
+
+First of all, you need to generate a **seed**: from which number you start
+generating new random numbers. The approach taken here is the same as in many
+other games: the player is presented with a `Start` screen. On `nmi` code we
+count the frames until the player actually presses the `Start` button.
+Obviously, this is not really random, but unless you are on a TAS or you are an
+amazing player with frame-perfect input skills, it's good enough.
+
+All of this is implemented on the [rand.s](./rand.s) file. After the "Start"
+screen the player is presented with the algorithm being used and the random
+value that we got. The player can then press `Select` to change the algorithm
+being used, or press `A` to select a new number. There are a total of two PRNG
+algorithms being tested here:
+
+- [linear.s](./linear.s): A Galois linear feedback shift register (16-bit).
+- [precalc.s](./precalc.s): Indexing a pre-computed set of random numbers.
+
+These algorithms are better explained at the top comment from their respective
+files. All in all, we get the following result:
+
+![rand.gif](../docs/rand.gif)
diff --git a/rand/linear.s b/rand/linear.s
new file mode 100644
index 0000000..9ab7aa1
--- /dev/null
+++ b/rand/linear.s
@@ -0,0 +1,61 @@
+;;;
+;; Pseudo-random number implementation by a linear feedback shift register.
+;;
+;; This is one of the most common techniques developed on NES/Famicom games, and
+;; it's based on the algorithm from french mathematician Évariste Galois:
+;; https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Galois_LFSRs.
+;; That is, we have a wider-than-8-bit register which keeps on shifting and
+;; "taps" on some bits whenever the carry flag is set. This sounds complicated
+;; but it really is not, and it can be further optimized as Brad Smith proved:
+;; https://github.com/bbbradsmith/prng_6502.
+;;
+;; All in all, the implementation here is based on the "basic" implementation
+;; from NesHacker: https://github.com/NesHacker/NES-RNG/blob/main/nes-rng.s; as
+;; it's easier to reason about. Other than that, refer to the NESDev wiki for
+;; more information: https://www.nesdev.org/wiki/Random_number_generator.
+
+;; Producing random numbers with a linear feedback shift register require at
+;; least 16-bit. In this case, we have the low byte which will be the end result
+;; upon each call to `linear_feedback_shift_register`; and the high byte which
+;; will be messed up to feed the low byte on each iteration. If we wanted more
+;; random numbers (i.e. how many random numbers can be generated before they
+;; start repeating all over again), we would need to add more bytes. For a
+;; simple 8-bit computer like the NES/Famicom, a 16-bit register for this is
+;; more than enough.
+.scope Linear
+ zp_register_lo = $40
+ zp_register_hi = $41
+.endscope
+
+;; Updates the 'a' register with a new random number as extracted from the
+;; linear feedback shift register referenced in the `Linear` scope.
+;;
+;; See: https://github.com/NesHacker/NES-RNG/blob/main/nes-rng.s
+.proc linear_feedback_shift_register
+ lda Linear::zp_register_hi
+ ldy #8
+
+@loop:
+ ;; Shift the least significant bit from the high byte to the low byte of the
+ ;; 16-bit register.
+ lsr
+ ror Linear::zp_register_lo
+
+ ;; Following the Galois algorithm, if the carry flag was set, then we need
+ ;; to tap on some specific bits of the low byte with an xor. Hence, if the
+ ;; carry flag is clear, skip the `eor` instruction.
+ bcc @skip_eor
+ eor #$B4
+
+@skip_eor:
+ ;; Save the current state of the high register and decrement the loop index.
+ sta Linear::zp_register_hi
+ dey
+ bne @loop
+
+ ;; The low byte now contains the shifted values from the loop. That's our
+ ;; final "random" number!
+ lda Linear::zp_register_lo
+
+ rts
+.endproc
diff --git a/rand/precalc.s b/rand/precalc.s
new file mode 100644
index 0000000..0b6da86
--- /dev/null
+++ b/rand/precalc.s
@@ -0,0 +1,55 @@
+;;;
+;; Pseudo-random number implementation by using a pre-calculated table.
+;;
+;; The implementation for this is extremely simple, as the given input parameter
+;; is used to index the random table below. Note that the table is 256 bytes
+;; long. This has the benefit that you never need to worry about bad indexing,
+;; and that the implementation is kept simple and fast. The inconvenience is
+;; that, obviously, you lose 256 bytes of data.
+;;
+;; From a programmer's happiness perspective, this solution also feels quite
+;; uninspired, but it gets the job done and there will be no surprises.
+;;
+;; From the player's perspective, of course, if they are messing with the code
+;; itself, it's pretty easy to manipulate the randomness of it all. As in, if
+;; they are using a TAS or they have mad frame-perfect input skills, they can
+;; predict the seed and get the value they want.
+;;
+;; All of the above being said, Final Fantasy is famous for using this technique
+;; for their random number generation, so it's not as unhinged as you would
+;; think.
+;;
+;; NOTE: to avoid the cost of having to have a 256 byte table, one idea I've had
+;; is that instead of using the `rand_table` we could use simply `main` (or
+;; better yet, `$8000`), as that spans more than 256 bytes. Moreover, the linker
+;; can have a configuration for random fill values, so any gaps could also have
+;; random bytes in it.
+
+;; Given a number passed via the 'a' register, it updates this same 'a' register
+;; with the next random number.
+;;
+;; NOTE: implemented by indexing a pre-calculated random table.
+.proc precalc
+ tax
+ lda rand_table, x
+ rts
+.endproc
+
+;; Pre-computed table, hopefully it feels random enough :)
+rand_table:
+ .byte $D7, $3A, $1C, $8F, $09, $B2, $E6, $54, $A3, $91, $2B, $F5, $78, $0D, $4C, $6E
+ .byte $FF, $C0, $52, $33, $6A, $E9, $9B, $1A, $47, $88, $7D, $21, $0E, $F4, $B3, $9C
+ .byte $15, $67, $A8, $41, $D2, $39, $80, $76, $C9, $E5, $0A, $1B, $5F, $22, $73, $DA
+ .byte $B4, $96, $3C, $E0, $8D, $F7, $2A, $05, $9E, $43, $11, $6D, $A7, $58, $C1, $32
+ .byte $28, $0F, $79, $BE, $51, $64, $9D, $A9, $3B, $71, $8E, $C6, $4A, $13, $F0, $27
+ .byte $E2, $5C, $06, $D3, $95, $B8, $4F, $70, $19, $A4, $6B, $38, $82, $C7, $5E, $01
+ .byte $F3, $2D, $9A, $65, $7C, $D1, $0B, $E8, $57, $36, $84, $1F, $B0, $92, $45, $AC
+ .byte $60, $7E, $A1, $53, $C8, $29, $D4, $FB, $07, $42, $E3, $99, $16, $8A, $3D, $C5
+ .byte $24, $B1, $6F, $03, $7A, $E7, $8C, $59, $D0, $46, $93, $1E, $A5, $2C, $B7, $F1
+ .byte $89, $55, $C3, $30, $62, $98, $04, $D6, $7F, $A0, $E4, $12, $3B, $81, $F9, $23
+ .byte $C4, $0D, $5A, $71, $9F, $B6, $2E, $85, $37, $A9, $18, $6C, $E1, $4B, $D9, $02
+ .byte $F8, $63, $B5, $40, $97, $0C, $7A, $51, $A2, $3E, $8F, $D5, $14, $69, $E0, $B8
+ .byte $4D, $77, $25, $9B, $0A, $F2, $3C, $86, $E9, $1F, $68, $A3, $50, $C1, $7D, $04
+ .byte $B2, $8E, $56, $1D, $73, $9C, $F5, $2A, $61, $D7, $09, $3E, $84, $A0, $E6, $1B
+ .byte $3F, $C8, $94, $05, $72, $D6, $A7, $4C, $1A, $5F, $B3, $29, $80, $E1, $6D, $9E
+ .byte $0C, $43, $F7, $8B, $52, $16, $A8, $3D, $91, $2B, $E5, $70, $C6, $4A, $D9, $F8
diff --git a/rand/rand.s b/rand/rand.s
new file mode 100644
index 0000000..abf944f
--- /dev/null
+++ b/rand/rand.s
@@ -0,0 +1,438 @@
+;;;
+;; Showcase different strategies for Random Number Generation (RNG).
+;;
+;; Refer to the README.md file for documentation. Here I have left comments
+;; whenever there's something "new" if you are coming from the `basics/`
+;; directory.
+
+.segment "HEADER"
+ .byte 'N', 'E', 'S', $1A
+ .byte $02, $01
+ .byte $00, $00
+
+.segment "VECTORS"
+ .addr nmi, reset, irq
+
+.segment "CHARS"
+.incbin "../assets/alphanum.chr"
+
+.segment "CODE"
+
+.include "../shared/ppu.s"
+.include "../shared/clear.s"
+.include "../shared/joypad.s"
+
+;; Different algorithms.
+.include "linear.s"
+.include "precalc.s"
+
+;; Number of algorithms for this game.
+ALGORITHM_SIZE = $02
+
+;; See Vars::zp_button_timer.
+KEY_TIMER = 15
+
+;; Variables used by this game.
+.scope Vars
+ ;; 0: "Press start" state; 1: "number generation" state.
+ zp_state = $30
+
+ ;; Timer for key presses. A button press will only be considered if the
+ ;; button timer is zero. Whenever that's the case, the code will reset the
+ ;; timer to this new value, and decrement it whenever a new press is found.
+ ;; Whenever we reach back to zero, then the button press will be considered
+ ;; again. All of this is because whenever the player presses a button, it
+ ;; actually presses it for more than one frame, and things can go crazy from
+ ;; this fact.
+ zp_button_timer = $31
+
+ ;; Algorithm that has been selected.
+ zp_algorithm = $32
+
+ ;; The random seed for this game. As described in the README.md file, this
+ ;; is actually a frame counter for the "Press start" state, and whenever the
+ ;; player hits "Start", it will be paused. That is, our random seed is
+ ;; simply the number of frames that the player took to press "Start" at the
+ ;; beginning.
+ ;;
+ ;; NOTE: it's not going to be initialized to get a more random feeling on
+ ;; real hardware from unknown RAM state.
+ zp_seed = $33
+
+ ;; The number to be displayed.
+ zp_number = $34
+.endscope
+
+;; Main function, this takes care of reading input, changing the state, and
+;; calling the relevant algorithm to get new numbers.
+.proc main
+ ;; Initialize all variables (except Vars::zp_seed as explained above).
+ lda #0
+ sta Vars::zp_state
+ sta Vars::zp_button_timer
+ sta Vars::zp_algorithm
+ sta Vars::zp_number
+
+ ;; Clear both screens. Yes, over the top, but it gets the job done.
+ CLEAR_SCREENS $20, $28
+
+ ;; Initialize palettes and show the "Press start" message.
+ jsr init_palettes
+ jsr show_init_screen
+
+ cli
+ lda #%10001000
+ sta $2000 ; PPUCTRL
+ lda #%00011110
+ sta $2001 ; PPUMASK
+
+@main_game_loop:
+ ;; Should we actually read the joypad? This is handled via the button timer
+ ;; as explained above.
+ lda Vars::zp_button_timer
+ beq @check_joypad
+ dec Vars::zp_button_timer
+ jmp @end
+
+@check_joypad:
+ ;; Yes! Then read the joypad.
+ READ_JOYPAD1
+
+ ;; What's the current game state?
+ lda Vars::zp_state
+ bne @check_change_algorithm
+
+ ;; "Press start" state. If the player is not pressing "Start", ignore
+ ;; everything and go to the end.
+ lda Joypad::zp_buttons1
+ and #Joypad::BUTTON_START
+ beq @end
+
+ ;; Reset the button timer.
+ lda #KEY_TIMER
+ sta Vars::zp_button_timer
+
+ ;; The random seed has a proper value and we can use that as a first random
+ ;; number.
+ lda Vars::zp_seed
+ sta Vars::zp_number
+
+ ;; The 'linear' algorithm actually disregards any parameters and needs a
+ ;; 16-bit register. Let's initialize this register with the current seed.
+ sta Linear::zp_register_lo
+ sta Linear::zp_register_hi
+
+ ;; Move into the next state.
+ inc Vars::zp_state
+
+ jmp @end
+
+@check_change_algorithm:
+ ;; We are in a running state. Check if the player is asking to change the
+ ;; algorithm.
+ lda Joypad::zp_buttons1
+ and #Joypad::BUTTON_SELECT
+ beq @check_a_button
+
+ ;; Reset the button timer.
+ lda #KEY_TIMER
+ sta Vars::zp_button_timer
+
+ ;; The player asked to change the algorithm. Do it now and go generate a new
+ ;; number with that.
+ ldx Vars::zp_algorithm
+ inx
+ cpx #ALGORITHM_SIZE
+ bne @store_algorithm
+ ldx #0
+@store_algorithm:
+ stx Vars::zp_algorithm
+ jmp @next_number
+
+@check_a_button:
+ ;; Is the player asking for a new number? If not go to the end.
+ lda Joypad::zp_buttons1
+ and #Joypad::BUTTON_A
+ beq @end
+
+ ;; Reset the button timer.
+ lda #KEY_TIMER
+ sta Vars::zp_button_timer
+
+@next_number:
+ ;; Setup parameters depending on the algorithm and actually call it.
+ ldx Vars::zp_algorithm
+ bne @precalc
+ jsr linear_feedback_shift_register
+ jmp @store_number
+@precalc:
+ lda Vars::zp_number
+ jsr precalc
+@store_number:
+ sta Vars::zp_number
+
+@end:
+ ;; And wait for the render to happen as it's done in any other example.
+ lda #%10000000
+ ora $20
+ sta $20
+@wait_for_render:
+ bit $20
+ bmi @wait_for_render
+
+ jmp @main_game_loop
+.endproc
+
+;; NMI code is pretty standard. I have added comments for the code which is
+;; specific to this game.
+.proc nmi
+ bit $20
+ bpl @next
+
+ pha
+ txa
+ pha
+ tya
+ pha
+
+ lda #$00
+ sta $2003 ; OAMADDR
+ lda #$02
+ sta $4014 ; OAMDMA
+
+ ;; What's the current game state?
+ lda Vars::zp_state
+ beq @seed_inc
+
+ ;; Running state. Print the current algorithm and number.
+ jsr print_algorithm
+ jsr print_value
+
+ ;; The running state is displayed on the other nametable. Update the PPU
+ ;; control register for this (it's of course stupid to update it every time,
+ ;; but I didn't feel like doing the proper thing of shadowing the PPU
+ ;; control register and update only on changes, etc.).
+ lda #%10001010
+ sta $2000 ; PPUCTRL
+ bne @after_seed
+
+@seed_inc:
+ ;; "Press start" state: just increase the frame counter which is used as a
+ ;; seed.
+ inc Vars::zp_seed
+
+@after_seed:
+ bit $2002 ; PPUSTATUS
+ lda #$00
+ sta $2005 ; PPUSCROLL
+ sta $2005 ; PPUSCROLL
+
+ lda #%01111111
+ and $20
+ sta $20
+
+ pla
+ tay
+ pla
+ tax
+ pla
+@next:
+ rti
+.endproc
+
+;; Show the "Alg: <algorithm>" message on screen.
+.proc print_algorithm
+ ;; "ALG: "
+ WRITE_PPU_DATA $298B, $1A
+ WRITE_PPU_DATA $298C, $25
+ WRITE_PPU_DATA $298D, $20
+ WRITE_PPU_DATA $298E, $34
+ WRITE_PPU_DATA $298F, $00
+
+ lda Vars::zp_algorithm
+ beq @linear
+
+ ;; "PRECALC"
+ WRITE_PPU_DATA $2990, $29
+ WRITE_PPU_DATA $2991, $2B
+ WRITE_PPU_DATA $2992, $1E
+ WRITE_PPU_DATA $2993, $1C
+ WRITE_PPU_DATA $2994, $1A
+ WRITE_PPU_DATA $2995, $25
+ WRITE_PPU_DATA $2996, $1C
+ rts
+
+ ;; "LINEAR "
+@linear:
+ WRITE_PPU_DATA $2990, $25
+ WRITE_PPU_DATA $2991, $22
+ WRITE_PPU_DATA $2992, $27
+ WRITE_PPU_DATA $2993, $1E
+ WRITE_PPU_DATA $2994, $1A
+ WRITE_PPU_DATA $2995, $2B
+ WRITE_PPU_DATA $2996, $00
+ rts
+.endproc
+
+;; Show the "Val: $<number>" message on screen.
+.proc print_value
+ ;; "VAL: $"
+ WRITE_PPU_DATA $29AB, $2F
+ WRITE_PPU_DATA $29AC, $1A
+ WRITE_PPU_DATA $29AD, $25
+ WRITE_PPU_DATA $29AE, $34
+ WRITE_PPU_DATA $29AF, $00
+ WRITE_PPU_DATA $29B0, $35
+
+ ;; Set the high byte on the 'y' register, and the low byte on the 'x'
+ ;; register.
+ lda #$F0
+ and Vars::zp_number
+ lsr
+ lsr
+ lsr
+ lsr
+ clc
+ adc #$10
+ tay
+ lda #$0F
+ and Vars::zp_number
+ clc
+ adc #$10
+ tax
+
+ ;; Display the actual number.
+ bit $2002
+ lda #$29
+ sta $2006
+ lda #$B1
+ sta $2006
+ sty $2007
+ stx $2007
+
+ rts
+.endproc
+
+;; Show the "Press start" message.
+.proc show_init_screen
+ ;; "PRESS"
+ WRITE_PPU_DATA $21AB, $29
+ WRITE_PPU_DATA $21AC, $2B
+ WRITE_PPU_DATA $21AD, $1E
+ WRITE_PPU_DATA $21AE, $2C
+ WRITE_PPU_DATA $21AF, $2C
+
+ ;; "START"
+ WRITE_PPU_DATA $21B1, $2C
+ WRITE_PPU_DATA $21B2, $2D
+ WRITE_PPU_DATA $21B3, $1A
+ WRITE_PPU_DATA $21B4, $2B
+ WRITE_PPU_DATA $21B5, $2D
+
+ rts
+.endproc
+
+;; Initialize palettes. A bit over the top since only two colors are used.
+.proc init_palettes
+ lda #$3F
+ sta $2006 ; PPUADDR
+ lda #$00
+ sta $2006 ; PPUADDR
+
+ ldx #0
+@load_palettes_loop:
+ lda palettes, x
+ sta $2007 ; PPUDATA
+ inx
+ cpx #$20
+ bne @load_palettes_loop
+ rts
+palettes:
+ DEFAULT_COLOR = $0F
+
+ ;; Background
+ .byte DEFAULT_COLOR, $20, $FF, $FF
+ .byte DEFAULT_COLOR, $20, $FF, $FF
+ .byte DEFAULT_COLOR, $20, $FF, $FF
+ .byte DEFAULT_COLOR, $20, $FF, $FF
+
+ ;; Foreground
+ .byte DEFAULT_COLOR, $20, $FF, $FF
+ .byte DEFAULT_COLOR, $20, $FF, $FF
+ .byte DEFAULT_COLOR, $20, $FF, $FF
+ .byte DEFAULT_COLOR, $20, $FF, $FF
+
+ rts
+.endproc
+
+;;;
+;; NOTE: down below just boilerplate. Nothing special from the `basics/`
+;; examples.
+
+.proc reset
+ sei
+ cld
+
+ ldx #$40
+ stx $4017 ; APU Frame Counter
+
+ ldx #$FF
+ txs
+
+ inx
+ stx $2000 ; PPUCTRL
+ stx $2001 ; PPUMASK
+ stx $4010 ; APU DMC
+
+ bit $2002 ; PPUSTATUS
+@vblankwait1:
+ bit $2002 ; PPUSTATUS
+ bpl @vblankwait1
+
+ ldx #0
+ lda #0
+@ram_reset_loop:
+ sta $000, x
+ sta $100, x
+ sta $300, x
+ sta $400, x
+ sta $500, x
+ sta $600, x
+ sta $700, x
+ inx
+ bne @ram_reset_loop ; if x overflows back to #00, then we are done.
+
+ lda #$EF
+@sprite_reset_loop:
+ sta $200, x
+ inx
+ bne @sprite_reset_loop
+
+ lda #$00
+ sta $2003 ; OAMADDR
+ lda #$02
+ sta $4014 ; OAMDMA
+
+@vblankwait2:
+ bit $2002 ; PPUSTATUS
+ bpl @vblankwait2
+
+ lda #$3F
+ sta $2006 ; PPUADDR
+ lda #$00
+ sta $2006 ; PPUADDR
+
+ lda #$0F
+ ldx #$20
+@palettes_reset_loop:
+ sta $2007 ; PPUDATA
+ dex
+ bne @palettes_reset_loop
+
+ jmp main
+.endproc
+
+.proc irq
+ rti
+.endproc
+