flat assembler
Message board for the users of flat assembler.

 Index > Main > Create random patterns
Author
Picnic

Joined: 05 May 2007
Posts: 1288
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.
17 Aug 2008, 08:23
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.
17 Aug 2008, 11:45

Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
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()

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
```

Its definitely not what you want, but its a start. I got the idea from Sudoku, where this is a perfect application.
17 Aug 2008, 11:46
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.
17 Aug 2008, 11:49
Picnic

Joined: 05 May 2007
Posts: 1288
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.
17 Aug 2008, 15:38

Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
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()
;#######################################################
;# 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

; Many codes later
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 http://www.agner.org/optimize/
17 Aug 2008, 15:57
Picnic

Joined: 05 May 2007
Posts: 1288
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.
17 Aug 2008, 20:24

Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
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?
18 Aug 2008, 06:14
Picnic

Joined: 05 May 2007
Posts: 1288
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
18 Aug 2008, 12:34

Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Oooh 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

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

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

;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...
18 Aug 2008, 14:51
Picnic

Joined: 05 May 2007
Posts: 1288
Picnic
Neat implementation Madis731 and small code.
Muchos gracias
19 Aug 2008, 12:11
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum