flat assembler
Message board for the users of flat assembler.

Index > Main > Create random patterns

Author
Thread Post new topic Reply to topic
Picnic



Joined: 05 May 2007
Posts: 1288
Location: Paradise Falls
Picnic
Hi guys,

Here's my problem:
I'm trying to create random patterns-paths like the ones you see below. I have a 3x3 board.
Starting from a random position '1' numbers can be placed horizontally or vertically any distance but not diagonally.

Please follow any of the below 1..2..3..4.. to undestand better.

459
312
768

162
453
978

825
716
934

I could use some help.
Have a nice day everyone.
Post 17 Aug 2008, 08:23
View user's profile Send private message Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
I'll explain an algorithm, i'm sorry I don't have time now to put it in code, but hope it helps anyway.

Basically, from any given "position" you have, there are only 4 different locations you can place another number. There is a problem, of course, if that space is already occupied by another number previously. You will need to take special case with that one.

Thus, your random number generator should return a number between 0..3 (4 positions). Then, you can use such a result in the algorithm where to place the number. If that square is already occupied, try another one. The problem here is that in this way, some squares will get more "probability" than others.

A better, and more complicated, way is to calculate how many free "positions" you can put a number in, and then generate a random number between 0..n-1 (n being the number of positions).

It is simple to generate a pseudo-random number in a given range 0..n. Just use "x % n" where '%' is the modulus and 'x' is the result from a random number generator (whatever you use).


To speed this up, create a table, with a structure made of 4 cells (also called a multi-dimensional array). The first part determines the current position of the number. The structure is simply:

Code:
cells[4]    
that is, an array of 4 cells ("from the current position").

Here's how I mark the positions of the cells:
Code:
012
345
678    


For example, the table looks like this (C code):

Code:
{
  {1,2,3,6} // top-left position (the free horizontal/vertical cells FROM it)
  {0,2,4,7} // top-middle position (1)
  {0,1,5,8} // top-right position (2)

  {0,4,5,6} // middle-left position (3)
  {1,3,5,7} // middle position (4)
  {2,3,4,8} // middle-right position (5)

  {0,3,7,8} // bottom-left position (6)
  {1,4,6,8} // bottom-middle position (7)
  {2,5,6,7} // bottom-right position (8)
}    
Then you can use the result from the RNG and get a "value" in the array, then place the number there. Of course, if that cell is occupied already, you'll have to choose another one (not random again as it may cause a halt, rare but it can).

The problem with the above is that I believe it's not the best method at all.
Post 17 Aug 2008, 11:45
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
Okay try this:
Code:
;Initialize:
        mov     eax,010203h
        mov     ebx,060504h
        mov     ecx,070809h
        mov     edx,1009 ; seed can be zero
        mov     esi,123  ; Repeat shuffle x 123
      .shuffle:
        ror     edx,13     ;\
        imul    edx,104729 ;|
        rol     edx,13     ;\_RND()
        add     edx,107723 ;/

        test    edx,1
        jne     @f
        xchg    eax,ebx
      @@:
        test    edx,2
        jne     @f
        xchg    ebx,ecx
      @@:
        test    edx,4
        jne     @f
        xchg    ecx,eax
      @@:

        test    edx,8
        jne     @f
        imul    eax,01000001h ;=03010203
        bswap   eax           ;=03020103
        and     eax,00FFFFFFh ;=00020103
        imul    ebx,01000001h
        bswap   ebx
        and     ebx,00FFFFFFh
        imul    ecx,01000001h
        bswap   ecx
        and     ecx,00FFFFFFh
      @@:
        test    edx,16
        jne     @f
        xchg    al,ah         ;=00010302
        xchg    bl,bh
        xchg    cl,ch
      @@:
        test    edx,32
        jne     @f
        bswap   eax           ;=03020100
        shr     eax,8         ;=00030201
        bswap   ebx
        shr     ebx,8
        bswap   ecx
        shr     ecx,8
      @@:
        sub     esi,1
        jne     .shuffle ;shuffle many times Smile
    

Its definitely not what you want, but its a start. I got the idea from Sudoku, where this is a perfect application.
Post 17 Aug 2008, 11:46
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
I'd go for recursive algorithm, that in each step does this:

pseudocode
Code:

call recursive_proc for some random initial position

bool recursive_proc(x,y,number):
  board[x,y] = number
  if number=9, return true
  if no empty neighbor, return false
  x1,y1 = random_empty_neighbor(x,y)
