Author Topic: Chaos Game  (Read 3351 times)

0 Members and 1 Guest are viewing this topic.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Chaos Game
« on: December 18, 2013, 02:37:11 pm »
The Chaos Game is not a 'game' in the standard sense. Instead, it is a mathematical 'game' like Conway's Game of Life or Langton's Ant. There are so many cool, neat things about the Chaos Game, and many uses for it, but that would take a good semester or two just to describe and employ it. Instead, I will describe the basics and the way I am using it at the moment:

  • Start with a polygon, like a triangle or a square, or something more inventive
  • Start at some point, maybe on the perimeter-- it doesn't really matter (well, some deeper investigation will say otherwise, but... :P)
  • Now select a vertex randomly and move halfway to that vertex. Repeat this step many times.
On the surface, it makes neat things happen if you use a triangle-- it actually does not fill it in. There are certain points that can never be reached inside the triangle and in fact, it will make a Sierpinski's Triangle. However, squares and such will be filled in.

USES: One of the really cool effects of this deals with the very important part of the iterative step. The key word is "random." If you use an algorithm that cycles, this game will show that with strong biases for certain points. Any common runs or cycles will do this. For example, if you use a square and an RNG that returns the sequence {2,3} more frequently than other pairings with 2, the space between points 2 and 3 will be darker than any other points. Since we cannot produce real "random" numbers, we can test pseudo-random number generators to see if they produce the correct result or where biases might be. A very chaotic PRNG that has a very long period will yield good results. A PRNG that has a shorter period or common runs will produce a less amazing result.

Since I have been working on PRNGs, I have been using some simple implementations of the Chaos Game. Below is a code that allows you to add in your own 'Random' routine to test as well as the choice of using a square or triangle. In z80 assembly, we often mask out bits to generate integers in a smaller range like [0,1,2,3] or [0,1,2,3,4,5,6,7] (powers of 2, minus 1 make easy masks). While this is fast and simple, the Chaos Game will tell you if this is actually destroying the chaotic behavior of your RNG. If this is the case, you might have better results using a range that isn't a power of 2. However, this can be more time consuming. It's your pick :)
Code: [Select]
.nolist
#define TASM
#define bcall(xxxx)     rst 28h \ .dw xxxx
#define equ .equ
.list
shape=4
rand=2
update=1

     .org 9D93h
     .db $BB,$6D
    bcall(4BD0h)    ;_GrBufClr
    bcall(486Ah)    ;_GrBufCpy
    bcall(4570h)    ;_RunIndicOff
    di
    ld a,$FD
    out (1),a
    ld hl,0
ChaosGame_SierpinskisGasket:
    in a,(4)    ;test ON press
    and 8
    ret z
    in a,(1)    ;test Clear press
    and 64
    ret z
    ld (coords),hl
    call Plot
    ld hl,(coords)
    srl h
    srl l
    push hl
#IF update==256
    ld a,(count)
    inc a
    ld (count),a
    jr nz,$+5
    bcall(486Ah)  ;_GrBufCpy
#ENDIF
    call Random
#IF shape==3
    call L_mod_3
    pop hl
    jr z,ChaosGame_SierpinskisGasket
    dec a
    ld a,32
    jr nz,$+7
      add a,l
      ld l,a
      jp ChaosGame_SierpinskisGasket
    add a,h
    ld h,a
    jp ChaosGame_SierpinskisGasket
#ENDIF
#IF shape==4
    and 3
    pop hl
    jr z,ChaosGame_SierpinskisGasket
    rrca
    ld b,a
    ld a,32
    jr nc,$+6
      add a,l
      ld l,a
      ld a,32
    rrc b
    jp nc,ChaosGame_SierpinskisGasket
      add a,h
      ld h,a
    jp ChaosGame_SierpinskisGasket
#ENDIF
#IF rand==0
;  From CaDan, by Iambian and Geekboy
Random:
LFSR:
    ld    hl,lfsrseed1
    ld    a,(hl)
    rrca
    ld    (hl),a
    jp nc,+_
    xor    %00111000
    ld    (hl),a
_:
 ld l,a
 ret
#ENDIF
#IF rand==1
;  From CaDan, by Iambian and Geekboy
Random:
LFSR2Byte:
  ld hl,(lfsrseed2)
  ld a,L
  rlca
  xor h
  rlca  ;
  rlca  ;
  xor h ;
  rlca
  xor h
  rlca
  adc hl,hl
  ld (lfsrseed2),hl
  ld a,h     ;for combatability
  ret
