What is DDA? Digital Differential Analysis (DDA) is a fast algorithm for determining which grid cells a ray passes through. In Cub3D, it’s used to find where rays intersect with walls in the 2D map grid.The algorithm works by:
Starting at the player’s position
Stepping through the grid one cell at a time
Always moving to the nearest grid line (either vertical or horizontal)
Stopping when a wall (cell containing ‘1’) is encountered
DDA is more efficient than naive ray marching because it only checks grid boundaries, not every point along the ray.
Ray Direction Setup Before DDA can begin, each ray needs a direction vector. This is calculated in the main raycasting loop:
raycasting.c (lines 102-127)
void raycasting (t_map * mapa , int i ) { double camera_x; double side_x; double side_y; double dist; int start_y; while ( ++ i < WIDTH) { camera_x = 2 * i / ( double )WIDTH - 1 ; mapa -> ray_dir_x = mapa -> dir_x + mapa -> plane_x * camera_x; mapa -> ray_dir_y = mapa -> dir_y + mapa -> plane_y * camera_x; init_dda (mapa, & side_x, & side_y); perform_dda (mapa, & side_x, & side_y); calculate_wall_data (mapa, & dist); select_texture (mapa); start_y = (HEIGHT - mapa -> line_height ) / 2 ; mapa -> end = start_y + mapa -> line_height ; if (start_y < 0 ) start_y = 0 ; if ( mapa -> end > HEIGHT) mapa -> end = HEIGHT; draw_3d_dda (i, start_y, mapa -> end , mapa); } }
For each screen column i from 0 to WIDTH:
Calculate Camera X
camera_x = 2 * i / ( double )WIDTH - 1 ;
Converts screen column to range [-1, 1], where:
-1 = left edge of screen0 = center of screen+1 = right edge of screen
Calculate Ray Direction
mapa -> ray_dir_x = mapa -> dir_x + mapa -> plane_x * camera_x; mapa -> ray_dir_y = mapa -> dir_y + mapa -> plane_y * camera_x;
Combines the camera’s forward direction (dir_x, dir_y) with the perpendicular camera plane (plane_x, plane_y) scaled by camera_x. The camera plane vectors define the field of view. In Cub3D, they’re set to 66% of the perpendicular direction vector (0.66 factor in set_player_dir_and_plane).
DDA Initialization The init_dda() function prepares all parameters needed for the DDA algorithm:
raycasting.c (lines 40-66)
void init_dda (t_map * mapa , double * side_dist_x , double * side_dist_y ) { mapa -> map_x = ( int )( mapa -> xx ); mapa -> map_y = ( int )( mapa -> yy ); mapa -> delta_dist_x = fabs ( 1 / mapa -> ray_dir_x ); mapa -> delta_dist_y = fabs ( 1 / mapa -> ray_dir_y ); if ( mapa -> ray_dir_x < 0 ) { mapa -> step_x = - 1 ; * side_dist_x = ( mapa -> xx - mapa -> map_x ) * mapa -> delta_dist_x ; } else { mapa -> step_x = 1 ; * side_dist_x = ( mapa -> map_x + 1.0 - mapa -> xx ) * mapa -> delta_dist_x ; } if ( mapa -> ray_dir_y < 0 ) { mapa -> step_y = - 1 ; * side_dist_y = ( mapa -> yy - mapa -> map_y ) * mapa -> delta_dist_y ; } else { mapa -> step_y = 1 ; * side_dist_y = ( mapa -> map_y + 1.0 - mapa -> yy ) * mapa -> delta_dist_y ; } }
Delta Distance Calculation The delta distances represent how far the ray must travel to cross one grid cell:
mapa -> delta_dist_x = fabs ( 1 / mapa -> ray_dir_x ); mapa -> delta_dist_y = fabs ( 1 / mapa -> ray_dir_y );
delta_dist_x Distance the ray travels to cross one vertical grid line
delta_dist_y Distance the ray travels to cross one horizontal grid line
Mathematical derivation: If the ray direction is (ray_dir_x, ray_dir_y), then moving distance d along the ray moves:
d * ray_dir_x units in Xd * ray_dir_y units in Y
To cross 1 unit in X:
d * ray_dir_x = 1 d = 1 / ray_dir_x
Step Direction and Initial Side Distance For each axis, we determine:
Step direction : Which way to move through the grid (+1 or -1)Initial side distance : How far until we hit the first grid line
X-axis (Vertical lines)
Y-axis (Horizontal lines)
if (mapa -> ray_dir_x < 0 ) { mapa -> step_x = - 1 ; // Moving left * side_dist_x = ( mapa -> xx - mapa -> map_x ) * mapa -> delta_dist_x ; } else { mapa -> step_x = 1 ; // Moving right * side_dist_x = ( mapa -> map_x + 1.0 - mapa -> xx ) * mapa -> delta_dist_x ; }
Example: If player is at position (5.3, 7.8) and ray points right (ray_dir_x > 0):
map_x = 5 (current grid cell X)Distance to next vertical line (x=6): (6 - 5.3) = 0.7
side_dist_x = 0.7 * delta_dist_x
DDA Execution The perform_dda() function implements the core stepping algorithm:
raycasting.c (lines 15-38)
int perform_dda (t_map * mapa , double * side_dist_x , double * side_dist_y ) { int hit; hit = 0 ; while ( ! hit) { if ( * side_dist_x < * side_dist_y) { * side_dist_x += mapa -> delta_dist_x ; mapa -> map_x += mapa -> step_x ; mapa -> side = 0 ; } else { * side_dist_y += mapa -> delta_dist_y ; mapa -> map_y += mapa -> step_y ; mapa -> side = 1 ; } if ( mapa -> final_map [ mapa -> map_y / SIZE][ mapa -> map_x / SIZE] == '1' ) hit = 1 ; } return ( mapa -> side ); }
Algorithm Steps
Compare Side Distances
if ( * side_dist_x < * side_dist_y)
Determines whether the next grid line is vertical or horizontal by comparing which is closer.
Step to Nearest Grid Line
If vertical line is closer: * side_dist_x += mapa -> delta_dist_x; // Update distance to next vertical line mapa -> map_x += mapa -> step_x; // Move to next column mapa -> side = 0 ; // Record we hit a vertical wall
If horizontal line is closer: * side_dist_y += mapa -> delta_dist_y; // Update distance to next horizontal line mapa -> map_y += mapa -> step_y; // Move to next row mapa -> side = 1 ; // Record we hit a horizontal wall
Check for Wall
if (mapa -> final_map [ mapa -> map_y / SIZE][ mapa -> map_x / SIZE] == '1' ) hit = 1 ;
Checks if the current grid cell contains a wall. Note the division by SIZE (30) to convert from pixel coordinates to grid coordinates.
Repeat Until Hit
The loop continues until a wall is found. The side variable (0 or 1) indicates whether the wall face is vertical or horizontal.
Visual Example Grid (top-down view): 0 1 2 3 4 ┌───┬───┬───┬───┬───┐ │ │ │ │ 1 │ 1 │ 0 ├───┼───┼───┼───┼───┤ │ │ │ │ │ 1 │ 1 ├───┼───┼───┼───┼───┤ │ P →→→→→→→→→ W │ 1 │ 2 (P = Player at (0.5, 2.5)) ├───┼───┼───┼───┼───┤ (Ray shoots right) │ │ │ │ │ 1 │ 3 (W = Wall hit at x=3) ├───┼───┼───┼───┼───┤ │ 1 │ 1 │ 1 │ 1 │ 1 │ 4 └───┴───┴───┴───┴───┘ DDA steps: 1. side_dist_x = 0.5 * delta_dist_x (to x=1) side_dist_y = 0.5 * delta_dist_y (to y=3) 2. Compare: side_dist_x < side_dist_y? Step to x=1, update side_dist_x 3. Step to x=2, update side_dist_x 4. Step to x=3, update side_dist_x Check: final_map[2][3] == '1'? Yes! Hit detected, side = 0 (vertical wall)
Distance Calculation After DDA finds a wall, calculate_wall_data() computes the perpendicular distance:
raycasting.c (lines 68-82)
void calculate_wall_data (t_map * mapa , double * dist ) { if ( mapa -> side == 0 ) * dist = ( mapa -> map_x - mapa -> xx + ( 1 - mapa -> step_x ) / 2 ) / mapa -> ray_dir_x / SIZE; else * dist = ( mapa -> map_y - mapa -> yy + ( 1 - mapa -> step_y ) / 2 ) / mapa -> ray_dir_y / SIZE; mapa -> line_height = ( int )(HEIGHT / * dist); if ( mapa -> side == 0 ) mapa -> wall_x = mapa -> yy / SIZE + * dist * mapa -> ray_dir_y ; else mapa -> wall_x = mapa -> xx / SIZE + * dist * mapa -> ray_dir_x ; mapa -> wall_x -= floor ( mapa -> wall_x ); }
We must use perpendicular distance , not Euclidean distance, to avoid the “fisheye effect” where walls appear curved.
For vertical walls (side == 0): dist = (map_x - xx + ( 1 - step_x) / 2 ) / ray_dir_x / SIZE
For horizontal walls (side == 1): dist = (map_y - yy + ( 1 - step_y) / 2 ) / ray_dir_y / SIZE
The term (1 - step_x) / 2 adjusts for whether we hit the near or far edge of the grid cell:
If step_x = 1 (moving right): (1-1)/2 = 0 (near edge)
If step_x = -1 (moving left): (1-(-1))/2 = 1 (far edge)
Wall Height Calculation mapa -> line_height = ( int )(HEIGHT / * dist);
The wall height on screen is inversely proportional to distance:
Closer walls → larger line_height
Farther walls → smaller line_height
Wall X Coordinate if (mapa -> side == 0 ) mapa -> wall_x = mapa -> yy / SIZE + * dist * mapa -> ray_dir_y; else mapa -> wall_x = mapa -> xx / SIZE + * dist * mapa -> ray_dir_x; mapa -> wall_x -= floor (mapa -> wall_x ); // Fractional part only
This calculates where on the wall the ray hit, used for texture mapping:
For vertical walls: Y-coordinate along the wall
For horizontal walls: X-coordinate along the wall
Result is in range [0, 1) representing position within one texture
Texture Selection Based on which side was hit and the ray direction, select the appropriate texture:
raycasting.c (lines 84-100)
void select_texture (t_map * mapa ) { if ( mapa -> side == 0 ) { if ( mapa -> ray_dir_x > 0 ) mapa -> current_tex = & mapa -> tex_east ; else mapa -> current_tex = & mapa -> tex_west ; } else { if ( mapa -> ray_dir_y > 0 ) mapa -> current_tex = & mapa -> tex_south ; else mapa -> current_tex = & mapa -> tex_north ; } }
side = 0 (Vertical wall)
ray_dir_x > 0 → East texture (hit from west)ray_dir_x < 0 → West texture (hit from east) side = 1 (Horizontal wall)
ray_dir_y > 0 → South texture (hit from north)ray_dir_y < 0 → North texture (hit from south)
O(k) where k is the number of grid cells crossed before hitting a wall.
Best case: O(1) if wall is in adjacent cell
Worst case: O(max(width, height)) if ray crosses entire map
Average case: Much better than naive ray marching which checks every point
O(1) - Only a fixed number of variables needed regardless of map size.
No floating-point multiplication in the main loop (only addition)
Division by SIZE happens after DDA completes
Integer map lookups only at grid boundaries
Early termination on first wall hit
Common Pitfalls Division by Zero : If ray_dir_x or ray_dir_y is exactly 0, delta_dist becomes infinite. The implementation uses fabs(1 / ray_dir) which handles this gracefully in practice since rays are never perfectly axis-aligned.
Coordinate Systems : The code mixes pixel coordinates (xx, yy) and grid coordinates (map_x / SIZE, map_y / SIZE). The SIZE constant (30) acts as the scaling factor between these systems.