Motore 3D in C++ – Raycasting parte II – texture mapping

Nella prima parte abbiamo visto come implementare un motore 3D basato su raycasting. Il motore realizzato è abbastanza spartano e prevede colori piatti sia per i muri che per soffitto e pavimento. Aggiungiamo ora le texture.

Prendiamo una immagine quadrata 256×256 pixel, ad esempio questa:

stone

Questa sarà la nostra texture che andremo ad applicare ai muri nel rendering finale della scena 3D. Siccome abbiamo stabilito che l’ambiente 3D è composto unicamente da semplici cubi una texture quadrata è l’ideale per texturizzare tutte le facce.

Come funziona il texture mapping?

L’idea base è quella di considerare questa volta non soltanto la lunghezza del raggio ma calcolare anche lo scostamento rispetto alla faccia del blocco. In figura si mostra il raggio uscente (in giallo), la collisione con il blocco e lo scostamento (in nero) rispetto alla faccia del blocco stesso:
raycasting - texture mapping

Lo scostamento ci serve per recuperare la “striscia” verticale di texture (1 x 256 pixel) da riscalare opportunamente (in funzione della lunghezza del raggio, come visto nella prima parte) e applicare al posto della semplice riga verticale monocolore. Ripetendo il processo per ogni singolo raggio otteniamo il texture mapping completo della scena.

Caricamento della texture da file esterno

Per prima cosa occorre caricare la texture da una immagine esterna. Nel mio caso ho utilizzato il formato non compresso TGA perchè estremamente semplice da leggere (una collezione lineare di triple RGB).

Aggiungiamo al codice dei define per le dimensioni della texture:

#define TEXT_W 256
#define TEXT_H 256

definiamo la struttura dati Texture: altezza, larghezza e puntatore al vettore di pixel RGB.

struct Texture
{
	uint32_t width;
	uint32_t height;
	TrueColorPixel *data;
};

Modifichiamo la struttura dati RayHit aggiungendo lo scostamento di cui parlavamo prima: blockOffset e wallX. Il primo è lo scostamento in coordinate texture (i pixel di scostamento rispetto alla dimensione della texture), il secondo è lo scostamento in coordinate mappa 2D (un valore floating point compreso tra 0 ed 1).

struct RayHit
{
	double distance;
	int mapX;
	int mapY;
	double wallX;
	double rayDirX;
	double rayDirY;
	int side;
	uint32_t blockOffset;
};

Definiamo la variabile globale stone

Texture stone;

Nel main() carichiamo la texture. Si tratta di aprire e leggere il file “stone.tga” e allocare un vettore di 65536 byte (246×256) in stone.data. Per i dettagli della funzione LoadTexture basta dare un’occhiata al sorgente.

	if (!LoadTexture("stone.tga", &stone))
	{
		printf("\nError loading texture file!");
		exit(0);
	}

A questo punto, nella funzione RenderScence, subito dopo aver calcolato la lunghezza del raggio, calcoliamo lo scostamento (sia wallX che blockOffset):

		// calcola wallX ovvero l'offset x del blocco colpito dal raggio
		double wallX;
		if (side == 1)
		{
			wallX = rayPosX + ((mapY - rayPosY + (1 - stepY) / 2) / rayDirY) * rayDirX;
		}
		else
		{
			wallX = rayPosY + ((mapX - rayPosX + (1 - stepX) / 2) / rayDirX) * rayDirY;
		}
		wallX -= floor((wallX));

		// riga della texture (in coordinate texture) 
		int texX = int(wallX * double(TEXT_W));
		
		// inverti in base alla posizione del raggio
		if (side == 0 && rayDirX > 0)
		{
			texX = TEXT_W - texX - 1;
		}
		if (side == 1 && rayDirY < 0)
		{
			texX = TEXT_W - texX - 1;
		}

		// carica RayHit con le informazioni per disegnare la colonna
		RayHit what;
		what.distance = perpWallDist;
		what.blockOffset = texX;
		what.mapX = mapX;
		what.mapY = mapY;
		what.side = side;
		what.rayDirX = rayDirX;
		what.rayDirY = rayDirY;
		what.wallX = wallX;