#ENDIF
#IF rand==2
;  From Zeda's library
Random:
Rand8:
;Output:  L is a pseudo-random number, DE=509, B=0, C=seed1
;Destroys:A
;Size:    141 bytes
;Speed:   fastest: 672, slowest: 796
;Notes:
;  Requires 2 seeds of 1 byte each, seed1 and seed2
;Method
;  We iterates 2 Linear Congruential Generators. 'x' is seed1, 'y' is seed2
;    (33x+17) mod 251 -> x
;    (13y+83) mod 241 -> y
;  Next, we output the lower 8 bits of x*y mod 509
;  This all gives a period of 60491 (251*241) which should be overkill for games and such
    ld hl,(seed1)
    ld h,0
;multiply by 13
    ld b,h
    ld c,l
    add hl,hl
    add hl,bc
    add hl,hl
    add hl,hl
    add hl,bc
;add 83
    ld c,83
    add hl,bc
;mod_241
    ld c,15
    ld a,h
    add a,a
    add a,a
    add a,a
    add a,a
    sub h
    add a,l        ;139
    jr nc,$+6
    add a,c
    jr nc,$+3
    add a,c
    add a,c
    jr c,$+3
    sub c
;store back to seed1
    ld (seed1),a
;seed2
    ld hl,(seed2)
    ld h,b
;multiply by 33
    ld b,h
    ld c,l
    add hl,hl
    add hl,hl
    add hl,hl
    add hl,hl
    add hl,hl
    add hl,bc
;add 17
    ld c,17
    add hl,bc
;---
;make BC=seed1
    ld c,a
;---
;mod_251
    ld a,h
    add a,a
    add a,a
    add a,h
    add a,l
    jr nc,$+8
    add a,5
    jr nc,$+4
    add a,5
    cp 251
    jr c,$+4
    add a,5
;store seed2
    ld (seed2),a

    ld h,a
    ld l,b
;H_Times_C
    sla h \ jr nc,$+3 \ ld l,c
    add hl,hl \ jr nc,$+3 \ add hl,bc
    add hl,hl \ jr nc,$+3 \ add hl,bc
    add hl,hl \ jr nc,$+3 \ add hl,bc
    add hl,hl \ jr nc,$+3 \ add hl,bc
    add hl,hl \ jr nc,$+3 \ add hl,bc
    add hl,hl \ jr nc,$+3 \ add hl,bc
    add hl,hl \ jr nc,$+3 \ add hl,bc
HL_mod_509:
;HL_mod_509 -> HL
    ld a,h
    ld d,b
    srl a
    rl d
    add a,h
    sub d
    jr nc,$+3
    inc d
    add a,l
    jr nc,$+4
    inc d
    ccf
    ld e,a
    ld hl,509
    ex de,hl
    sbc hl,de
    jr c,$+6
    add hl,de
    sbc hl,de
    ret nc
    add hl,de
    ret
#ENDIF
#IF shape==3
L_mod_3:
;Outputs:
;    A is the remainder
;    destroys L,BC
;    z flag if divisible by 3, else nz

    ld bc,0306h
    ld a,l
    res 4,l
    rlca
    rlca
    rlca
    rlca
    and 15
    add a,l
    and 31
    ld l,a
    sra l
    sra l
    and b
    add a,l
    sub c \ jr nc,$+3 \ add a,c
    sub b \ ret nc \ add a,b
    ret
;at most 123 cycles, at least 114, 30 bytes
#ENDIF
#IF rand==3
;  From Zeda's library
Random:
Rand24:
;Inputs: seed1,seed2
;Outputs:
; HLA is the pseudo-random number
; seed1,seed2 incremented accordingly
;Destroys: BC,DE
;Notes:
; seed1*243+83 mod 65519 -> seed1
; seed2*251+43 mod 65521 -> seed2
; Output seed1*seed2
    ld hl,(seed1)
    xor a
    ld b,h \ ld c,l
    ld de,83
    add hl,hl \ rla    ;2
    add hl,bc \ adc a,d    ;3
    add hl,hl \ rla    ;6
    add hl,bc \ adc a,d    ;7
    add hl,hl \ rla    ;14
    add hl,bc \ adc a,d    ;15
    add hl,hl \ rla    ;30
    add hl,hl \ rla    ;60
    add hl,hl \ rla    ;120
    add hl,bc \ adc a,d    ;121
    add hl,hl \ rla    ;242
    add hl,bc \ adc a,d    ;243
    add hl,de \ adc a,d    ;243x+83
