Omnimaga
Calculator Community => Other Calc-Related Projects and Ideas => TI Z80 => Topic started by: Xeda112358 on December 18, 2013, 02:37:11 pm
-
The Chaos Game (http://en.wikipedia.org/wiki/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 :)
.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.
-
Xeda, I need to do something.
You are making me look bad :P
Jk, lol, that thing is looking awesome :D
-
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.
-
The behavior of quad1 seems odd IMO ... Or was it supposed to act that way ?
Either case, nice explanation :)
-
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.
-
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?
-
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.
-
SOmething like this:
(http://ecademy.agnesscott.edu/~lriddle/ifs/pentagon/pentagonLarge.gif)
-
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
-
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?
-
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).
-
Ohhhh, Nice visualisation. That could end up in a neat screensaver!
-
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.
-
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.
-
These from CaDan as offered by Geekboy:
; 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
-
Xeda: I have a challenge for you: Do a Mandelbrot set.
That's a chaos game, right?
/me hopes he didn't ask something stupid...
-
The Mandelbrot set is not a chaos game, actually. A chaos game is just starting with a handful of vertices, and jumping halfway to a randomly selected vertex. Ideally, you would do this for infinitely many points, but we can't, so we just do it for a gazillion.
-
I am working on updating it to allow custom inputs for vertices. It Currently allows input as a real list in the form of {y1,x1,y2,x2,...} or a complex list where each component is {y1+ix1,y2+ix2,...}.
However, for quick testing it will probably be a lot easier to simply pass a number and have the program generate a regular polygon with the given number of vertices. So should I add this? The program is currently small-ish at 210 bytes plus the RNG to test.
Also, I was thinking of having it be able to take input in a string as "nn,filename" where nn is the number of vertices and filename is the variable that has a data stream to directly test.
Thoughts?
-
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.
I figured out that I was using the second one incorrectly. The lower bits are not that great to use, but the upper byte or using both actually turns out really well. I started the seed with 1.
Also, I made an update. It will run a little slower now, but it is much more useful offering many more vertex tests without the need to constantly recompile. You can supply your own vertices or have the program generate N vertices for a regular polygon (it uses a sine routine).