hugi compo #29- random mazes - how reduce size of this
in [ASM]
|
From: io_x on 2 Oct 2009 05:36 http://www.frontiernet.net/~fys/hugi/hcompo.htm This for other information In few words the hugi size competition #29 is about to write a .com program, the few bytes is possible, that return in the dos screen pseudo random mazes. The generated mazes are of the kind +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ ? | | | | | | | | | +--+--+--+ + + + + +--+ + + + +--+ +--+ + +--+ + + + + + + | | | | | | | | | | | | | | | | | | | + + + + + + +--+ +--+--+--+ +--+ +--+ +--+ + + + +--+--+ +--+ | | | | | | | | | | | | | | | | +--+--+ +--+--+--+ +--+ + + +--+ + + +--+ +--+--+ + + + +--+ + | | | | | | | | | | | | + +--+--+ +--+--+--+ +--+ + + +--+--+ + +--+--+--+--+ + +--+--+ + | | | | | | | | | | | | | + + + +--+ +--+ +--+--+--+ +--+--+--+--+--+--+--+ + + + + +--+ + | | | | | | | | | | | | | + + +--+ + + +--+ + + + +--+--+--+--+--+--+--+--+--+--+--+--+ +--+ | | | | | | | | | | | | + +--+ +--+--+ +--+ + + + +--+ + +--+ +--+ + +--+ +--+ + + + | | | | | | | | | | | | | | | | +--+ +--+ +--+--+ +--+--+--+--+ + +--+--+--+ +--+--+--+ + + +--+ + | | | | | | | | | | | | | + +--+ +--+ + +--+--+--+ +--+ + + +--+ + +--+ + + + +--+ + + | | | | | | | | ? +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ so 25x10 cells mazes, where each line begin with a wall or a + end with \r\n. The enter of maze should be the char 02h the exit should be the char 07fh. (that here are print with a '?') Each cell of maze has to be connected from one other cell with only one path (so there is always a path that goes from enter of maze to exit of maze; and there are not part in the maze closed [that can not be visit]) Then the programme has to deal with one input number where the allowed values goes from 0 to 100 and it has to deal with no argument at all too. If for example the name of .com file name is "entry" than entry entry 0 have to result in the print in the dos box the same 25x10 cells pseudo random maze the same for entry 88 entry 88 the same maze The program has to print in the screen using the Dos routines. This is my 182 bytes entry, but there are people say enought 135bytes and some other 96bytes How i can reduce its size? Than i not understand why for maze to much big the program not give the correct result. Thank you --------------------------- ;com file ;nasmw -o m.com m.asm ;; ; Ho applicato il seguente metodo ricorsivo: ; 1) Prima si costruisce una griglia dentro un rettangolo ; in cui tutte le caselle della suddivisione sono marcate ; non visitate ['N'], ; mentre il bordo della griglia e' marcato: visitato. ; 2) Si sceglie una casella di detto rettangolo da cui partire ; ; 3) Si marca tale casella con 'visitata' ; 4) Se tale casella non ha una casella confinante marcata non visitata ; Se lo stack e' vuoto ; esci ; altrimenti ; pop dallo stack la posizione della precedente casella ; si rende tale casella la casella attuale ; goto 4 ; altrimenti ; scegliere casualmente una casella confinante non visitata ; si leva il muro tra tale casella confinante e la casella iniziale ; push nello stack la posizione della casella iniziale ; si rende tale casella confinante la casella attuale ; goto 3 ; ; Una casella e' la seguente scrittura ; +-- ; |XY ; quindi e' formata da 6 chars. ; N significa *non visitato*, se a posto di N ci sta un qualsiasi altro ; carattere significa visitato. ; +--+--+--+ ; | |1 | | ; +--+--+--+ ; | 3|NN|2 | ; +--+--+--+ ; | |0 | | ; +--+--+--+ ; Per levare il muro da: ; W muro 1 W*i-162/2=" " ; B muro 2 B*i+2=' ' ; W muro 0 W*i+162/2=" " ; B muro 3 B*i-1=' ' ; L == lunghezza in caselle del rettangolo del labirinto ; H == altezza in caselle del rettangolo del labirinto ; Discussione sui valori limite ; Per la *corretta* rappresentazione in un Box Dos ; L_Max=26 L_Min=1, H_Max=20 H_Min=1. ; Utilizzando "> programma > file.txt" ; ho provato i valori fino a (L_Max,H_Max)=(97,97) ottenendo ; un labirinto di 56 Kb nel file.txt ; da (L,H)=(98, 97) il programma non funziona; ; sospetto che cio' sia dovuto all'array "arr" in .bss ; vicino a o maggiore ai 64kb (0..0FFFFh oppure 0..65535) ; che non puo' essere gestito dal programma oppure ; non puo' essere gestito dalla routine DOS che stampa ; tale array nello schermo. ; per il corrente file "arr" ha size ; BytesMemory(L,H)=((L+1)*(H+2)*6) ; BytesMemory(98,97)=99*99*6=58806 non funziona ; mentre ; BytesMemory(97,97)=98*99*6=58212 funziona ; Sospetto che il programma funzioni per ogni L ed H ; tali che BytesMemory(L,H)<=58212 ; Infatti ; BytesMemory(10,850)=(11*852*6)=56232 e qui funziona ;; %define L 25 %define H 10 ;%define L 10 ;%define H 850 %define BytesMemory ((L+1)*(H+2)*6) %define H21 (2*H+1) %define sopra (L+1)*6 %define sopra2 (L+1)*3 %define LineareMax 3*((L-1)+2*(L+1)*H)+1 %define passi (LineareMax-sopra-1)/3 org 100h Start: pusha ; **************************** ; *** Prende il numero ; **************************** mov si, 080h xor ax, ax ; punta alla size riga comando cmp byte[si], 0 je .6 ; nessun argomento ritorna 0 ..2: inc si ; va all'inizio dell'array ..3: lodsb ; preleva il primo carattere cmp al, ' ' jbe .3 ; leva gli spazi iniziali ..4: sub al, '0' jl .5 ; finisce quando incontra uno spazio ; o un char minore di '0' aad 10 ; al=al+ah*10 and ah=0 mov ah, al lodsb jmp short .4 ..5: mov al, ah ; ritorna numeri del tipo al:ah=n:n ..6: mov [seed], ax ; inizializza il seed per rand ; ******************************************* ; *** Fa la griglia ; ******************************************* mov di, arr mov cx, BytesMemory mov al, 10 lea si, [di+sopra] rep stosb ; tutto 10 [visitato] qui cx=0 lea di, [si-sopra2] mov bx, H21 mov ax, "+-" mov dx, "|N" ; le caselle NN: non visitate ..7: mov cl, L ; altrimenti visitate ..8: stosw mov byte[di], ah inc di loop .8 stosb mov byte[di], 0Dh ; fa la linea inc di inc di xchg ax, dx dec bx jnz .7 ; passa alla linea successiva mov byte[di], '$' mov byte[di-sopra2-3], 07fh mov byte[si], 02h ; ritorna in si la casella iniziale ; ******************************************* ; *** Fa il labirinto ; ******************************************* ; parte dalla casella puntata da si inc si ; punta all'interno della casella, dove c'e' 'N' mov di, sp ; salva lo stack per l'uscita ..9: mov word[si], " " ; " " significa visitata ..9a: mov ax, [seed] mul word[val] ; rand() inc ax mov [seed], ax add al, ah ; valore casuale in al and ax, 03h ; al=0[sotto],1[alto],2[sinistra],3[destra] mov cx, 4 ; le caselle confinanti sono 4 ..9b: mov bx, ax add bx, ax mov bp, [conv+bx] ; in bp l'offset cmp byte[si+bp], 'N' ; si+bp punta alla casella confinante je .a ; vede se tale casella � visitata, se si' va in .a inc ax and al, 3 loop .9b ; va alla prossima casella ; ** caso le caselle sono tutte visitate cmp di, sp jbe .z ; se lo stack e' vuoto esci[ e'in casella iniziale] pop ax ; altrimenti prende la casella precedente add si, ax ; ax=-162,+3,+162,-3 passa alla casella precedente jmp short .9a ..a: ; ** caso vi � una casella non visitata mov bx, [muro+bx] ; si+bx punta al muro (oppure a un char precedente) mov word[si+bx], " " ; leva il muro di divisione [ed eventualemente una N] ; che verra' in ogni caso levata in .9 add si, bp neg bp ; neg bp poiche' trova la casella precedente push bp jmp short .9 ; quando fa il pop e ritrova la strada ..z: ; usa la casella iniziale in si e la ritorna ; ****************************** ; *** Stampa sullo schermo ; ****************************** lea dx, [si-sopra2-1] ; usa si per stampare l'array mov ah, 09h int 21h popa ret align 2 val dw 32581 ; 0 1 2 3 conv dw sopra, -sopra, 3, -3 muro dw sopra2, -sopra2, 2, -1 Section .bss seed resw 1 arr resb BytesMemory fine resb 512 ; for to be sure -----------------------
From: Rod Pemberton on 2 Oct 2009 06:20 "io_x" <a(a)b.c.invalid> wrote in message news:4ac5c7f6$0$1106$4fafbaef(a)reader4.news.tin.it... > http://www.frontiernet.net/~fys/hugi/hcompo.htm > > This is my 182 bytes entry, but there are people say enought 135bytes > and some other 96bytes > Who's at 96? I've got 102 so far but no "ConFrom" in example.asm which could be +50, +80, +120, or easily more... > How i can reduce its size? Hey, I can't give specifics, since I'm trying to compete... But, you might look at: 1) hidden features of opcodes, like aaa, aad, aam 2) single byte opcodes, like lodsb, stosb, cbw, cdq, inc, dec, xchg Rod Pemberton
From: Esra Sdrawkcab on 2 Oct 2009 14:38 On Fri, 02 Oct 2009 10:36:20 +0100, io_x <a(a)b.c.invalid> wrote: > http://www.frontiernet.net/~fys/hugi/hcompo.htm > This for other information > > This is my 182 bytes entry, but there are people say enought 135bytes > and some other 96bytes > No, the current leader is 134 bytes. 96 seems *very* ambitious! > How i can reduce its size? > Than i not understand why for maze to much big the program not give > the correct result. You don't set the initial cell using the random number generator. Thanks for the code; I'm going to see what can be shortened, but it needs to get bigger first to add the RNG to locate the initial cell. My attempt at a program was also a big display array with another one of steps to next cell and wall. But it was too large. -- Nuns! Reverse!
From: io_x on 3 Oct 2009 03:13 "Esra Sdrawkcab" <admin(a)127.0.0.1> ha scritto nel messaggio news:op.u06rdzmrhswpfo(a)dell3100... > On Fri, 02 Oct 2009 10:36:20 +0100, io_x <a(a)b.c.invalid> wrote: > >> http://www.frontiernet.net/~fys/hugi/hcompo.htm >> This for other information > >> >> This is my 182 bytes entry, but there are people say enought 135bytes >> and some other 96bytes >> > No, the current leader is 134 bytes. 96 seems *very* ambitious! > >> How i can reduce its size? >> Than i not understand why for maze to much big the program not give >> the correct result. > > You don't set the initial cell using the random number generator. why i have to set the initial cell? > Thanks for the code; I'm going to see what can be shortened, but it needs to > get bigger first to add the RNG to locate the initial cell. yes all you is allow to use it in competition too > My attempt at a program was also a big display array with another one of > steps to next cell and wall. > But it was too large. > > > > -- > Nuns! Reverse!
From: io_x on 3 Oct 2009 03:23
"Esra Sdrawkcab" <admin(a)127.0.0.1> ha scritto nel messaggio news:op.u06rdzmrhswpfo(a)dell3100... > On Fri, 02 Oct 2009 10:36:20 +0100, io_x <a(a)b.c.invalid> wrote: > You don't set the initial cell using the random number generator. why have i to set the initial cell *random*? i choose the first one of the maze |