;now AHL mod 65519
; Essentially, we can at least subtract A*65519=A(65536-17), so add A*17 to HL
    ex de,hl
    ld l,a
    ld b,h
    ld c,l
    add hl,hl
    add hl,hl
    add hl,hl
    add hl,hl
    add hl,bc
    add hl,de
    ld c,17
    jr nc,$+3
    add hl,bc
    add hl,bc
    jr c,$+4
    sbc hl,bc
    ld (seed1),hl
;seed1 done, now we need to do seed2
    ld hl,(seed2)
; seed1*243+83 mod 65519 -> seed1
; seed2*251+43 mod 65521 -> seed2
; Output seed1*seed2
    xor a
    ld b,h \ ld c,l
    ld de,43
    add hl,hl \ rla  ;2
    add hl,bc \ adc a,d ;3
    add hl,hl \ rla  ;6
    add hl,bc \ adc a,d ;7
    add hl,hl \ rla  ;14
    add hl,bc \ adc a,d ;15
    add hl,hl \ rla  ;30
    add hl,bc \ adc a,d ;31
    add hl,hl \ rla  ;62
    add hl,hl \ rla  ;124
    add hl,bc \ adc a,d ;125
    add hl,hl \ rla  ;250
    add hl,bc \ adc a,d ;251
    add hl,de \ adc a,d ;251x+83
;now AHL mod 65521
; Essentially, we can at least subtract A*65521=A(65536-15), so add A*15 to HL
    ex de,hl
    ld l,a
    ld b,h
    ld c,l
    add hl,hl
    add hl,hl
    add hl,hl
    add hl,hl
    sbc hl,bc
    add hl,de
    ld c,15
    jr nc,$+3
    add hl,bc
    add hl,bc
    jr c,$+4
    sbc hl,bc
    ld (seed2),hl
;now seed1 and seed 2 are computed
    ld bc,(seed1)
    ex de,hl
    call BC_Times_DE
    ex de,hl
    ld l,b
    ld h,0
    ld b,h
    ld c,l
    add hl,hl
    add hl,hl
    add hl,bc
    add hl,hl
    add hl,hl
    add hl,bc
    add hl,hl
    add hl,bc
    ld c,d
    ld d,e
    ld e,a
    ld a,c
    sbc hl,bc
    sbc a,b
    ret nc
    ld c,43
    add hl,bc
    ret
BC_Times_DE:
;BHLA is the result
 ld a,b
 or a
 ld hl,0
 ld b,h
;1
 add a,a
 jr nc,$+4
 ld h,d
 ld l,e
;2
 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,b
;227+10b-7p
 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,b

 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,b

 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,b

 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,b

 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,b

 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,b

;===
;AHL is the result of B*DE*256
 push hl
 ld h,b
 ld l,b
 ld b,a
 ld a,c
 ld c,h
;1
 add a,a
 jr nc,$+4
 ld h,d
 ld l,e
;2
 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,c
;227+10b-7p
 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,c

 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,c

 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,c

 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,c

 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,c

 add hl,hl
 rla
 jr nc,$+4
 add hl,de
 adc a,c

 pop de
;Now BDE*256+AHL
 ld c,a
 ld a,l
 ld l,h
 ld h,c
 add hl,de
 ret nc
 inc b
;BHLA is the 32-bit result
 ret
#ENDIF
#IF rand==4
Random:
;from ionRandom
    ld hl,(seed1)
    ld a,r
    ld d,a
    ld e,(hl)
    add hl,de
    add a,l
    xor h
    ld (seed1),hl
    ld hl,0
    ld e,a
    ld d,h
    add hl,de
    djnz $-1
    ld l,h
    ret
#ENDIF
#IF rand==5
Random:
    ld hl,(seed1)
    xor a
    ld b,h \ ld c,l
    ld de,83
    add hl,hl \ rla    ;2
    add hl,bc \ adc a,d    ;3
    add hl,hl \ rla    ;6
    add hl,bc \ adc a,d    ;7
    add hl,hl \ rla    ;14
    add hl,bc \ adc a,d    ;15
    add hl,hl \ rla    ;30
    add hl,hl \ rla    ;60
    add hl,hl \ rla    ;120
    add hl,bc \ adc a,d    ;121
    add hl,hl \ rla    ;242
    add hl,bc \ adc a,d    ;243
    add hl,de \ adc a,d    ;243x+83
