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..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] 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) } 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
|
|||||||||||||||||||||
|
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 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:
|