flat assembler
Message board for the users of flat assembler.
Index
> Main > Create random patterns 
Author 

Borsuc 17 Aug 2008, 11:45
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..n1 (n being the number of positions). It is simple to generate a pseudorandom 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 multidimensional array). The first part determines the current position of the number. The structure is simply: Code: cells[4] 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} // topleft position (the free horizontal/vertical cells FROM it) {0,2,4,7} // topmiddle position (1) {0,1,5,8} // topright position (2) {0,4,5,6} // middleleft position (3) {1,3,5,7} // middle position (4) {2,3,4,8} // middleright position (5) {0,3,7,8} // bottomleft position (6) {1,4,6,8} // bottommiddle position (7) {2,5,6,7} // bottomright position (8) } The problem with the above is that I believe it's not the best method at all. 

17 Aug 2008, 11:45 

Madis731 17 Aug 2008, 11:46
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 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 17 Aug 2008, 11:49
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 17 Aug 2008, 15:38
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 

Madis731 17 Aug 2008, 15:57
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 ; 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


17 Aug 2008, 15:57 

Picnic 17 Aug 2008, 20:24
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 

Madis731 18 Aug 2008, 06:14
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 18 Aug 2008, 12:34
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 

Madis731 18 Aug 2008, 14:51
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 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 ;Many lines of gamecode 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) lookup 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 19 Aug 2008, 12:11
Neat implementation Madis731 and small code.
Muchos gracias 

19 Aug 2008, 12:11 

< Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992024, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.