generating a pre-defined list in an un-defined sequence

edited August 2013 in Sinclair Basic
I've decided to become a drunkard, to which end I've been drinking a whole bottle of beer in one day (whereas normally I'd make it last 2 or 3 days). So if that subject line doesn't seem to make a lot of sense, then that might be because I've just finished a bottle of "Spooky Ale - The Official GHOST BREW for All Hallows" (well, it is 11:35pm). An illustration should suffice to introduce some clarity, thus:
  10 LET p=768
  20 LET r=INT (RND*768): LET y=INT (r/24): LET x=r-y*32:
     LET q=22528+y*32+x: LET p=p-(PEEK q<>0): POKE q,0:
     GO TO 20+(NOT p)
That code will (eventually) turn the screen black in an irregular (and increasingly slow) manner. The simple solution to this is to pre-generate the list of required values and then shuffle it to get an irregular output sequence. Problems with that are: a) it uses at least 1536 bytes to hold the list; b) it gives the same sequence every time, unless the list is re-shuffled every time; which together waste both space & time.

So ... is there such a thing as a function which will generate a list of values in a specified range, each value once only, and in different sequences each time the range is generated? - and I don't mean something which keeps a list of the numbers it's generated so far, and only returns a number which isn't in its list, as that wastes even more space & time than the above example!

So, for the attributes example above, I would specify a range of 22528->23295, call the function 768 times and it would generate every number in that range once and once only, but in an undefined sequence, and a different sequence each time. Impossible, I'd say, but that might just be the drink talking.
Post edited by Battle Bunny on
«1

Comments

  • edited July 2013
    10 RANDOMIZE
    20 DIM p(768)
    30 FOR f=1 TO 768
    40 LET p(f)=f
    50 NEXT f
    60 FOR f=768 to 1 STEP -1
    70 LET i=INT(RND*f)+1
    80 POKE 22527+p(i),0
    90 LET p(i)=p(f)
    100 NEXT f
    
    Creator of ZXDB, BIFROST/NIRVANA, ZX7/RCS, etc. I don't frequent this forum anymore, please look for me elsewhere.
  • edited July 2013
    10 RANDOMIZE
    20 DIM p(768)
    30 FOR f=1 TO 768
    40 LET p(f)=f
    50 NEXT f
    60 FOR f=768 to 1 STEP -1
    70 LET i=INT(RND*f)+1
    80 POKE 22527+p(i),0
    90 LET p(i)=p(f)
    100 NEXT f
    

    I'm off the booze. It took me an hour to understand why that worked. Well, I suppose that I'll have to drink that bottle that's still in the fridge of "Honey Dew - Refreshingly Golden ..." ... Hang on! "... ORGANIC Beer" !? D,oh! I should have read the label more carefully in the shop.

    For anyone who was as bamboozled as I was, here's a typical sequence for a five element list.
    f       p()       i  p(i)=p(f)
    |  1  2  3  4  5  |  ---------
    5     *           2  p(2)=p(5)=5
       1  5  3  4  5
    4              *  2  p(2)=p(4)=4
       1  4  3  4  5
    3        *        3  p(3)=p(3)=3
       1  4  3  4  5
    2  *              1  p(1)=p(2)=4
       4  4  3  4  5
    1           *     1  p(1)=p(1)=4
       4  4  3  4  5
    
    f=5: options 1-5 are 1,2,3,4,5 got p(2)=2 set p(2)=5
    f=4          1-4     1,5,3,4       p(2)=5     p(2)=4
    f=3          1-3     1,4,3         p(3)=3     p(3)=3
    f=2          1-2     1,4           p(1)=1     p(1)=4
    f=1          1       4             p(1)=4     p(1)=4
    

    So each pass records in the selected slot the value from the slot which will be discarded next time around. If the select & discard slots are the same then the remaining slots will hold the values as yet unused. If the select & discard slots are different then the discarded value will have been saved in the selected slot so the remaining slots will still hold the values as yet unused. "It's absolutely brilliant!" (David Darling)
  • I always read these threads hoping to learn something but end up feeling like Alan Davies on an episode of QI!
  • edited July 2013
    Oh, my, that Honey Dew is nice. I'm going to have to reconsider my abstinence resolution.

    Here's an illustration to ... errrmmm ... illustrate ... the routine. The list has 22 elements "a"-"v" rather than 768. The colour codes are:
    * black on black .( 8*0 + 0 = 0 ) - not selected
    * yellow on green ( 4*8 + 6 = 38 ) - selected (line 70)
    * red on blue ....( 1*8 + 2 = 10 ) - moved (line 90)

    The left-hand column shows the sequence in which the letters have been selected. The letters along the bottom are changed to yellow on green as each one is selected, to show that all 22 have been selected in 22 passes. Run it again (and again) and it gives a different sequence each time (for quite a long while, anyway). "It's absolutely brilliant!" (Richard Darling)
    unjumble.gif

    unjumble.bas
      10 PRINT #0;AT 0,5;"abcdefghijklmnopqrstuv":
         RANDOMIZE: LET s=22: DIM p$(s,2)
      30 FOR f=1 TO s: LET p$(f)=CHR$ 0+CHR$ (f+96): NEXT f
      60 FOR f=s TO 1 STEP -1
      70   LET i=INT(RND*f)+1:  LET p$(i,1)=CHR$ 38: LET q$=p$(i,2):
           PRINT TAB 4;q$;#0;AT 0,CODE q$-92;INK 6;PAPER 4;q$
      90   LET p$(i,2)=p$(f,2): LET p$(f,1)=CHR$ 10
      96   FOR g=1 TO s:
             PRINT p$(g,2);: POKE 22528+(s-f)*32+g+4,CODE p$(g,1):
           NEXT g
     100 NEXT f: PAUSE 0
    
  • edited July 2013
    I prefer to think of it like cards. After all, that's what we're used to shuffling as a paradigm.

    Imagine we get some cards numbered (to make it simple) one to ten. Einar's routine lines 30-50 sets out the "cards".

    We then roll up a random number from one to ten. And we grab that card. So if we roll an 8, we get the 8th card. It says "8" on it, of course. So we fill in square 8 in black. We put the card in a discard pile.

    We now have 9 cards, so we roll a number from 1 to 9, and grab that. Say it's 3. The third card has "3" on it of course. So we fill in square 3 in black, drop the card into the discard pile, and go round again.

    We have 8 cards. So we roll a number from 1 to 8, and roll an 8 again. We grab the 8th card - this now has "10" written on it. So we fill in the 10th square in black, and move the card to the discard pile.

    etc.

    Repeating this until we run out of cards means we fill in the squares on the screen in a random order; hitting each one once and once only (because there's only one "card" per square). The real routine needs 768 cards of course - but the principle is exactly the same.
  • edited July 2013
    This brings to mind a routine which I wrote back in 2005, to plot all points on the Spectrum's screen in a "satisfyingly irregular" sequence and in a "reasonable time", as in this "nearly done" screen capture:
    randplot.gif

    from the routine, which took about four minutes to run overall (due to duplicate plotting). Using plain RND for x,y doesn't work, as patterns start appearing on the screen after a while. Looking at the listing, I used FRAMES to alter the RND value and then constrained it within the screen dimensions.

    What if each card was a pixel and you had 49,152 of them? Could the "shrinking stack" method be modified to pixellate the whole of the Spectrum's display file without needing 147,456 bytes for the list? That's assuming 2 bytes for each cell address and one byte for each bit position within each cell. Although only three bits are needed for the bit position, so we could get by with 2*49152 + 3*49152/8 = 116,736 bytes, I suppose. Nope, that's not going to work.

    Oh, hang on ... could the list be just 3*49152 bits = 18,432 bytes, or even just 1*49152 bits = 6144 bytes? It would be easy to determine x,y from the bit's place in the list, and then use PIXEL_ADD to place it on the screen - but what happens once that pixel/card is removed from the list/pack? The relative bit positions in the list become messed up after the first selection and the x,y formula will go wrong. Nope, that's not going to work.

    If that "shrinking stack" method could somehow be employed in this other instance to eliminate the duplicate plotting, then I would expect it to speed it up substantially.
  • edited July 2013
    Actually you would need 256*192*2=98304 bytes since each screen coordinate can be represented using 2 bytes (X and Y coordinates). Thus you can't use exactly the same method in this case.

    I can imagine a couple alternatives. First, do you have the link to the original thread?
    Creator of ZXDB, BIFROST/NIRVANA, ZX7/RCS, etc. I don't frequent this forum anymore, please look for me elsewhere.
  • edited July 2013
    I can imagine a couple alternatives. First, do you have the link to the original thread?

    Google "Random plot not so random" (including the quotes) and it comes top of the list. The originating Jim was a different Jim. I'd improved my version substantially afterwards; at my last post the m/c version was taking 80 minutes(!). I got it down to 4 minutes - not quite so embarrasing.
  • edited July 2013
    Look up LFSR :)

    I confess I originally considered and discarded this idea, but now that you mentioned it, I think it may work...

    The reason I discarded it before, is that Battle Bunny requested a different sequence each time. However LFSR will always generate exactly the same sequence every time. In practical terms, we would always see on screen PLOT 0,0 immediately followed by PLOT 143,85 immediately followed by PLOT 37,158 for instance.

    Notice this is different from a random generator, that produces internally a much larger sequence and allows us to "see" a different subset each time, thus it "seems" like a different sequence each time.

    However, this is the reason I'm now considering it may work: Each time, if we use the entire sequence but start at a different position in the sequence, it may give the impression of a different sequence anyway. What I mean is, although we will always see PLOT 0,0 immediately followed by PLOT 143,85 immediately followed by PLOT 37,158, this order may be hard to recognize if it sometimes happens at the beginning when the screen is almost empty, sometimes on an almost filled screen, etc. There are so many pixels that the user should not pay much attention to each position.

    The only way to be sure is to try it :)
    Creator of ZXDB, BIFROST/NIRVANA, ZX7/RCS, etc. I don't frequent this forum anymore, please look for me elsewhere.
  • edited July 2013
    On second thought, there's a perfect solution combining RND and a 16 bits LFSR. The algorithm to fill the screen would work as follows:
    • First use RND to generate a new 16 bits random number. Let's call it A.

    • Randomly choose a starting point within the LFSR sequence. You may use the same RND to do so.

    • Finally execute LFSR exactly 65536 times. Each execution will provide a number B from 0 to 65535, without repetition. Now calculate C = A xor B, then X=HSB(C) and Y=LSB(C). If this position is outside the screen simply discard it, otherwise PLOT a point at this position.

    Notice that calculating C = A xor B will also generate a sequence of numbers from 0 to 65535 without repetition. Since we will use a different value of A each time we fill the screen, this sequence will be different each time!
    Creator of ZXDB, BIFROST/NIRVANA, ZX7/RCS, etc. I don't frequent this forum anymore, please look for me elsewhere.
  • edited July 2013
    LFSR is probably the best answer, to give a random effect.

    Personally, I'd just use a prime number, about 30% of the full range. Start at the first position and add that number, then erase that square. Then add the same number again and erase another character. Wrap when you go past 767. But then the sequence would look a bit regular and would be the same every time. That's how the creatures in the hopper in Buzzsaw+ are animated. They all appear to be animated independently, but really it's a sequence that gets to each one once before it repeats.
    Joefish
    - IONIAN-GAMES.com -
  • edited July 2013
    joefish wrote: »
    Personally, I'd just use a prime number, about 30% of the full range. Start at the first position and add that number, then erase that square. Then add the same number again and erase another character. Wrap when you go past 767. But then the sequence would look a bit regular and would be the same every time. That's how the creatures in the hopper in Buzzsaw+ are animated. They all appear to be animated independently, but really it's a sequence that gets to each one once before it repeats.

    To be more accurate, it doesn't need to be a prime number, but a co-prime in relation to the grid size :)

    But yes, I used exactly the same approach in BIFROST*. This approach works well on very small grids like we did, but not so well for attribute squares in a 24x32 grid. And certainly not for individual pixels in a 256x192 grid, where its regularity will become too obvious.
    Creator of ZXDB, BIFROST/NIRVANA, ZX7/RCS, etc. I don't frequent this forum anymore, please look for me elsewhere.
  • edited July 2013
    A full 256*192 plot can be done with the "shrinking stack" method. On the +128k RAM pages 0,1,2,3,4,6 provide exactly the right amount of space to hold all 49152 coordinate pairs (ie. 6 * 16kb). I've nearly finished it, but it's too late and I'm too tired to continue just now. I'll finish it in the morning, unless I discover some dreadful flaw in the plan. All the values loaded OK (takes about 5 seconds), and I've just copied the modified "RND+" function from my old routine, and I know that works to give a nice irregular spread ( ref. the pic in post #8 ), so it's just a matter of finishing off the extraction loop.
  • edited July 2013
    Notice that calculating C = A xor B will also generate a sequence of numbers from 0 to 65535 without repetition. Since we will use a different value of A each time we fill the screen, this sequence will be different each time!

    That should work very well. Note you don't have to find explicit X and Y coords followed by a call to PLOT -- the number 0-49151 can be converted to a display address and pixel position (within a byte) directly. C & 7 = bit position 0-7 within byte. C/8+0x4000 = address in the display file.

    BB, this method takes 0 bytes of memory and will be very fast. The only downside is you have to iterate over 64k-48k unused numbers in the sequence. Also be aware 0 is never visited by an LFSR so to include it, perhaps subtract 1 from the 16-bit value before deciding if it is in the 0-49151 range.
  • edited July 2013
    Well, it works, but it's slower than my old version. It takes about 6 minutes, probably because of all the page swapping. Plus it leaves one bit unplotted - bit 0 of ($4000). It does give a nice irregular pattern like the old one though. I used Jon Ritman's routine from Head over Heels to generate the numbers (Star Tip 3 in YS).

    --

    I put in a check to skip the bank switching when the two pages were the same, but it made little difference to the running time.

    I fixed the unplotted bit and shaved a minute off the running time by removing the "+1" from the pointer calculation. The reason it made such a difference was that I was doing "const_one, add" at the end of a calculator command sequence rather than an "inc bc" after the FP_TO_BC call - and the increment wasn't needed either way, anyway.
  • fogfog
    edited July 2013
    the sort of effect is used a lot in c64 demos and intros esp from the basic screen to clear it over the years.

    but instead of using plotting , there is chars used.. 2 off the top of my head are one slides each char line.. so line 1 is left right .. and 2 is right to left etc .. or random inverted blocks (lethargy by cosines uses that IRC) quick way to clear the screen.

    there is a demo (tmr will know) .. that draws a vine on the screen in hi-res like a speccy colour mode.. and scrolls up the screen, really clever how it's done. forgot the name of the demo

    people do use pre-calc'd basic for sinus tables for sprites etc :)
  • edited July 2013
    That should work very well. Note you don't have to find explicit X and Y coords followed by a call to PLOT -- the number 0-49151 can be converted to a display address and pixel position (within a byte) directly. C & 7 = bit position 0-7 within byte. C/8+0x4000 = address in the display file.

    Good thinking!
    Creator of ZXDB, BIFROST/NIRVANA, ZX7/RCS, etc. I don't frequent this forum anymore, please look for me elsewhere.
  • edited July 2013
    OK, I had to do one of those LFSR jobs as well, despite having no idea what they were. It takes about 10 seconds to blank the screen ... but ... there's one sma-a-a-a-a-ll problem ... every so often it finishes with one or two points unplotted, whereas my more sedate version couldn't avoid always plotting all of them.

    In the listing the blue section is the LFSR routine, the green section is Jon Ritman's routine, and the magenta section is an implementation of Alcoholics Anonymous' plotting idea.
            org  23296
    
    SEED:   equ  23670
    FRAMES: equ  23672
    
    PixOUT:
            ld   hl,(SEED)
            ld   (SEED32+2),hl
            ld   hl,(FRAMES)
            ld   (SEED32),hl
            call RANDOM
            ex   de,hl           ;DE=base start
            push de
            call RANDOM
            pop  de              ;HL=LFSR start
            ld   bc,0000         ;BC=counter
    
    LOOP1:
            push bc
    ;[color=blue]blue section replaced with ES version
            ld a,l
            rla
            rla
            xor l
            rla
            xor l
            rla
            rla
            xor l
            rla
            rla
            rla
            rr h
            rr l
    ;[/color]
            ld   a,h
            xor  d
            ld   b,a
            ld   a,l
            xor  e
            ld   c,a             ;BC=plot coordinates
    
            push hl              ;[color=red]
            call Magenta[/color]         ;replaces all lines which were here
            pop  hl
            pop  bc
            dec  bc
            ld   a,b
            or   c
            jp   nz,LOOP1
    ;[color=red]
            ld   b,d
            ld   c,e
            call Magenta
    ;[/color]
            ld   bc,$0000
            call $1f3d           ;PAUSE_1
            ret
    
    Magenta:
            ld   hl,$bfff
            sbc  hl,bc          ;[color=red]
            ret  c
            push de             ;[/color][color=magenta]
            ld   a,c
            and  7               ;A =bit position
            inc  a
            ld   e,a
            xor  a
            scf
    RotateLeft:                  ;rotate bit to correct position in A
            rla
            dec  e
            jr   nz,RotateLeft
    
            srl  b
            rr   c
            srl  b
            rr   c
            srl  b
            rr   c               ;BC=BC/8
            ld   hl,$4000
            add  hl,bc           ;HL=16384+INT(yx/8)=display file address
            or   (hl)
            ld   (hl),a          ;update display byte [color=red]
            pop  de
            ret                  ;[/color]
    ;[color=green]
    SEED32: defm "FOUR"          ;must be 4 bytes
    
    RANDOM: LD HL,(SEED32+2)
            LD D,L
            ADD HL,HL
            ADD HL,HL
            LD C,H
            LD HL,(SEED32)
            LD B,H
            RL B
            LD E,H
            RL E
            RL D
            ADD HL,BC
            LD (SEED32),HL
            LD HL,(SEED32+2)
            ADC HL,DE
            RES 7,H
            LD (SEED32+2),HL
            JP M,RANDOM3
            LD HL,SEED32
    RANDOM2:INC (HL)
            INC HL
            JR Z,RANDOM2
    RANDOM3:LD hl,(SEED32)
            RET                  ;[/color]
    
  • edited July 2013
    OK, I had to do one of those LFSR jobs as well, despite having no idea what they were. It takes about 10 seconds to blank the screen ... but ... there's one sma-a-a-a-a-ll problem ... every so often it finishes with one or two points unplotted, whereas my more sedate version couldn't avoid always plotting all of them.

    The LFSR formula you chose doesn't support zero. Notice that, if HL is zero before executing the blue section, then HL will be still zero after the blue section.

    Therefore the first problem is, you need to ensure your "LFSR start" value is never zero, otherwise your algorithm will plot all points at exactly the same position.

    The second problem is, since HL is never zero, then "HL xor DE" will be always different from DE. Because of this, the point corresponding to position DE will never be plotted. Just remember to plot an extra point at position DE before or after executing everything else.
    Creator of ZXDB, BIFROST/NIRVANA, ZX7/RCS, etc. I don't frequent this forum anymore, please look for me elsewhere.
  • edited July 2013
    BTW I didn't test it, but at first glance I think the entire blue section could be optimized to this:
    ld   b,l
            ld   a,b
            srl  b
            srl  b
            xor  b
            srl  b
            xor  b
            srl  b
            srl  b
            xor  b
            slr  a
            rr   h
            rr   l
    

    And at second glance I think the entire blue section could be optimized to this:
    ld   a,l
            rla
            rla
            xor  l
            rla
            xor  l
            rla
            rla
            xor  l
            rla
            rla
            rla
            rr   h
            rr   l
    
    Creator of ZXDB, BIFROST/NIRVANA, ZX7/RCS, etc. I don't frequent this forum anymore, please look for me elsewhere.
  • edited July 2013
    Overwriting DE doesn't help either ...

    If the entire Magenta section is put in a subroutine enclosed with PUSH DE/POP DE, with the out of bounds check at the top, thus:
    Magenta: ld hl,$bfff : sbc hl,bc : ret c : push de ... pop de : ret
    and a "call Magenta" put in its place; then, after the end of LOOP1, this:
    ld b,d : ld c,e : call Magenta
    then it works every time (including your last LFSR change).

    I think that little loop at RANDOM2 stops that routine returning zero.
  • edited July 2013
    If the entire Magenta section is put in a subroutine enclosed with PUSH DE/POP DE, with the out of bounds check at the top, thus:
    Magenta: ld hl,$bfff : sbc hl,bc : ret c : push de ... pop de : ret
    and a "call Magenta" put in its place; then, after the end of LOOP1, this:
    ld b,d : ld c,e : call Magenta
    then it works every time (including your last LFSR change).

    You have just described the required change to "plot an extra point at position DE after executing everything else", right?
    I think that little loop at RANDOM2 stops that routine returning zero.

    I suspect it only prevents all 4 bytes from being zero at the same time, but it doesn't prevent the first 2 bytes from being zero, thus setting HL to zero.
    Creator of ZXDB, BIFROST/NIRVANA, ZX7/RCS, etc. I don't frequent this forum anymore, please look for me elsewhere.
  • edited July 2013
    I've updated the listing in post#21 with the changes I mentioned; new lines are in red; moved lines retain their colours; deleted lines aren't there.

    --

    I also changed the "CALL RANDOM" lines to "CALL RANDOM16" and added this:
    RANDOM16:
            call RANDOM
            ld   a,h
            or   l
            ret  nz
            ld   hl,(SEED32+2)
            ret
    

    --

    Here's the Wikipedia page which covers the genesis of that "shrinking stack" method of generating an irregular list of numbers.

    https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

    The code in the paragraph regarding the Richard Durstenfeld "modern algorithm" variation of the Fisher-Yates shuffle is exactly it.

    ... and here's the page where I got the info for the LFSR method - the "Fibonacci LFSRs" section. I couldn't make head-or-tail of the C code, so I wrote a Z80 routine based on the picture.

    https://en.wikipedia.org/wiki/Linear_feedback_shift_register
  • edited July 2013
    Wow. That's interesting.

    The thing I took away from that is that I doubt there's a card game on the spectrum that has a genuine shuffle - that is shuffles the deck such that any combination is possible, and equally likely. Mostly because a random seed with around 250 bits would be fairly unlikely on the humble speccy.

    For that matter, I suspect most card games haven't bothered on any platform at all. Perhaps excluding the hardware random number generators.
  • edited July 2013
    Can you guess what it is yet? (just press ENTER, Spectrum +128k only)

    http://www.users.globalnet.co.uk/~jg27paw4/pourri/pixoutdisp128part2.z80

    This thread came about originally through working on the Compendium and coming across my old "random plot screen erase" and "random attribute screen reveal" routines. So I thought, why not combine the two ideas? I used ZX-Paintbrush to convert the picture off the Wikipedia page.

    It uses the "Richard Durstenfeld "modern algorithm" variation of the Fisher-Yates shuffle" (otherwise known as the Saukas method), but instead of putting every coordinate in the list it encodes a picture by just entering those coordinates where the pixel is set, setting all the others to $ffff. It takes about 5 minutes, by the way; it's in need of some inspiration to speed it up. The border goes white when it's finished.

    It sets the first half of the 32-bit seed in part 1 and the second half in part 2, so the reveal should be different each time it's run (not each time the snapshot is loaded, of course). The 128 snapshot runs OK on Spin, Fuse, SpecEmu and Spectaculator.
  • edited July 2013
    A galois lfsr is simpler to implement. Here's a version that (might) work:
    start:
    
       ld de,0         ; repeat 65536 times
       ld hl,$3141     ; initial lfsr state
    
    lfsr_galois:
    
       ; 16-bit Galois LFSR
       ; x^16 + x^14 + x^13 + x^11 + 1
    
       ; hl = 16-bit Galois state
    
       srl h
       rr l
       jr nc, done_lfsr
    
       ld a,$b4
       xor h
       ld h,a
    
    done_lfsr:
       
       dec hl     ; alter lfsr range to include 0
       
       ; only 0 <= lfsr < $c000=49152 is useful
       
       ld a,h
       cp $c0
       jr nc, skip_value
    
       ; have a valid screen address
       
       ld a,l
       and $07
       ld b,a
    
       ld a,1
       jr z, done_shift
    
    shift:
    
       add a,a
       djnz shift
    
    done_shift:
    
       ld c,l
       ld b,h
       
       srl h
       rr l
       scf      ; introduce 1 in 0x4000
       rr h
       rr l
       srl h
       rr l
       
       or (hl)
       ld (hl),a
    
       ld l,c
       ld b,h
    
    skip_value:
    
       inc hl
    
    done_yet:
    
       dec e
       jp nz, lfsr_galois
       dec d
       jp nz, lfsr_galois
       
       ret
    

    No XOR with the lfsr state in there; instead you can choose a random non-zero initial state.


    Edit: Funny how you always notice these things two minutes after you post but the lfsr does not have to shift right -- you can also shift it left, which means the "srl h; rr l" in there can be changed to "add hl,hl" and the xor part can have its bits reversed and applied to register l. I was wondering about the volatility of the sequence generated by this version as it makes changes in the topmost bits of the lfsr state and then we throw away any numbers above 49152 and that would seem to mean changes have to trickle down by divide-by-twos which might be a noticeable pattern. Reversing the galois shift gets rid of that concern without having to try another polynomial. There are also a couple of spots things can be sped up but I know there are some who enjoy that sort of thing so let's leave that as an exercise :D
  • edited July 2013
    Can you guess what it is yet? (just press ENTER, Spectrum +128k only)

    http://www.users.globalnet.co.uk/~jg27paw4/pourri/PixOUTdisp128part2.Z80

    Your link doesn't match the filename you have used. It should be:

    www.users.globalnet.co.uk/~jg27paw4/pourri/pixoutdisp128part2.z80
    It uses the "Richard Durstenfeld "modern algorithm" variation of the Fisher-Yates shuffle" (otherwise known as the Saukas method), but instead of putting every coordinate in the list it encodes a picture by just entering those coordinates where the pixel is set, setting all the others to $ffff. It takes about 5 minutes, by the way; it's in need of some inspiration to speed it up. The border goes white when it's finished.

    Why don't you just use the same algorithm from post #21? Just keep somewhere else in memory a copy of the image you want to display (such as address $c000) and, instead of plotting each coordinate, compare with the stored image first to decide if each position must be plotted or erased. This way, the new image will gradually appear even if there was another image already on screen.
    Creator of ZXDB, BIFROST/NIRVANA, ZX7/RCS, etc. I don't frequent this forum anymore, please look for me elsewhere.
  • edited July 2013
    I've corrected the above URL, thanks.

    I've speeded up the program; it now takes about a minute. I timed the various parts, and each pass through the calculator segment was taking about 20,000T, so I decided that I needed to do something about that.

    I could dispense with the INT (...)+1 as FP_TO_BC gave me the INT and I didn't want the +1 anyway, which just left the "f * SEED32 / 65536". Then I realised that I didn't need the division either, as "/ 65536" is the same as shifting 16 bits to the right, so I just needed to put SEED32 in a separate register pair and treat it as a binary fraction. So then all I needed was a 32-bit multiplication routine giving a 64-bit answer and rounding the integer half, which I'd got off a page written by Andre Adrian a while ago. So I could get rid of all the calculator-related code which was taking up most of the time.

    The ROM calculator is very clever, and handy at times, but it's rather slow.
  • edited July 2013
    Why don't you just use the same algorithm from post #21? Just keep somewhere else in memory a copy of the image you want to display (such as address $c000) and, instead of plotting each coordinate, compare with the stored image first to decide if each position must be plotted or erased. This way, the new image will gradually appear even if there was another image already on screen.

    If I just store the image data then that would be 6912 bytes and would give a 6912 byte-level reveal whereas I was doing a 49152 bit-level reveal. I don't see how that would work at the bit level.

    I did a byte-level version of the shuffle method using JR's RND and AA's long multiplication routine and it takes 10 seconds to complete the picture, although it needs 6912*3 bytes as it has to shuffle the bytes in synch with their screen addresses otherwise it wouldn't know where to put anything. The LFSR method would only need the picture data, but it would be too quick, so would need an 8* delay on each pass to make it around 10 seconds again (which seems a reasonable time to wait for the picture).
Sign In or Register to comment.