Nella DrawColumn anzichè disegnare una colonna di pixel piatti, disegnamo una striscia verticale di texture opportunamente riscalata:

	// disegna colonna
	for (uint32_t c = cropup; c < (colh - cropdown); c++)
	{
		// calcola il pixel da prelevare nella texture
		double d = (double)c / (double)colh;
		int texY = ((int)(d * TEXT_H)) % TEXT_H;
		TrueColorPixel t = texture.data[what.blockOffset + texY * TEXT_W];

		// disegna il pixel della texture
		frame.data[index].r = t.r;
		frame.data[index].g = t.g;
		frame.data[index].b = t.b;

		index += frame.width;
	}

Il risultato finale è questo:
raycasting - texture mapping

A questo punto diventa abbastanza banale creare più di una immagine texture, caricarle tutte in memoria e texturizzare i blocchi utilizzando la texture oppurtuna (in funzione ad esempio numero intero associato al blocco, nel file world.txt).

Questo il codice sorgente completo con texture mapping

Il risultato finale:

Pavimento e soffitto

Il pavimento e soffitto possono essere rendirizzati con una tecnica analoga. Innanzitutto, siccome abbiamo visto che la geometria del rendering finale è simmetrica rispetto all’asse verticale dello schermo allora lo sarà anche il pavimento rispetto al soffitto. Una volta che sappiamo texturizzare il pavimento basta “ribaltarlo” in verticale per ottenere il soffitto (magari cambiando immagine texture).

Procediamo con il redenring del pavimento: per ogni colonna di pixel dello schermo e immediatamente dopo aver disegnato la riga muro, occorre procedere in questo modo:

Si considera il segmento di pixel verticale rimanente per raggiungere il fondo dello schermo. Si calcolano le coordinate mondo di ogni pixel di questo segmento. Ad ogni coordinata mondo corrisponde un preciso punto nella texture 256×256 di pavimento. Si disegna quel pixel con il colore della texture in quel punto. Ripetendo per tutte le colonne otteniamo la texture completa del pavimento.

Per disegnare il soffitto non occorre ricalcolare altri punti. Sapendo che è simmetrico rispetto al pavimento è sufficiente cambiare texture ed usare gli stessi punti trovati per il pavimento. Ovviamente avendo cura di ribaltare il plot sull’asse verticale.

	// posizione X,Y del texel della texture proprio sotto il muro
	double floorXWall, floorYWall;

	// 4 possibili direzioni del muro
	if (what.side == 0 && what.rayDirX > 0)
	{
		floorXWall = what.mapX;
		floorYWall = what.mapY + what.wallX;
	}
	else if (what.side == 0 && what.rayDirX < 0)
	{
		floorXWall = what.mapX + 1.0;
		floorYWall = what.mapY + what.wallX;
	}
	else if (what.side == 1 && what.rayDirY > 0)
	{
		floorXWall = what.mapX + what.wallX;
		floorYWall = what.mapY;
	}
	else
	{
		floorXWall = what.mapX + what.wallX;
		floorYWall = what.mapY + 1.0;
	}

	double distWall, distPlayer, currentDist;
	distWall = what.distance;
	distPlayer = 0.0;

	// disegna pavimento e soffitto
	uint32_t c = (colh + frame.height) / 2;
	
	while (c < frame.height) // per ogni pixel al di sotto della colonna muro
	{
		// calcola la distanza
		currentDist = frame.height / (2.0 * c - frame.height);
		double weight = (currentDist - distPlayer) / (distWall - distPlayer);

		// calcola il punto X,Y nel blocco corrente
		double currentFloorX = weight * floorXWall + (1.0 - weight) * state.posx;
		double currentFloorY = weight * floorYWall + (1.0 - weight) * state.posy;
		
		// calcola il punto X,Y nella texture del pavimento
		int floorTexX, floorTexY;
		floorTexX = int(currentFloorX * 256) % 256;
		floorTexY = int(currentFloorY * 256) % 256;
		
		if(CAST_FLOOR)
		{
			// pixel di pavimento (relativo alla colonna column)
			TrueColorPixel f = tiles.data[floorTexX + floorTexY * 256];
			frame.data[index].r = f.r;
			frame.data[index].g = f.g;
			frame.data[index].b = f.b;
		}

		if(CAST_CEILING)
		{
			// pixel di soffitto (relativo alla colonna column)
			TrueColorPixel g = ceiling.data[floorTexX + floorTexY * 256];
			frame.data[column + (frame.height - c - 1) * frame.width].r = g.r;
			frame.data[column + (frame.height - c - 1) * frame.width].g = g.g;
			frame.data[column + (frame.height - c - 1) * frame.width].b = g.b;
		}
		
		index += frame.width;
		c++;
	}