try_this:
  result = recursive_proc(x1, y1, number+1)
  if result = true, return true
  if tried all empty neighbors, return false
  x1,y1 = next_empty_neighbor()
  goto try_this
    


This is the idea, there will be few more small problems during implementation (how to save which neighbors have been already tested, for next_empty_neighbor()). If you haven't done anything recursive, you might want to start with something simpler.

PS: upon every "return false", you obviously also have to reset "board[x,y]" to empty state.
Post 17 Aug 2008, 11:49
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: Paradise Falls
Picnic
Yes, a recursive way could be a straightforward solution for this problem, to generate such patterns.
Thanks for the feedback so far guys, you gave me ideas to play.
Post 17 Aug 2008, 15:38
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
I have studied this problem a bit. The thing is that though this seems a really complicated puzzle, it only really has 21 different solutions. Others are just variations of the same puzzle with swapping/shifting the rows/columns. One deviation is 90° rotation I think because 180° I was able to reproduce with swap rows 1&3 & swap columns 1&3.

When you think about it, there's only one square you can put your '1' into and when you think a bit further, there's only one place where you can put '2' into. '3' has two places to go etc. some explanations attached in the manner of spreadsheet.

Code:
;Initialize:
        mov     edx,103583 ; seed can NOT be zero
                           ; better if it was random
        mov     esi,67     ; Repeat shuffle x 67
                           ; is 3 or 4 enough??? Test it!
        push    rdx
        mov     eax,edx
        xor     edx,edx
        mov     edi,21
        div     edi
        mov     eax,edx
        pop     rdx

        lea     eax,[eax*3]
        shl     eax,2
        mov     ecx,[Init+eax+8]
        mov     ebx,[Init+eax+4]
        mov     eax,[Init+eax+0]
      .shuffle:
        ror     edx,13     ;\
        imul    edx,104729 ;|
        rol     edx,13     ;\_RND()
        add     edx,107723 ;/
;#######################################################
;# Sample!
;# edx=...1001001001010b
;#              |   \_/_three lower bits exchange rows
;#              |\_/____three next bits exchange columns
;#              |_______this bit rotates by 90°
;#######################################################
        test    edx,1
        jne     @f
        xchg    eax,ebx
      @@:
        test    edx,2
        jne     @f
        xchg    ebx,ecx
      @@:
        test    edx,4
        jne     @f
        xchg    ecx,eax
      @@:

        test    edx,8
        jne     @f
        imul    eax,01000001h ;=03010203
        bswap   eax           ;=03020103
        and     eax,00FFFFFFh ;=00020103
        imul    ebx,01000001h
        bswap   ebx
        and     ebx,00FFFFFFh
        imul    ecx,01000001h
        bswap   ecx
        and     ecx,00FFFFFFh
      @@:
        test    edx,16
        jne     @f
        xchg    al,ah         ;=00010302
        xchg    bl,bh
        xchg    cl,ch
      @@:
        test    edx,32
        jne     @f
        bswap   eax           ;=03020100
        shr     eax,8         ;=00030201
        bswap   ebx
        shr     ebx,8
        bswap   ecx
        shr     ecx,8
      @@:
        test    edx,64
        jne     @f
        ;Dislocate each row by +1 compared to previous one
        imul    ebx,01000001h
        shr     ebx,8
        xchg    cl,ch
        bswap   ecx
        shr     ecx,8
        ;Replace interesting parts
        xchg    ah,bh
        xchg    al,cl
        xchg    bx,cx
        xchg    ebx,ecx
        ;Start locating each row properly
        xchg    bl,bh
        bswap   ebx
        shr     ebx,8
        imul    ecx,01000001h
        shr     ecx,8
      @@:

        sub     esi,1
        jne     .shuffle ;shuffle many times Smile

; Many codes later Very Happy
align 16
      Init dd 00080904h,00010203h,00070605h ;x21
           dd 00080704h,00010203h,00090605h
           dd 00090804h,00010203h,00060705h
           dd 00070804h,00010203h,00060905h
           dd 00060504h,00010203h,00070809h
           dd 00060504h,00010203h,00070908h
           dd 00090504h,00010203h,00080607h
           dd 00050604h,00010203h,00080709h
           dd 00050604h,00010203h,00090708h
           dd 00050904h,00010203h,00060807h
           dd 00040305h,00010206h,00090807h
           dd 00040305h,00010206h,00080907h
           dd 00040309h,00010208h,00050607h
           dd 00040308h,00010209h,00050706h
           dd 00060307h,00010208h,00050409h
           dd 00060307h,00010209h,00050408h
           dd 00090308h,00010207h,00050406h
           dd 00070308h,00010209h,00060405h
           dd 00080307h,00010206h,00090405h
           dd 00050304h,00010209h,00060708h
           dd 00090304h,00010205h,00080706h    
    


