Assembly x86 - Programmazione
Andrea "DoC" Piola - PALib - Home page! - e-mail
Il primo programma: Raycasting
Vediamo ora l'esempio di una mappa formata da sole 16 caselle per lato, la casella nera è il personaggio (noi), le celle più scure sono le pareti, l'origine degli assi (X, Y) la consideriamo in basso a sinistra.
| F | ||||||||||||||||
| . | ||||||||||||||||
| . | ||||||||||||||||
| . | ||||||||||||||||
| . | ||||||||||||||||
| . | ||||||||||||||||
| . | ||||||||||||||||
| . | ||||||||||||||||
| . | ||||||||||||||||
| . | ||||||||||||||||
| . | ||||||||||||||||
| Yp | ||||||||||||||||
| . | ||||||||||||||||
| . | ||||||||||||||||
| 0 | ||||||||||||||||
| 0 | . | . | . | . | . | Xp | . | . | . | . | . | . | . | F | ||
Dette Ls e As rispettivamente la larghezza e l'altezza dello schermo abbiamo:
Il campo di visuale (Field of Vision) in genere, per questo tipo di motori, viene considerato pari ad un angolo compreso tra i 60° e i 72° (±30° o ±36° rispetto alla direzione di osservazione), questi sono probabilmente i valori che forniscono una migliore rappresentazione a video del mondo 3D; siccome noi non faremo uso direttamente di questo angolo dovremo impostare in modo appropriato la distanza dello schermo (Ds).-Ls/2 <= Xs <= +Ls/2 -As/2 <= Ys <= +As/2
Ora possiamo emettere i famosi raggi (r) e ne serviranno tanti quante sono le colonne dello schermo, per ogni raggio dobbiamo calcolare l'angolo θ:
A questo punto ci serve conoscere le coordinate delle prime intersezioni di questo raggio con i bordi verticale e orizzontale della cella in cui è presente il personaggio:θ = arctg (Xs/Ds)
Anche se le coordinate di intersezione le ho chiamate in entrambi i casi con Xi e Yi, sono da considerarsi due coppie separate. Una volta calcolate le prime intersezioni inizia il ciclo principale del motore di raycasting:Prima intersezione Y (bordo verticale): Se cos(φ - θ) > 0 -> avviene sul lato a destra di P Xi = (Xp - Xp%Lc) + Lc (colonna successiva) Se cos(φ - θ) < 0 -> avviene sul lato a sinistra di P Xi = (Xp - Xp%Lc) - 1 (Colonna precedente) Yi = (Xi - Xp)·tg(φ - θ) + Yp Prima intersezione X (bordo orizzontale): Se sin(φ - θ) > 0 -> avviene sul lato superiore a P Yi = (Yp - Yp%Ac) + Ac (riga superiore) Se sin(φ - θ) < 0 -> avviene sul lato inferiore a P Yi = (Yp - Yp%Ac) - 1 (Riga inferiore) Xi = (Yi - Yp)·cotg(φ - θ) + Xp % indica il modulo, cioè il resto della divisione fra i due operandi
Note Xc e Yc si controlla nella mappa se in quella cella è presente un muro (in genere valore <> 0). Se l'abbiamo trovato possiamo uscire dal ciclo, altrimenti calcoliamo la prossima intersezione:Xc = Xi / Lc se Lc=2n -> Xc = Xi >> n Yc = Yi / Ac se Ac=2m -> Yc = Yi >> m
Ora per evitare di controllare ad ogni intersezione se siamo all'interno della mappa è utile creare un muro che la cinga completamente (come nell'esempio); in questo modo, qualunque sia la direzione di osservazione, sicuramente troveremo una parete che ci permetterà di uscire dal ciclo senza dover effettuare confronti, con conseguente risparmio di tempo.Se l'intersezione che stiamo controllando è Y (bordo verticale): Xi ±= Lc Yi ±= Ac·tg(φ - θ) Se l'intersezione che stiamo controllando è X (bordo orizzontale): Xi ±= Lc·cotg(φ - θ) Yi ±= Ac ± = concorde con il segno di cos(φ - θ) per le Xi concorde con il segno di sin(φ - θ) per le Yi Ritorniamo al punto 1
Io userò il primo metodo, se volete usare il secondo dovete fare attenzione a quando il cos e il sin tendono a 0.Distanza = √((Xi - Xp)2+(Yi - Yp)2) Teorema di Pitagora Oppure con la trigonometria: Distanza = (Xi - Xp)/cos(φ - θ) Distanza = (Yi - Yp)/sin(φ - θ)
Nota la distanza ci rimangono gli ultimi calcoli:
Ora che abbiamo i dati della texture, in quale punto dello schermo dobbiamo disegnarla? L'ascissa Xs già la conosciamo perchè e il dato da cui siamo partiti per tracciare il raggio r, mentre Ys dobbiamo calcolarla:Distanza = Distanza·cos(θ) Il cos(θ) serve per correggere la distorsione visiva. Usando la similitudine dei triangoli: Altezza colonna = Ds·Am / Distanza Dove Am = Altezza muro Colonna Texture = Xi & (Lc - 1)
L'ultimo passaggio consiste nel trasformare (Xs, Ys) nelle coordinate vere dello schermo; sapendo che queste ultime hanno l'origine in alto a sinistra e sono crescenti rispettivamente verso destra e verso il basso:Per il punto inferiore della colonna: Ysbottom = -Ds·Ap/Distanza Dove Ap = Altezza del punto di osservazione Per il punto superiore: Ystop = Ysbottom+ Am - 1
Dove SCenterX e SCenterY rappresentano le coordinate del centro dello schermo, ad esempio se utilizziamo la risoluzione di 320x200 saranno (160, 100).X = Xs + SCenterX Y = -Ys + SCenterY
Per il momento chiudiamo la parentesi teorica e iniziamo a scrivere la prima versione del programma, scegliamo per questo la struttura dei file COM. Avendo scelto di utilizzare le istruzioni del coprocessore dobbiamo segnalarlo anche al compilatore aggiungendo all'inizio del listato la direttiva .387; non è sufficiente indicare .287 perchè in questo coprocessore le funzioni trigonometriche di seno e coseno non sono implementate. Inoltre se compilate questo sorgente con il TASM dovrete inserire .386 e .387 dopo la direttiva .MODEL TINY.
In quest'ultimo caso otterrete un file con dimensioni leggermente superiori perchè i salti condizionati a 16 bits possono avere una distanza di arrivo compresa tra -128 e +127 bytes dalla posizione del salto stesso. Siccome nel listato ci sono alcuni salti condizionati che superano questi limiti, con MASM e la direttiva .286 verranno automaticamente corretti durante la fase di compilazione, mentre con il TASM non potendo usare la direttiva .286 (che comunque fornirebbe errore) tutti i salti Jcc vengono considerati near tra -32768 e +32767 con conseguente spreco di byte (se sono compresi tra -128 e +127 vengono aggiunte due istruzioni NOP per allineamento).
Un'altra breve parentesi, nel primo tutorial avevo scritto che i numeri floating point bisognava dichiararli con REAL4, REAL8 o REAL10 ma mi accorgo in questo momento che queste sono direttive esclusive del MASM (purtroppo non avendo mai usato prima d'ora il TASM mi era sfuggito), quindi dovremo più semplicemente usare DD, DQ o DT seguiti dal numero floating point.
La prima cosa da fare è inizializzare le costanti e i dati che utilizzeremo:Corrisponde al file Ray01.ASM (Nella versione scaricabile del tutorial). .MODEL TINY .286 ; Con TASM .386 .387 .CODE .STARTUP ; Qui mettiamo il codice del motore di Raycasting ; Dopo inseriamo le procedure viste nel capitolo precedente ; (Naturalmente solo se vengono usate) ; Infine inseriamo i dati che ci servono ; (Possiamo anche usare la direttiva .DATA, in questo caso ; la inseriremo prima di .CODE) ; la direttiva .EXIT non la usiamo -> inseriremo RET END
Adesso passiamo al programma principale, questo si deve occupare innanzitutto di allocare la memoria necessaria per l'immagine e i dati; poi di caricare l'immagine ed attivare la modalità grafica (tutte cose che abbiamo visto nel capitolo precedente):.DATA ; Le prime costanti riguardano le celle (Considero Lc=Ac) Lc = 64 ; Larghezza delle celle LcShift = 6 ; Bits di scorrimento Hm = 64 ; Altezza muro Nc = 16 ; Numero di colonne NcShift = 4 ; Numero di colonne della mappa 2^n ; Le prossime costanti definiscono le dimensione della finestra STop = 0 ; Limite superiore finestra video SBottom = 199 ; Limite inferiore finestra video SLeft = 0 ; Limite sinistro finestra video SRight = 319 ; Limite destro finestra video SCenterX = (SLeft+SRight)/2 ; Ascissa centro finestra video SCenterY = (STop+SBottom)/2 ; Ordinata centro finestra video Ls = (SRight-SLeft)+1 ; Numero totale di colonne ; IncDir rappresenta la dimensione dello spostamento avanti/indietro (in unità) ; Limite è la distanza minima (in unità) dalle pareti (potenza di 2) ; L'unità equivale a 1/Lc di Lc IncDir = 4 ; Incremento direzione Limite = 16 ; Distanza minima dalle pareti ; Ora definiamo le variabili Temp DW 0 ; Variabile temporanea Dist DW 220 ; Distanza dello schermo Xp DW 6*Lc+Lc/2 ; Ascissa personaggio Yp DW 4*Lc+Lc/2 ; Ordinata personaggio Ap DW Hm/2 ; Altezza punto di visuale Am DW Hm ; Altezza dei muri Hc DW 0 ; Altezza colonna Xi_X DW 0 ; Ascissa intersezione X (bordo orizzontale) Yi_X DW 0 ; Ordinata intersezione X (bordo orizzontale) Xi_Y DW 0 ; Ascissa intersezione Y (bordo verticale) Yi_Y DW 0 ; Ordinata intersezione Y (bordo verticale) Xs DW -SCenterX ; Ascissa schermo Ys DW -SCenterY ; Ordinata schermo Angolo DD 30.0 ; Angolo di visuale IncAng DD 2.0 ; Incremento dell'angolo Coseno DW 0 ; Coseno dell'angolo di visuale Seno DW 0 ; Seno dell'angolo di visuale SegBuf DW 0 ; Segment buffer SegImm DW 0 ; Segment immagine GrdRad DQ 0.017453292519943295769 ; pi/180° ; I prossimi sono gli offset delle singole texture ; L'immagine è formata da 4x4 texture di 64 pixels di lato Off DW 0, 64, 128, 192 DW 64*256+0, 64*256+64, 64*256+128, 64*256+192 DW 128*256+0, 128*256+64, 128*256+128, 128*256+192 DW 192*256+0, 192*256+64, 192*256+128, 192*256+192 ; Infine viene la mappa (le righe sono in ordine inverso rispetto a Y) ; I numeri rapresentano la texture (escluso lo 0 che viene considerato ; come cella vuota e quindi la texture 0 non può rappresentare un muro) Mappa DB 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6 DB 6, 0, 0, 0, 0,10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6 DB 6, 0, 0, 0,10,10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6 DB 6, 0, 0,10,10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6 DB 6, 0,10,10, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 4, 6 DB 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 4, 0, 0, 6 DB 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 6 DB 6, 7, 7, 7, 7, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6 DB 6, 0, 0, 0, 7, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 6 DB 6, 0, 0, 0, 7, 0, 0, 0, 0, 0, 4, 4, 4, 0, 0, 6 DB 6, 0, 0, 0, 7, 7, 0, 0, 0, 0, 0, 0, 4, 4, 4, 6 DB 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6 DB 6, 0, 0, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0, 9, 9, 6 DB 6, 0, 0, 9, 0, 0, 0, 9, 0, 9, 9, 9, 9, 9, 0, 6 DB 6, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6 DB 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6
Fatte tutte le impostazioni possiamo iniziare il ciclo principale che si occuperà di disegnare i muri e gestire la pressione dei tasti (spostamento e altezza):.CODE .STARTUP ; Alloca memoria per immagine e dati MOV AH,4AH ; Funzione 4AH - Cambia dimensione blocco MOV BX,1000H ; 64 Kb INT 21H ; Interrupt MS-Kernel MOV AH,48H ; Funzione 48H - Alloca memoria MOV BX,1000H ; 64 Kb INT 21H ; Interrupt MS-Kernel JC @M2 ; Esce se c'e' un errore MOV ES,AX ; Memorizza segment immagine MOV SegImm,AX ; Memorizza segment immagine MOV AH,48H ; Funzione 48H - Alloca memoria MOV BX,1000H ; 64 Kb INT 21H ; Interrupt MS-Kernel MOV SI,AX ; Memorizza segment palette MOV SegBuf,AX ; Memorizza segment buffer JC @M1 ; Esce se c'e' un errore ; Il buffer ci serve come schermo virtuale (è più veloce) ; Carica immagine e palette MOV DX,OFFSET Nome ; Indirizzo nome file CALL Carica ; Carica immagine JNC @M3 ; Salta se non c'e' un errore ; Se c'è un errore o è finito il programma elimina la memoria ed esce MOV ES,SegImm ; Carica Segment primo blocco MOV AH,49H ; Funzione 49H - Libera memoria INT 21H ; Interrupt MS-Kernel @M1: MOV ES,SegBuf ; Carica Segment secondo blocco MOV AH,49H ; Funzione 49H - Libera memoria INT 21H ; Interrupt MS-Kernel @M2: RET ; Fine programma ; I dati possono essere inseriti anche in mezzo al codice come in questo caso Nome DB "Muri.raw",0 ; Nome del file con le texture ; Attiva modalità grafica, nuova palette e l'handler della tastiera @M3: MOV AX,013H ; Funzione 0 (AH) e modo video 13 (AL) INT 10H ; Interrupt video XOR DX,DX ; Azzera Offset MOV ES,SI ; Copia Segment palette CALL Palette ; Imposta nuova palette CALL InitKbrd ; Inizializza tastiera CALL Direzione ; Calcola incrementi iniziali dello spostamento
Prima di proseguire voglio chiarire meglio come ho deciso di effettuare il controllo sulla distanza minima (che per mia scelta deve essere 2n), infatti quando il resto è minore della distanza minima bisognerebbe calcolare:; Ora comincia il ciclo principale @M4: MOV Xs,-SCenterX ; Inizializza Xs CALL RayCast ; Richiama procedura di RayCasting XOR AX,AX ; Azzera spostamento X XOR BX,BX ; Azzera spostamento Y XOR DI,DI ; Azzera DI ; Controlla pressione dei tasti F1-F2 (Altezza personaggio) @M5: CMP Buffer[59],0 ; Controlla pressione tasto F1 JE @M6 ; Se non è premuto salta INC Ap ; Incrementa altezza personaggio INC DI ; Posizione modificata CMP Ap,Hm ; Controlla se raggiunto soffitto JB @M6 ; Se no salta DEC Ap ; Decrementa altezza personaggio @M6: CMP Buffer[60],0 ; Controlla pressione tasto F2 JE @M7 ; Se non è premuto salta INC DI ; Posizione modificata DEC Ap ; Decrementa altezza personaggio JG @M7 ; Se > pavimento salta INC Ap ; Incrementa altezza personaggio ; Controlla pressione dei tasti cursore (Spostamento) @M7: CMP Buffer[72],0 ; Controlla pressione cursore Su JE @M8 ; Se non è premuto salta MOV AX,Coseno ; Incremento X MOV BX,Seno ; Incremento Y INC DI ; Posizione modificata @M8: CMP Buffer[80],0 ; Controlla pressione cursore Giù JE @M9 ; Se non è premuto salta MOV AX,Coseno ; Incremento X MOV BX,Seno ; Incremento Y NEG AX ; Cambia segno NEG BX ; Cambia segno INC DI ; Posizione modificata @M9: CMP Buffer[75],0 ; Controlla pressione cursore Sinistra JE @M10 ; Se non è premuto salta FLD IncAng ; Carica incremento angolo FADD Angolo ; Aggiorna l'angolo di visuale FSTP Angolo ; Memorizza nuovo angolo INC DI ; Posizione modificata CALL Direzione ; Calcola nuovi incrementi @M10: CMP Buffer[77],0 ; Controlla pressione cursore Destra JE @M11 ; Se non è premuto salta FLD Angolo ; Carica angolo di visuale FSUB IncAng ; Sottrae incremento angolo FSTP Angolo ; Memorizza nuovo angolo INC DI ; Posizione modificata CALL Direzione ; Calcola nuovi incrementi ; Controlla pressione tasto ESC @M11: CMP Buffer[1],0 ; Controlla pressione tasto ESC JNE @M13 ; Se è premuto esce dal programma OR DI,DI ; Posizione e/o orientamento modificate? JZ @M5 ; Se no continua controllo tasti ; Controlla se lo spostamento è valido (non deve esserci un muro) ADD AX,Xp ; Calcola nuova ascissa Xp del personaggio ADD BX,Yp ; Calcola nuova ordinata Yp del personaggio MOV SI,AX ; Copia nuova Xp MOV DI,BX ; Copia nuova Yp SHR SI,LcShift ; Calcola Xc SHR DI,LcShift ; Calcola Yc SHL DI,NcShift ; Moltiplica per numero di colonne ADD SI,DI ; Calcola offset nella mappa CMP Mappa[SI],0 ; Controlla presenza muro JNE @M4 ; Se c'è un muro salta MOV Xp,AX ; Memorizza nuova Xp MOV Yp,BX ; Memorizza nuova Yp ; Ora controlla se il personaggio si trova ad una distanza minima dalla parete ; L'uso di OR e di AND non è chiarissimo ma mi è sembrato il metodo migliore @M12: AND AX,(Lc-1) ; Resto di Xp / Lc AND BX,(Lc-1) ; Resto di Xp / Lc CMP AX,Limite ; Controlla se > distanza minima JAE @M14 ; Se si salta CMP Mappa[SI-1],0 ; Controlla presenza parete JE @M15 ; Se no salta OR Xp,Limite-1 ; Assicura la distanza minima JMP @M15 ; Salta @M14: CMP AX,Lc-Limite ; Controlla se > distanza minima JBE @M15 ; Se si salta CMP Mappa[SI+1],0 ; Controlla presenza parete JE @M15 ; Se no salta AND Xp,NOT (Limite-1) ; Assicura la distanza minima @M15: CMP BX,Limite ; Controlla se > distanza minima JAE @M16 ; Se si salta CMP Mappa[SI-16],0 ; Controlla presenza parete JE @M4 ; Se no salta OR Yp,Limite-1 ; Assicura la distanza minima JMP @M4 ; Salta @M16: CMP BX,Lc-Limite ; Controlla se > distanza minima JBE @M4 ; Se si salta CMP Mappa[SI+16],0 ; Controlla presenza parete JE @M4 ; Se AND Yp,NOT (Limite-1) ; Assicura la distanza minima JMP @M4 ; Ridisegna mappa ; Ripristina vecchio handler della tastiera, la modalità testo ed esce dal programma @M13: CALL ResetKbrd ; Ripristina vecchia tastiera MOV AX,03H ; Funzione 0 (AH) e modo video 3 (AL) INT 10H ; Interrupt video JMP @M1 ; Fine programma
A questo punto scriviamo la procedura Direzione, che verrà richiamata ogni volta che viene modificato l'angolo di osservazione:
Eccoci giunti alla procedura di Raycasting e come potrete vedere fa uso quasi esclusivamente di calcoli con numeri floating point; ho scelto questa strada anche se è la peggiore (come prestazioni) in modo da farvi vedere le istruzioni del coprocessore, infatti nella maggioranza dei manuali sull'Assembly questo argomento è appena accennato o addirittura è assente; se poi volete migliorare questo programma vi consiglio di utilizzare delle tabelle in cui inserire i valori delle funzioni trigonometriche e di passare ai numeri in virgola fissa (Numeri floating point trasformati in interi moltiplicandoli per una potenza di 2).Direzione: FLD Angolo ; Carica angolo di osservazione FMUL GrdRad ; Trasforma in radianti FSINCOS ; Calcola seno e coseno MOV Temp,IncDir ; Copia dimensione spostamento FILD Temp ; Carica dimensione spostamento in ST FMUL ST(1),ST ; IncDir*cos FMULP ST(2),ST ; IncDir*sin FISTP Coseno ; Memorizza incremento X FISTP Seno ; Memorizza incremento Y RET ; Fine procedura
L'ultima cosa da fare è aggiungere le procedure per caricare l'immagine e gestire la tastiera che abbiamo visto nel capitolo precedente, salvare il file, compilarlo e verificare quanto abbiamo fatto.RayCast: ; Per prima cosa azzeriamo il buffer XOR AX,AX ; Indice colore MOV ES,SegBuf ; Segment buffer XOR DI,DI ; Azzera offset schermo grafico MOV CX,320*200/2 ; Numero totale di pixels / 2 REP STOSW ; Riempie lo schermo (Scrive due pixels per volta) MOV BP,Ls ; Carica larghezza schermo MOV ES,SegImm ; Carica segment immagine ; Calcoliamo θ, sin(φ-θ), cos(φ-θ), tan(φ-θ) e cotan(φ-θ) @R1: MOV Am,Hm ; Altezza muro FILD Xs ; Xs FILD Dist ; Ds Xs FPATAN ; θ FLD Angolo ; φ° θ FMUL GrdRad ; φ θ FSUB ST,ST(1) ; φ-θ θ FSINCOS ; cos sin θ FLD ST ; cos cos sin θ FDIV ST,ST(2) ; Cotg cos sin θ FLD ST(2) ; sin Cotg cos sin θ FDIV ST,ST(2) ; tg Cotg cos sin θ ; Cerchiamo la prima intersezione Y (Bordo verticale) MOV DI,-Lc ; Carica larghezza cella (negativa) MOV SI,-Lc ; Carica altezza cella (negativa) FLD ST(2) ; cos tg Cotg cos sin θ MOV BX,Xp ; Carica X personaggio FTST ; Controlla se coseno >= 0 MOV CX,BX ; Copia Xp AND BX,(Lc-1) ; Calcola Xp % Lc FSTSW AX ; Memorizza Status Word SUB CX,BX ; Calcola Xi SAHF ; Copia Status Word nei Flags FSTP ST ; tg Cotg cos sin θ JB @R2 ; Se coseno < 0 salta ADD CX,Lc+1 ; Colonna di sinistra NEG DI ; Cambia segno a incremnto Xi @R2: DEC CX ; Decrementa Xi MOV Xi_Y,CX ; Memorizza Xi parete Y FILD Xi_Y ; Xi tg Cotg cos sin θ FISUB Xp ; Xi-Xp tg Cotg cos sin θ FMUL ST,ST(1) ; (Xi-Xp)*tg tg Cotg cos sin θ FIADD Yp ; (Xi-Xp)*tg+Yp tg Cotg cos sin θ FIST Yi_Y ; Memorizza risultato (intero) ; Cerchiamo la prima intersezione X (Bordo orizzontale) FLD ST(4) ; sin Yi_Y tg Cotg cos sin θ MOV BX,Yp ; Carica Y personaggio FTST ; Controlla se seno >= 0 MOV CX,BX ; Copia Yp AND BX,(Lc-1) ; Calcola Yp % Lc FSTSW AX ; Memorizza Status Word SUB CX,BX ; Calcola Xi SAHF ; Copia Status Word nei Flags FSTP ST ; Yi_Y tg Cotg cos sin θ JB @R3 ; Se seno < 0 salta ADD CX,Lc+1 ; Riga superiore NEG SI ; Cambia segno a incremento Yi @R3: DEC CX ; Decrementa Yi MOV Yi_X,CX ; Memorizza Yi parete X FILD Yi_X ; Yi Yi_Y tg Cotg cos sin θ FISUB Yp ; Yi-Yp Yi_Y tg Cotg cos sin θ FMUL ST,ST(3) ; (Yi-Yp)*ctg Yi_Y tg Cotg cos sin θ FIADD Xp ; (Yi-Yp)*ctg+Xp Yi_Y tg Cotg cos sin θ FIST Xi_X ; Memorizza risultato (intero) ; Calcoliamo gli incrementi per le intersezioni successive MOV Temp,DI ; Copia ±Lc FILD Temp ; ±Lc Xi_X Yi_Y tg Cotg cos sin θ FMULP ST(3),ST ; Xi_X Yi_Y ±Lc*tg Cotg cos sin θ MOV Temp,SI ; Copia ±Lc FILD Temp ; ±Ac Xi_X Yi_Y ±Lc*tg Cotg cos sin θ FMULP ST(4),ST ; Xi_X Yi_Y ±Lc*tg ±Ac*ctg cos sin θ ; Cerchiamo la prima casella contenente un muro nella direzione (φ+θ) @R4: OR DI,DI ; Controlla segno incremento (come il coseno) JNS @R5 ; Se positivo salta FICOM Xi_Y ; Confronta Xi pareti X e Y FSTSW AX ; Memorizza Status Word SAHF ; Copia Status Word nei Flags JA @R7 ; Se Xi_X > Xi_Y salta JMP @R6 ; Salta @R5: FICOM Xi_Y ; Confronta Xi pareti X e Y FSTSW AX ; Memorizza Status Word SAHF ; Copia Status Word nei Flags JB @R7 ; Se Xi_X < Xi_Y salta @R6: MOV AX,Xi_Y ; Carica Xi parete Y MOV BX,Yi_Y ; Carica Yi parete Y ADD Xi_Y,DI ; Prossima Xi FXCH ; Yi_Y Xi_X ±Lc*tg ±Ac*ctg cos sin θ FADD ST,ST(2) ; Yi_Y±Lc*tg Xi_X ±Lc*tg ±Ac*ctg cos sin θ FIST Yi_Y ; Memorizza prossima Yi FXCH ; Xi_X Yi_Y' ±Lc*tg ±Ac*ctg cos sin θ MOV DX,BX ; Memorizza Yi JMP @R8 ; Salta @R7: MOV AX,Xi_X ; Carica Xi parete X MOV BX,Yi_X ; Carica Yi parete X ADD Yi_X,SI ; Prossima Yi FADD ST,ST(3) ; Xi_X±Ac*ctg Yi_Y' ±Lc*tg ±Ac*ctg cos sin θ FIST Xi_X ; Memorizza prossima Xi MOV DX,AX ; Memorizza Xi @R8: MOV CX,BX ; Copia Yi MOV Temp,AX ; Memorizza Xi SHR BX,LcShift ; Calcola Yc SHR AX,LcShift ; Calcola Xc SHL BX,NcShift ; Moltiplica per numero di colonne ADD BX,AX ; Calcola offset nella mappa CMP Mappa[BX],0 ; Controlla se presente muro JE @R4 ; Se no prossima intersezione ; Trovato muro eliminiamo i registri floating point che non ci servono più FSTP ST ; Yi_Y' ±Lc*tg ±Ac*ctg cos sin θ FSTP ST ; ±Lc*tg ±Ac*ctg cos sin θ FSTP ST ; ±Ac*ctg cos sin θ FSTP ST ; cos sin θ FSTP ST ; sin θ FSTP ST ; θ ; Ora calcoliamo la distanza del punto di intersezione dal personaggio FILD Temp ; Xi θ MOV Temp,CX ; Copia Yi FISUB Xp ; Xi-Xp θ FMUL ST,ST ; (Xi-Xp)^2 θ FILD Temp ; Yi (Xi-Xp)^2 θ FISUB Yp ; Yi-Yp (Xi-Xp)^2 θ FMUL ST,ST ; (Yi-Yp)^2 (Xi-Xp)^2 θ FADDP ST(1),ST ; (Xi-Xp)^2+(Yi-Yp)^2 θ FSQRT ; Distanza θ FXCH ; θ Distanza FCOS ; Cos(θ) Distanza FMULP ST(1),ST ; Distanza·Cos(θ) ; Calcola colonna texture, altezza colonna e YsBottom AND DX,(Lc-1) ; Calcola colonna texture FILD Dist ; Ds Distanza·Cos(θ) FDIVRP ST(1),ST ; Ds/(Distanza·Cos(θ)) FLD ST ; Ds/(Distanza·Cos(θ)) Ds/(Distanza·Cos(θ)) FIMUL Am ; Am*Ds/(Distanza·Cos(θ)) Ds/(Distanza·Cos(θ)) FISTP Hc ; Ds/(Distanza·Cos(θ)) FIMUL Ap ; Ap*Ds/(Distanza·Cos(θ)) FISTP Temp ; Memorizza Ys inferiore (Ora il coprocessore è vuoto) ADD Temp,SCenterY ; Somma ordinata centro dello schermo ; Calcoliamo l'offset iniziale della texture e YsTop MOV BL,Mappa[BX] ; Carica tipo di texture XOR BH,BH ; Azzera BH ADD BX,BX ; Moltiplica per 2 MOV DI,Off[BX] ; Carica offset texture ADD DI,DX ; Somma colonna texture MOV AX,Temp ; Carica Ys inferiore MOV CX,Hc ; Carica altezza colonna MOV BX,AX ; Copia Ys inferiore SUB AX,CX ; Sottrae altezza colonna INC AX ; Ys superiore MOV SI,Am ; Carica altezza muro ; Controlliamo se la colonna esce dalla finestra video ; In caso affermativo calcoliamo le nuove dimensioni della colonna ; e il nuovo offset iniziale della texture CMP AX,STop ; Controlla se < limite superiore JGE @R9 ; Se no salta SUB AX,STop ; Calcola differenza ADD CX,AX ; Nuova altezza colonna MOV Temp,AX ; Memorizza differenza FILD Am ; Am FIMUL Temp ; AX*Am FIDIV Hc ; AX*Am/Hc FISTP Temp ; Memorizza risultato MOV AX,Temp ; Carica AX*Am/Hc ADD SI,AX ; Nuova altezza del muro NEG AX ; Cambia segno SHL AX,8 ; Moltiplica per 256 ADD DI,AX ; Aggiorna offset texture MOV AX,STop ; Carica limite superiore @R9: CMP BX,SBottom ; Controlla se > limite inferiore JLE @R10 ; Se no salta SUB BX,SBottom ; Calcola differenza SUB CX,BX ; Nuova altezza colonna MOV Temp,BX ; Memorizza differenza FILD Am ; Am FIMUL Temp ; AX*Am FIDIV Hc ; AX*Am/Hc FISTP Temp ; Memorizza risultato SUB SI,Temp ; Nuova altezza muro ; Calcoliamo l'offset del primo punto della colonna (quello superiore) @R10: MOV Hc,CX ; Memorizza altezza colonna MOV BX,AX ; Copia Ys superiore SHL AX,8 ; Y * 256 SHL BX,6 ; Y * 64 MOV Am,SI ; Memorizza nuova altezza muro ADD AX,Xs ; Y * 256 + Xs ADD BX,SCenterX ; Y * 256 + X ADD BX,AX ; Y * 320 + X MOV DX,Am ; Carica altezza muro MOV DS,SegBuf ; Carica Segment buffer ; Finalmente! disegnamo la colonna MOV SI,CX ; Copia altezza colonna MOV AL,ES:[DI] ; Carica indice colore @R11: SUB CX,DX ; Errore -= Altezza muro JNS @R13 ; Se >= 0 salta @R12: ADD DI,256 ; Prossima riga texture ADD CX,SI ; Errore += Altezza colonna JS @R12 ; Se < 0 continua ciclo MOV AL,ES:[DI] ; Carica nuovo indice colore @R13: MOV [BX],AL ; Memorizza indice colore ADD BX,320 ; Prossima riga schermo DEC CS:Hc ; Decrementa altezza muro JG @R11 ; Disegna tutta la colonna ; Ripristiniamo il Segment DS e ripetiamo il ciclo Ls volte PUSH CS ; Memorizza CS nello stack POP DS ; Copia CS INC Xs ; Prossima colonna DEC BP ; Decrementa numero di colonne JG @R1 ; Disegna tutte le colonne ; Copia buffer nella memoria video MOV AX,0A000H ; Segment memoria video MOV DS,SegBuf ; Segment buffer MOV ES,AX ; Copia Segment memoria video XOR DI,DI ; Azzera offset destinazione XOR SI,SI ; Azzera offset sorgente MOV CX,320*200/2 ; Dimensione schermo / 2 REP MOVSW ; Copia buffer PUSH CS ; Memorizza CS nello stack POP DS ; Copia CS RET ; Fine procedura
oppure:MASM Ray01 LINK /t Ray01;
Una volta in esecuzione potete usare i cursori per muovervi nella mappa e i tasti F1/F2 per aumentare/diminuire l'altezza del personaggio.TASM Ray01 TLINK /t Ray01
Potete anche fare delle prove modificando i vari parametri:
Fatti gli esperimenti riprendiamo con la teoria e vediamo come disegnare il pavimento e il soffitto.
Per questo si possono seguire due vie, la prima consiste nel disegnare entrambi per righe verticali dello schermo, in modo tale che sfruttando la conoscenza di YsBottom e YsTop che ci siamo calcolati, vengano disegnati solo i punti effettivamente visibili. Questo però comporta l'uso di una tabella aggiuntiva (per non rallentare troppo l'esecuzione) in cui sono memorizzate le distanze. Il secondo metodo, che utilizzeremo noi, consiste nel disegnare il pavimento e il soffitto per righe orizzontali dello schermo (Ys = costante); questo metodo, se non vogliamo effettuare controlli per ogni pixel, comporta che vengano disegnati anche pixels non visibili che verranno coperti dai muri, però è quello che fornisce un algoritmo più semplice.
Per capire meglio le formule inserisco un semplice schema (e non ridete!):
La formula che ci serve è la stessa vista per calcolare Ys, solo che questa volta la nostra incognita è la Distanza:------------------------- Soffitto Schermo | | | - | Ds / \ --------------------| | --- --- | -- \ / ^ ^ | -- - Ys |-- /|\ v --| / | \ Ap --- -- / | \ -- / \ -- / \ -- / \ v ------------------------- --- Pavimento |< Distanza >|
Dove:Distanza = Ds·A/(|Ys|·cos(θ))
Il problema che si riscontra utilizzando il primo metodo (disegno per colonne) è proprio quello della divisione per Ys per ogni singolo punto.A = Ap Pavimento A = Am - Ap Soffitto
Una volta nota la Distanza ci troviamo X e Y:
Note X e Y troviamo la cella nella mappa e Xt, Yt della texture:X = Xp + Distanza·cos(φ-θ) Y = Yp + Distanza·sin(φ-θ)
A questo punto non ci rimane che leggere il tipo di texture, trovare il colore del punto Xt,Yt e infine disegnarlo sullo schermo alle coordinate:Xc = X >> LcShift Yc = Y >> LcShift Xt = X & (Lc - 1) Yt = Y & (Lc - 1)
Ripetiamo questi calcoli per tutte le colonne dello schermo e per tutte le righeX = Xs + SCenterX Y = -Ys + SCenterY
Ora vediamo come semplificare le formule:
A questo punto calcoliamo la differenza tra due valori di X e di Y:X = Xp + (Ds·A/|Ys|)·(cos(φ-θ)/cos(θ)) X = Xp + (Ds·A/|Ys|)·((cos(θ)·cos(φ)+sin(θ)·sin(φ))/cos(θ)) X = Xp + (Ds·A/|Ys|)·(cos(φ)+tan(θ)·sin(φ)) In maniera del tutto analoga: Y = Yp + (Ds·A/|Ys|)·(sin(φ)-tan(θ)·cos(φ))
Se andate a rivedere la teoria sul Raycasting:ΔX = X2 - X1 = (Ds·A/|Ys|)·(tan(θ2)-tan(θ1))·sin(φ) ΔY = Y2 - Y1 = -(Ds·A/|Ys|)·(tan(θ2)-tan(θ1))·cos(φ)
In definitiva otteniamo:θ = arctg (Xs/Ds) e quindi: tan(arctg (Xs/Ds))=Xs/Ds
Se consideriamo ΔXs = 1 (cioè pixels consecutivi della riga) otteniamo:ΔX = (A/|Ys|)·(Xs2-Xs1)·sin(φ) ΔY = -(A/|Ys|)·(Xs2-Xs1)·cos(φ)
Che come potete vedere sono assolutamente costanti e quindi dovremo calcolarli una sola volta per riga! Questa è l'unica ottimizzazione che mi sono concesso perchè mi è venuta spontanea.ΔX = (A/|Ys|)·sin(φ) ΔY = -(A/|Ys|)·cos(φ)
Se poi vogliamo esagerare consideriamo la mappa come un poligono, effettuiamo la proiezione e ci calcoliamo le coordinate di inizio e fine della riga orizzontale, questo comporta il disegno di molti meno punti e quindi risparmio di tempo, ma per il momento il mio cervello si rifiuta di collaborare.
Vediamo quindi come implementare questo algoritmo. Il listato è Ray02.ASM, che è uguale al precedente ma con la parte di controllo della distanza minima eliminata e la procedura di Raycast sostituita con quella che vedremo in seguito. Questo programma si occuperà di disegnare solo il pavimento e il soffitto.
Ovviamente la prima cosa da fare è definire i dati:
Per quanto riguarda la parte principale del codice:.MODEL TINY .286 .387 .DATA Lc = 64 ; Larghezza delle celle Hm = 64 ; Altezza muro LcShift = 6 ; Bits di scorrimento Nc = 16 ; Numero colonne NcShift = 4 ; Bits di scorrimento IncDir = 4 ; Incremento direzione Limite = 16 ; Distanza minima dalle pareti STop = 0 ; Limite superiore finestra video SBottom = 199 ; Limite inferiore finestra video SLeft = 0 ; Limite sinistro finestra video SRight = 319 ; Limite destro finestra video SCenterX = (SLeft+SRight)/2 ; Ascissa centro finestra video SCenterY = (STop+SBottom)/2 ; Ordinata centro finestra video Ls = (SRight-SLeft)+1 ; Larghezza dello schermo Temp DW 0 ; Variabile temporanea Dist DW 220 ; Distanza dello schermo Xp DW 6*Lc+Lc/2 ; Ascissa personaggio Yp DW 4*Lc+Lc/2 ; Ordinata personaggio Ap DW Hm/2 ; Altezza punto di visuale Am DW Hm ; Altezza dei muri Xs DW -SCenterX ; Ascissa prima colonna del video Ys DW 0 ; Ordinata schermo Angolo REAL4 30.0 ; Angolo di visuale IncAng REAL4 2.0 ; Incremento dell'angolo Coseno DW 0 ; Coseno dell'angolo di visuale Seno DW 0 ; Seno dell'angolo di visuale SegBuf DW 0 ; Segment buffer SegImm DW 0 ; Segment immagine X DW 0 ; Ascissa punto Y DW 0 ; Ordinata punto GrdRad REAL8 0.017453292519943295769 ; pi/180ø Off DW 0, 64, 128, 192 DW 64*256+0, 64*256+64, 64*256+128, 64*256+192 DW 128*256+0, 128*256+64, 128*256+128, 128*256+192 DW 192*256+0, 192*256+64, 192*256+128, 192*256+192 ; Per semplicità uso un'unica texture per tutte le celle ; sia del pavimento che del soffitto Pav DB 16*16 DUP (8)
Infine vediamo la procedura di disegno.CODE .STARTUP ; La parte iniziale è uguale a quella del caso precedente ... ; La parte che cambia è solo quella per il controllo della posizione ; che viene sostituita da: ADD AX,Xp ; Calcola nuova ascissa Xp del personaggio ADD BX,Yp ; Calcola nuova ordinata Yp del personaggio MOV Xp,AX ; Memorizza nuova Xp MOV Yp,BX ; Memorizza nuova Yp JMP @M4 ; Ridisegna mappa
RayCast: ; Imposta i parametri per il soffitto MOV AX,Hm ; Carica altezza muro SUB AX,Ap ; Sottrae altezza personaggio MOV Am,AX ; Memorizza altezza muro MOV Ys,SCenterY ; Semi altezza schermo MOV DI,SLeft ; Carica X iniziale MOV SI,OFFSET Pav ; Carica offset mappa soffitto ; Disegna soffitto @R1: CALL Riga ; Disegna riga ADD DI,320 ; Prossima riga DEC Ys ; Decrementa Ys JNS @R1 ; Disegna tutto il soffitto ; Imposta parametri per pavimento INC Ys ; Ys = 0 MOV AX,Ap ; Alterzza personaggio MOV SI,OFFSET Pav ; Carica offset mappa pavimento MOV Am,AX ; Altezza ; Disegna pavimento @R2: CALL Riga ; Disegna riga INC Ys ; Incrementa Ys ADD DI,320 ; Prossima riga CMP Ys,SCenterY ; Controlla se fine schermo JBE @R2 ; Disegna tutto il pavimento ; Copia buffer nella memoria video MOV AX,0A000H ; Segment memoria video MOV DS,SegBuf ; Segment buffer MOV ES,AX ; Copia Segment memoria video XOR DI,DI ; Azzera offset destinazione XOR SI,SI ; Azzera offset sorgente MOV CX,320*200/2 ; Dimensione schermo / 2 REP MOVSW ; Copia buffer PUSH CS ; Memorizza CS nello stack POP DS ; Copia CS RET ; Fine procedura ; Questa procedura disegna una riga orizzontale Riga: MOV BP,Ls ; Carica larghezza schermo PUSH DI ; Memorizza DI nello stack ; Calcola X, Y, ΔX e ΔY FILD Am ; A FIDIV Ys ; A/Ys FLD ST ; A/Ys A/Ys FCHS ; -A/Ys A/Ys FLD Angolo ; φ° -A/Ys A/Ys FMUL GrdRad ; φ -A/Ys A/Ys FLD ST ; φ φ -A/Ys A/Ys FSINCOS ; cos sin φ -A/Ys A/Ys FMULP ST(3),ST ; sin φ ΔY A/Ys FXCH ST(3) ; A/Ys φ ΔY sin FMUL ST(3),ST ; A/Ys φ ΔY ΔX FIMUL Dist ; A·Ds/Ys φ ΔY ΔX FILD Xs ; Xs A·Ds/Ys φ ΔY ΔX FILD Dist ; Ds Xs A·Ds/Ys φ ΔY ΔX FPATAN ; θ A·Ds/Ys φ ΔY ΔX FLD ST ; θ θ A·Ds/Ys φ ΔY ΔX FSUBR ST,ST(3) ; φ-θ θ A·Ds/Ys φ ΔY ΔX FSINCOS ; cos sen θ A·Ds/Ys φ ΔY ΔX FMUL ST,ST(3) ; cos·A·Ds/Ys sen θ A·Ds/Ys φ ΔY ΔX FXCH ST(4) ; φ sen θ A·Ds/Ys dX ΔY ΔX FSTP ST ; sen θ A·Ds/Ys dX ΔY ΔX FMUL ST,ST(2) ; cos·A·Ds/Ys θ A·Ds/Ys X ΔY ΔX FSTP ST(2) ; θ dY dX ΔY ΔX FCOS ; cos dY dX ΔY ΔX FDIV ST(2),ST ; cos dY dX/cos ΔY ΔX FDIVP ST(1),ST ; dY/cos dX/cos ΔY ΔX FILD Xp ; Xp dY/cos dX/cos ΔY ΔX FIADDP ST(2),ST ; dY/cos X ΔY ΔX FIADD Yp ; Y X ΔY ΔX ; Imposta Segment immagine e buffer MOV ES,SegImm ; Carica segment immagine MOV DS,SegBuf ; Carica Segment buffer ; Memorizza X e Y attuali e calcola il loro prossimo valore @R0: FIST CS:Y ; Memorizza Y FADD ST,ST(2) ; Prossima Y FXCH ; Scambia i registri FIST CS:X ; Memorizza X FADD ST,ST(3) ; Prossima X FXCH ; Scambia i registri ; Determina tipo di texture e gli offset MOV BX,CS:Y ; Carica Y MOV AX,CS:X ; Carica X MOV DX,BX ; Copia Y MOV CX,AX ; Copia X SAR BX,LcShift ; Calcola Yc SAR AX,LcShift ; Calcola Xc AND DX,Lc-1 ; Calcola riga texture AND CX,LC-1 ; Calcola colonna texture AND BX,Nc-1 ; Yc % Nc AND AX,Nc-1 ; Xc % Nc SHL BX,NcShift ; Moltiplica per numero colonne SHL DX,8 ; Moltiplica per larghezza immagine ADD BX,AX ; Offset mappa XOR AX,AX ; Azzera AX ADD CX,DX ; offset texture MOV AL,CS:[SI+BX] ; Carica tipo di texture ADD AX,AX ; Moltiplica per 2 MOV BX,AX ; Copia offset MOV BX,CS:Off[BX] ; Offset texture ADD BX,CX ; Copia puntatore ; Carica indice colore e scrive pixel MOV AL,ES:[BX] ; Carica indice colore MOV [DI],AL ; Scrive pixel ; Disegna tutta la riga orizzontale INC DI ; Incrementa puntatore DEC BP ; Decrementa larghezza schermo JG @R0 ; Disegna tutta la riga ; Ripristina DI, DS ed elimina i valori dal coprocessore POP DI ; Ripristina DI dallo stack PUSH CS ; Memorizza CS nello stack FSTP ST ; Elimina ST (Y) FSTP ST ; Elimina ST (X) FSTP ST ; Elimina ST (DeltaY) FSTP ST ; Elimina ST (DeltaX) POP DS ; Ripristina DS RET ; Fine procedura