;now AHL mod 65519
; Essentially, we can at least subtract A*65519=A(65536-17), so add A*17 to HL
    ex de,hl
    ld l,a
    ld b,h
    ld c,l
    add hl,hl
    add hl,hl
    add hl,hl
    add hl,hl
    add hl,bc
    add hl,de
    ld c,17
    jr nc,$+3
    add hl,bc
    add hl,bc
    jr c,$+4
    sbc hl,bc
    ld (seed1),hl
    ret
#ENDIF
#IF rand==6
Random:
    ld hl,(seed2)
; seed2*251+43 mod 65521 -> seed2
    xor a
    ld b,h \ ld c,l
    ld de,43
    add hl,hl \ rla  ;2
    add hl,bc \ adc a,d ;3
    add hl,hl \ rla  ;6
    add hl,bc \ adc a,d ;7
    add hl,hl \ rla  ;14
    add hl,bc \ adc a,d ;15
    add hl,hl \ rla  ;30
    add hl,bc \ adc a,d ;31
    add hl,hl \ rla  ;62
    add hl,hl \ rla  ;124
    add hl,bc \ adc a,d ;125
    add hl,hl \ rla  ;250
    add hl,bc \ adc a,d ;251
    add hl,de \ adc a,d ;251x+83
;now AHL mod 65521
; Essentially, we can at least subtract A*65521=A(65536-15), so add A*15 to HL
    ex de,hl
    ld l,a
    ld b,h
    ld c,l
    add hl,hl
    add hl,hl
    add hl,hl
    add hl,hl
    sbc hl,bc
    add hl,de
    ld c,15
    jr nc,$+3
    add hl,bc
    add hl,bc
    jr c,$+4
    sbc hl,bc
    ld (seed2),hl
    ret
#ENDIF
Plot:
;need to plot the pixel at HL
    ld a,l
    cp 64 \ ret nc
#IF update==1
    add a,80h
    out (16),a
#ENDIF
    ld a,h
    cp 96 \ ret nc
    ld c,l
    ld h,0
    ld b,h
    add hl,hl
    add hl,bc
    add hl,hl
    add hl,hl
    ld b,a
    rrca \ rrca \ rrca
    and 0Fh
#IF update==1
    add a,20h
    out (16),a
    add a,20h
#ELSE
    or 40h
#ENDIF
    ld c,a
    ld a,b
    ld b,93h
    add hl,bc
    and 7
    ld b,a
    inc b
    ld a,1
      rrca
      djnz $-1
    or (hl)
    ld (hl),a
#IF update==1
    out (17),a
#ENDIF

    ret

coords:    .db 0,0
count:    .db 0
lfsrseed2:
lfsrseed1:
seed1:
 .dw 256
seed2:
 .dw 0
As notes:
  • Press [ON] or [CLEAR] to exit
  • Set shape as 3 or 4 based on the mode you want to compile.
  • Set rand accordingly. There are 7 included (0,1,2,3,4,5,6). See below.
  • Set update to 256 to update every 256 iterations using the OS routine. This is not recommended. Use 1. It is faster and you see every pixel plotted.
There are 7 included PRNGs and 2 shapes. The shapes are 3 for a triangle, 4 for a square. The PRNGS are:

0 for a 1-byte Linear Feedback Shift Register (LFSR) that I was testing. It is a very fast code and pretty chaotic, but using shape=4 shows that it is actually strongly biased for simple masking. Using shape=3 yields excellent results with some minor bias. (credit goes to Iambian and Geekboy for this)

1 for a 2-byte LFSR, also from Iambian and Geekboy

2 for a much heavier/slower 8-bit PRNG I wrote. It works well for shape=3 and shows some fairly weak bias in shape=4, so it is decent for chaotic behavior

3 for an even larger, slower routine (about half the speed of the previous) but it yields a 24-bit pseudo-random number and passes both test very well. This routine is on par with the OS rand routine, but many times faster (probably hundreds or thousands times faster).

4 is the ION routine

5 and 6 are the LCGs used in (3)

You can add your own routines named Random as well, but they should return the result in L.
EDIT: Updated the code, added a download with a readme.

Offline Sorunome

  • Fox Fox Fox Fox Fox Fox Fox!
  • Support Staff
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 7920
  • Rating: +374/-13
  • Derpy Hooves
    • View Profile
    • My website! (You might lose the game)
Re: Chaos Game
« Reply #1 on: December 18, 2013, 02:44:04 pm »
Xeda, I need to do something.
You are making me look bad :P
Jk, lol, that thing is looking awesome :D