Description: My tests in OO.o converted to MS Excel
Download
Filename: algo.xls
Filesize: 84.5 KB
Downloaded: 98 Time(s)

Description: A pdf that spreads over 3 pages...
Download
Filename: algo.pdf
Filesize: 32.76 KB
Downloaded: 115 Time(s)


_________________
My updated idol Very Happy http://www.agner.org/optimize/
Post 17 Aug 2008, 15:57
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: Paradise Falls
Picnic
Thanks for the analysis Madis731 i appreciate that.
So there are 21 different unique solutions and all the rest are mostly variations.
I've tested your code a bit, it outputs quite good paths, changing seed and repeat value.
Post 17 Aug 2008, 20:24
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
You're welcome - the random part is just what I found and played with. If its not what you are looking for, you can always change the random function or just the prime values.

May we know what you are using it for?
Post 18 Aug 2008, 06:14
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: Paradise Falls
Picnic
Sure, i'll use them as levels on a hidden mini bonus game, inside an application.
Originally i did some handmade patterns then i thought it would be cool this mini game to have some kind of generator Smile
Post 18 Aug 2008, 12:34
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
Oooh Very Happy a game!
Then you definitely need speed and compactness and all the new features CPUs have, like the SSSE3:
Code:
        mov     edx,103583 ; seed can NOT be zero
                           ; better if it was random
        mov     esi,167    ; Repeat shuffle x 167
                           ; is 3 or 4 enough??? Test it!
        push    rdx
        mov     eax,edx
        xor     edx,edx
        mov     edi,21
        div     edi
        mov     eax,edx
        pop     rdx

        add     eax,eax
        movdqu  xmm0,dqword[Init+eax*8]
      .shuffle:
        ror     edx,13     ;\
        imul    edx,104729 ;|
        rol     edx,13     ;\_RND()
        add     edx,107723 ;/

        mov     eax,edx
        and     eax,111b
        shl     eax,4
        pshufb  xmm0,[Shuf+eax] ;The LUT approach! SSSE3
        sub     esi,1
        jne     .shuffle ;shuffle many times Smile

;Many lines of game-code later...

align 16
      Init dq 0605010203080904h,07h ;x21
           dq 0605010203080704h,09h
           dq 0705010203090804h,06h
           dq 0905010203070804h,06h
           dq 0809010203060504h,07h
           dq 0908010203060504h,07h
           dq 0607010203090504h,08h
           dq 0709010203050604h,08h
           dq 0708010203050604h,09h
           dq 0807010203050904h,06h
           dq 0807010206040305h,09h
           dq 0907010206040305h,08h
           dq 0607010208040309h,05h
           dq 0706010209040308h,05h
           dq 0409010208060307h,05h
           dq 0408010209060307h,05h
           dq 0406010207090308h,05h
           dq 0405010209070308h,06h
           dq 0405010206080307h,09h
           dq 0708010209050304h,06h
           dq 0706010205090304h,08h

align 16
      label Shuf dqword
           dq 0706020100050403h,08h ;swap row 1&2
           dq 0403080706020100h,05h ;swap row 2&3
           dq 0100050403080706h,02h ;swap row 1&3
           dq 0607050304020001h,08h ;swap col 1&2
           dq 0806040503010200h,07h ;swap col 2&3
           dq 0708030405000102h,06h ;swap col 1&3
           dq 0508010407000306h,02h ;rotate by 90°
           dq 0300070401080502h,06h ;rotate   -90° ;This is just a LUT filler. Now it has 8 (1000b) look-up values.
    

Btw, this also has a really neat SSE2 implementation which is somewhat shorther than my original, but much longer than the SSSE3 version posted here.
It goes something like xmm0~eax, xmm1~ebx, xmm2~ecx and then pshufd (or pshuflw) within each xmm and xchg can be simulated through the use of xmm3.
Good luck! I hope to see your game soon...
Post 18 Aug 2008, 14:51
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Picnic



Joined: 05 May 2007
Posts: 1288
Location: Paradise Falls
Picnic
Neat implementation Madis731 and small code.
Muchos gracias Smile
Post 19 Aug 2008, 12:11
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.