codice sorgente con texture mapping muri, terreno e soffitto.

Qui potete trovare il sorgente completo (progetto eclipse, immagini texture)

Forza 4 in C

Forza4, il mitico gioco a turno dove occorre allineare 4 o più pedine in una scacchiera 6×7.

In questo articolo mostro come realizzare un IA abbastamza intelligente da poter giocare decentemente contro un avversario umano.

La grafica è completamente realizzata in ASCII, quindi niente di incredibile; quello che interessa è l’algorimo dell’IA e come esso è stato implementato: il minmax.

Minmax è una funzione di valutazione in grado di minimizzare (min) la massima perdita possibile e contemporaneamente massimizzare (max) il minimo guadagno. L’algorimo è applicabile a tutti i giochi a informazione completa come forza4, scacchi, dama, tris e in generale i giochi a turno.

L’algoritmo trova la mossa migliore esplorando tutto l’albero delle possibilità da quel punto del gioco in poi; in sostanza effettua una enorme quantità di simulazioni di gioco, provando tutte le prossime possibili mosse dell’avversario, tutte le possibili contromosse successive, tutte le possibili mosse successive dell’avversario e cosi’ via fino alla fine di ogni partita “simulata”. Ovviamente il numero dei possibili sviluppi di gioco aumenta esponenzialmente al numero delle mosse provate e quindi non è possibile esplorare completamente l’albero: occorre fermarsi prima.

500px-minimax.svg

Una realizzazione concreta proverà solo un ristretto numero di mosse in avanti terminate le quali verrà valutato in una scala opportuna il vantaggio del giocatore a quel preciso stato di gioco.

Codice sorgente: forza4

/* FORZA 4 - algoritmo DFS minimax */

#define SKILL 10
#define ROW 6
#define COLUMN 7

int board[ROW*COLUMN];
long int depth,skill;
unsigned long int nodes;

void display_board(void)
{
	long int i,j;
	printf("\n");
	for(j=0;j<ROW;j++)
	{
		for(i=0;i<COLUMN;i++)
		{
			if(board[i+j*COLUMN]==1) printf("X ");
			if(board[i+j*COLUMN]==-1) printf("O ");
			if(board[i+j*COLUMN]==0) printf(". ");
		}
		printf("\n");
	}
	for(i=0;i<(COLUMN*2)-1;i++) printf("-");
	printf("\n");
	for(i=0;i<COLUMN;i++) printf("%d ",i+1);
	printf("\n");
}