THE GAME
Also, check out my website
If OmnomIRC is screwed up, blame me!
Click here to give me an internet!

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Chaos Game
« Reply #2 on: December 18, 2013, 02:47:05 pm »
I have to go to work, but I would be interested to see the iRandom routine tested. This is just a tool for testing pseudo-random number generators.

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: Chaos Game
« Reply #3 on: December 18, 2013, 02:47:11 pm »
The behavior of quad1 seems odd IMO ... Or was it supposed to act that way ?

Either case, nice explanation :)

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Chaos Game
« Reply #4 on: December 18, 2013, 02:49:12 pm »
Quad1 is an example of a PRNG that does not behave chaotically. It is the 2-byte LFSR, compared to the other two. The empty space in Quad2 shows that there is a bias for certain runs of numbers. The empty space in Quad1 shows there is basically only the same pattern over and over.

Offline Eiyeron

  • Urist McEiyolobster
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1430
  • Rating: +130/-10
  • (-_(//));
    • View Profile
    • Rétro-Actif : Rétro/Prog/Blog
Re: Chaos Game
« Reply #5 on: December 18, 2013, 02:54:01 pm »
Are any of these functions used in Axe Parser? We could port one of these RNG to it.

Anyway, I'm quite confused on how it displays the bias. How the pixel position is defined?

Offline ben_g

  • Hey cool I can set a custom title now :)
  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1002
  • Rating: +125/-4
  • Asm noob
    • View Profile
    • Our programmer's team: GameCommandoSquad
Re: Chaos Game
« Reply #6 on: December 18, 2013, 04:16:42 pm »
That triangle looks like a triforce made out of triforces made out of triforces made out of triforces O.O

Anyway, this looks quite cool. I wonder what it would give with pentagons etc.
« Last Edit: December 18, 2013, 04:17:42 pm by ben_g »
My projects
 - The Lost Survivors (Unreal Engine) ACTIVE [GameCommandoSquad main project]
 - Oxo, with single-calc multiplayer and AI (axe) RELEASED (screenshot) (topic)
 - An android version of oxo (java)  ACTIVE
 - A 3D collision detection library (axe) RELEASED! (topic)(screenshot)(more recent screenshot)(screenshot of it being used in a tilemapper)
Spoiler For inactive:
- A first person shooter with a polygon-based 3d engine. (z80, will probably be recoded in axe using GLib) ON HOLD (screenshot)
 - A java MORPG. (pc) DEEP COMA(read more)(screenshot)
 - a minecraft game in axe DEAD (source code available)
 - a 3D racing game (axe) ON HOLD (outdated screenshot of asm version)

This signature was last updated on 20/04/2015 and may be outdated

Offline Eiyeron

  • Urist McEiyolobster
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1430
  • Rating: +130/-10
  • (-_(//));
    • View Profile
    • Rétro-Actif : Rétro/Prog/Blog
Re: Chaos Game
« Reply #7 on: December 18, 2013, 04:20:15 pm »
SOmething like this:

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55934
  • Rating: +3153/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • DJ Omnimaga Music
Re: Chaos Game
« Reply #8 on: December 18, 2013, 04:45:17 pm »
Seems kinda interesting, and also in the first two screenshots, I like how it perfectly recreates a sierpinski triangle, sort-of. Other sierpinkski programs usually left out white pixels. :P

Offline Lunar Fire

  • LV3 Member (Next: 100)
  • ***
  • Posts: 66
  • Rating: +7/-1
  • I'll be watching you from the shadows
    • View Profile
    • My Tumblr
Re: Chaos Game
« Reply #9 on: December 18, 2013, 05:49:11 pm »
I remember programming the Sierpinski triangle using a much simpler algorith that only required the value of the 3 pixels directly over the currently plotted point. The algorith was simple enough that I didn't even bother to program it in ASM, it rendered smoothly in BASIC on a 6 MHz calc.

Have you tried rendering other fractals using the Chaos Game? Is it even possible to do other Sierpinski fractals with this method, or does it end up filling the shape like the square?

Your drill is the drill that will pierce the heavens!

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Chaos Game
« Reply #10 on: December 18, 2013, 06:52:37 pm »
For anything with more than 4 vertices, it completely fills the regions. As to the talk of Sierpinski's Triangle generation, there are many, many ways of doing that. LunarFire mentioned one, and I have previously made some in assembly that are extremely fast. I also like to play with warped versions (such as the one mapping it to a circle). Attached is a screenshot of an animated one that I made that has it warped interestingly.

To answer some questions about what the resulting images mean, the first two screenshots produced Sierpinski's Triangles with decent definition because the pattern of the PRNG was fairly chaotic. If it had been too patterned (like cycling through 0,1,2,0,1,2,0,1,2,...) it would not have made a Sierpinski's Triangle.

For the ones dealing with a square, the first one was a similar pattern that had a very simple and short cycle, so it bounced back and forth between the same order of vertices. If it had jumped halfway each time to random vertices, it would have filled in the whole area (like the last one). The middle one was pretty chaotic, but the fact that it did not generate the appropriate image is due to it having a cycle (albeit a fairly long one).

Offline Eiyeron

  • Urist McEiyolobster
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1430
  • Rating: +130/-10
  • (-_(//));
    • View Profile
    • Rétro-Actif : Rétro/Prog/Blog
Re: Chaos Game
« Reply #11 on: December 19, 2013, 12:55:03 am »
Ohhhh, Nice visualisation. That could end up in a neat screensaver!

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Chaos Game
« Reply #12 on: December 19, 2013, 09:36:57 am »
Ohhhh, Nice visualisation. That could end up in a neat screensaver!
Allow me to point you to my avatar... It is actually the same fractal, but with a coloring scheme and you can see it all at once (the calculator screen was too small) :)

Also, I tested the Ion random routine as well as a few more LCGs and they turned out to work well. The LCGs only worked nicely because I did mod_65521 and mod_65519 instead of mod_65536. I also made it so that the user can press [CLEAR] to exit instead of just [ON] and I made it update every drawn pixel instead of every 256 by interleaving LCD updating into the pixel plotting routine. It is actually faster this way, taking ~8000 extra t-states for every 256 pixels instead of using that extremely slow OS routine at about 150000 (or was it 300 000?).

Anyways, in order of the best randomness routines currently included:

rand== 1 is fairly chaotic (it passes many tests showing small amounts of bias) and it is very fast. This is the LFSR that Cadan is currently using. (Use the upper byte)

rand == 3 is one I wrote. If I remember correctly, it is the method used by the calculators called l'Écuyer's algorithm. It basically runs two LCGs at the same time, then it multiplies the two using another modulo operation producing an output. This is also called an MLCG (Multiple Linear Congruential Generator) I believe. As reference, the OS routine takes more than 170 000 t-states, compared to this routine which takes less than 1600.

rand== 6 is one of the LCGs used in the previous one and also passes both tests. It is also a lot faster on its own, so while it has a much smaller period of 65521, this should be more than enough for games while providing a decent 8-bit RNG.

rand== 4 is the ION routine. If you have ever played an ION game that has 'random' events (like Donkey Kong), you might notice it gets into loops where it starts doing the same things over and over. An easy fix is to press a button. What happens is that the ION routine relies on the R register which gets incremented as code is executed. If there is no input into the system, it falls into predictable behavior because it is the same code executing every time. If you disturb the system with input, such as a keypress that causes a deviation in the game loop, the r register will start behaving more chaotically. In my tests, it worked just fine, though, almost filling in the square.

rand== 5 Is the other LCG that performed slightly worse than the ION routine

rand== 2 Is the 8-bit MCLG which leaves close to 1/4 of the square unfilled (estimate, not actually counted).

rand== 0 is an LFSR which is fast but fails most of the chaos tests. This may be a seeding issue.

EDIT: I was incorrectly testing Cadan's 2-byte LFSR. It is quite excellent.

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: Chaos Game
« Reply #13 on: December 19, 2013, 11:44:57 am »
What LFSR's are you using? I'd be curious to see if there is an LFSR that does work, as LFSR's are pretty fast.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Chaos Game
« Reply #14 on: December 19, 2013, 12:08:48 pm »
These from CaDan as offered by Geekboy:
Code: [Select]
;  From CaDan, by Iambian and Geekboy
LFSR:
    ld    hl,lfsrseed1
    ld    a,(hl)
    rrca
    ld    (hl),a
    ret    nc
    xor    %00111000
    ld    (hl),a
 ret

;  From CaDan, by Iambian and Geekboy
LFSR2Byte:
  ld hl,(lfsrseed2)
  ld a,L
  rlca
  xor h
  rlca  ;
  rlca  ;
  xor h ;
  rlca
  xor h
  rlca
  adc hl,hl
  ld (lfsrseed2),hl
  ld a,h     ;for combatability
  ret