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... )
• 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.

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.

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.

That triangle looks like a triforce made out of triforces made out of triforces made out of triforces

Anyway, this looks quite cool. I wonder what it would give with pentagons etc.

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.

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!

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.

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