int checkwin(int player,int column,int lenght)
{
	long int j,r,l,i,height;
	lenght--;
	i = column;
	j = ROW-1;
	while(board[i+j*COLUMN]!=0) j--;
	j++;
	height = j;

	r = 0;
	l = 0;
	while(((++i)<COLUMN)&&(board[i+j*COLUMN]==player)) r++;
	i = column;
	while(((--i)>=0)&&(board[i+j*COLUMN]==player)) l++;
	if ((r+l)>=lenght) return 1;
	i = column;

	r = 0;
	while(((++j)<ROW)&&(board[i+j*COLUMN]==player)) r++;
	if (r>=lenght) return 1;
	j = height;

	r = 0;
	l = 0;
	while(((++i)<COLUMN)&&((++j)<ROW)&&(board[i+j*COLUMN]==player)) r++;
	i = column;
	j = height;
	while(((--i)>=0)&&((--j)>=0)&&(board[i+j*COLUMN]==player)) l++;
	if ((r+l)>=lenght) return 1;
	i = column;
	j = height;

	r = 0;
	l = 0;
	while(((++i)<COLUMN)&&((--j)>=0)&&(board[i+j*COLUMN]==player)) r++;
	i = column;
	j = height;
	while(((--i)>=0)&&((++j)<ROW)&&(board[i+j*COLUMN]==player)) l++;
	if ((r+l)>=lenght) return 1;

	return 0;
}

int extimated_value(int player)
{
	long int i,j,value,l;

	value = 0;
	for(l=2;l<4;l++)
	{
		for(i=0;i<COLUMN;i++)
		{
			if(checkwin(player,i,l)) value = value + l;
		}
	}

	return value;
}

int goodness(int player,int depth,int column,int trigger)
{
	long int max,i,value,j;
	max = -200;
	if (checkwin(-player,column,4)) return -128;
	if (depth==0) return 0;
	for(i=0;i<COLUMN;i++)
	{
		if(board[i]==0)
		{
			j = ROW-1;
			while(board[i+j*COLUMN]!=0) j--;
			board[i+j*COLUMN] = player;
			nodes++;
			value = -goodness(-player,depth-1,i,-max)/2;
			board[i+j*COLUMN] = 0;
			if (value>max) max = value;
			if (value>trigger) return max;
		}
	}
	return max;
}

int best_move(int player)
{
	long int i,j,max,value,best,same,trigger,old,att;
	long int res[COLUMN];
	max = -100;
	best = -1;
	for(i=0;i<COLUMN;i++)
	{
		if(board[i]==0)
		{
			nodes = 0;
			j = ROW-1;
			while((board[i+j*COLUMN]!=0)&&(j>=0)) j--;
			board[i+j*COLUMN] = player;
			value = -goodness(-player,skill,i,200);
			printf("\nmove %d goodness: %d   tree size for this move: %d nodes",i+1,value,nodes);
			res[i] = value;
			board[i+j*COLUMN] = 0;
			if (value>max)
			{
				max = value;
				best = i;
			}
		}
	}
	if(best==-1)
	{
		for(i=0;i<COLUMN;i++) if(board[i]==0) return i;
	}

	return best;
}

int main(void)
{
	int move,j,i,coins;
	coins = ROW*COLUMN;
	skill = SKILL-3;

	for(i=0;i<(ROW*COLUMN);i++) board[i] = 0;
	display_board();

	while(coins!=0)
	{
		if (coins==40) skill=SKILL-2; /* quick start */
		if (coins==36) skill=SKILL-1; /* improve skill level... */
		if (coins==34) skill=SKILL;   /* ...to maximum */
		do
		{
			printf("\nchoose column [1-%d]...",COLUMN);
			scanf("%d",&move);
			if(board[move-1]!=0) printf("\ncolumn is full");
		}
		while(board[move-1]!=0);
		move--;
		j = ROW-1;
		while((board[move+j*COLUMN]!=0)&&(j>=0)) j--;
		board[move+j*COLUMN] = 1;
		coins--;
		display_board();
		if(checkwin(1,move,4))
		{
			printf("\nYou win\n");
			return 1;
		}
		move = best_move(-1);

		j = ROW-1;
		while((board[move+j*COLUMN]!=0)&&(j>=0)) j--;
		board[move+j*COLUMN] = -1;
		display_board();
		printf("\nCPU move in %d",move+1);
		coins--;
		if(checkwin(-1,move,4))
		{
			display_board();
			printf("\nCPU wins\n");
			return 1;
		}
		printf("\n");

	}
	printf("\n");
	return 1;
}

Ecco l’output del programma durante una partita:

forza4