Raycasting (DDA)

Raycasting is the algorithm that turns the 2D map into the first-person world view. In this project, the core traversal uses DDA: a grid-walking method that advances from one cell boundary to the next until a blocking tile is reached.

Grid traversal

One column, one ray, one deterministic first hit

DDA is the core grid-walking algorithm behind `cub3D`. For each screen column, the engine builds a ray, walks cell crossings until a solid tile is hit, then projects the corresponding wall slice.

01

per-column DDA sequence

The same four stages repeat for every screen column in the render loop.

01 build ray direction from camera_x

each screen column gets a different camera-space coordinate and therefore a different ray direction

                camera_x = 2.0 * x / frame_width - 1.0
ray_dir_x = dir_x + plane_x * camera_x
ray_dir_y = dir_y + plane_y * camera_x
              

02 initialize DDA distances

delta distances, step direction, and first side distances define how the ray walks the grid

                map_x = (int)player_x
map_y = (int)player_y
delta_x = fabs(1.0 / ray_dir_x)
delta_y = fabs(1.0 / ray_dir_y)
if (ray_dir_x < 0) { step_x = -1; side_x = (player_x - map_x) * delta_x; }
else               { step_x =  1; side_x = (map_x + 1 - player_x) * delta_x; }
              

03 advance until first blocking tile

compare the next X crossing and Y crossing, then move on the smallest one

                while (!hit && guard++ < MAX_STEPS)
{
  if (side_x < side_y) { side_x += delta_x; map_x += step_x; side = 0; }
  else                 { side_y += delta_y; map_y += step_y; side = 1; }
  if (is_solid(map_y, map_x)) hit = 1;
}
              

04 project the wall slice

perpendicular distance avoids fish-eye distortion and drives the final screen-space slice

                if (side == 0) perp_dist = side_x - delta_x;
else           perp_dist = side_y - delta_y;
line_height = (int)(frame_h / perp_dist)
draw_start = frame_h / 2 - line_height / 2
draw_end   = frame_h / 2 + line_height / 2
              

02

interactive DDA visualizer

Switch between top-down ray view, projected wall result, and DDA step trace.

2D ray view 3D projection DDA steps

move over the map view to inspect a column

03

DDA invariants

The traversal stays deterministic because each column is independent and state-local.

first hit only

the loop stops on the first blocking grid cell reached by the ray

guarded traversal

a maximum step count avoids infinite loops on malformed runtime state

stack-local ray data

`t_ray` lives per column and does not share mutable state with other rays

✓

`O(W * K)` and column-independent

Width `W` controls the number of rays, while `K` is the average number of grid crossings before a hit. That keeps the algorithm simple, local, and predictable.

deterministic first-hit traversal per-column independence projection from `perp_dist` ready for texture mapping

Per-Column Flow

For each screen column:

1. compute camera_x
2. derive ray_dir from dir + plane * camera_x
3. initialize map cell, deltas, steps, and side distances
4. walk the grid with DDA
5. stop on the first solid hit
6. compute perp_dist
7. project the wall slice for rendering

That makes the whole wall rendering pipeline column-based and deterministic.

raycast_scene

The 3D scene is a column loop

`raycast_scene()` does not draw a whole wall at once. It repeats the same work for every frame column x: cast a ray, find distance, compute height, draw one slice.

Play Step Reset

column0

perp_dist-

line_height-

waiting frame

Real function

int raycast_scene(t_app *app)
{
    int   x;
    t_ray ray;

    x = 0;
    while (x < app->frame.width)
    {
        ray = cast_ray(app, x);
        draw_wall_column(app, ray);
        bonus_sprites_set_depth(app, x, ray.perp_dist);
        x++;
    }
    return (0);
}

Distance to height

`line_height = frame.height / perp_dist`.

The larger the distance, the smaller the vertical slice becomes.

Why DDA Works

DDA compares the next X-boundary crossing and the next Y-boundary crossing. Whichever distance is smaller is the next grid line reached by the ray.

That guarantees:

• no skipped cells
• first-hit correctness
• stable side detection (side == 0 or side == 1)

That is why DDA fits tile maps so well.

Blocking Rules

A DDA traversal stops when the current traversed cell is considered solid.

That includes:

• mandatory wall tiles
• bonus solid tiles
• door tiles depending on passability state in bonus mode

The same world logic therefore has to stay consistent across traversal, collision, and rendering.

Perpendicular Distance

After the hit, the engine uses perpendicular distance instead of raw Euclidean distance from the player.

That matters because:

• it removes fish-eye distortion
• it produces correct wall slice height
• it matches the camera plane projection model

From there, line_height, draw_start, and draw_end are derived for the current column.

Fish-eye - and how to correct it

euclidean distance vs perpendicular distance

1. First - understand the problem

Imagine you are the player. You look at a straight wall in front of you. The wall is flat, at the same projected distance everywhere. But with Euclidean distance, the rays near the edges of the field of view travel farther.

2. What it does on screen

Reminder: line_height = WIN_H / distance. The larger the distance, the smaller the column. So if edge rays are longer, their columns get smaller, and the wall looks curved.

×Euclidean distance (fish-eye) ✓Perpendicular distance (correct)

Euclidean distance - curved wall (fish-eye)

Euclidean distances - larger near the edges:

edge col center col edge col

3. How your code corrects fish-eye

Your code never computes sqrt(dx² + dy²) for projection. It directly uses the accumulated DDA distances, which gives the perpendicular distance automatically.

// × NEVER this in your code:
dist = sqrt(dx*dx + dy*dy);   // euclidean distance = fish-eye

// ✓ what your code does:
if (r.side == 0)
    r.perp_dist = r.side_x - r.delta_x;  // perpendicular distance
else
    r.perp_dist = r.side_y - r.delta_y;  // perpendicular distance

Why does side_x - delta_x give the perpendicular distance?

side_x = accumulated distance to the next vertical border

delta_x = distance between two consecutive vertical borders

side_x - delta_x = distance to the previous border = distance to the wall

This value is projected on the camera axis. It is perpendicular to the camera plane, not diagonal. That is why it is the same for all rays that hit the same flat wall.

4. Summary - the 3 distances

Fish-eye happens when the rays near the screen edges appear longer than the center ray, even when they hit the same wall. Result: the wall looks curved, like through a wide-angle lens.

The cause: using Euclidean distance (sqrt(dx² + dy²)), which measures the real length of the diagonal ray.

The correction: use perpendicular distance (side_x - delta_x), which measures the ray projection on the camera axis. This value is identical for rays hitting the same flat wall, so the wall remains straight.

In your code: r.perp_dist = r.side_x - r.delta_x. That is all you need. No sqrt, no manual correction.

Safety and Complexity

The traversal includes a guard limit to avoid infinite loops in malformed runtime states, even though validated maps should already be enclosed.

For frame width W and average traversal length K:

• total cost is approximately O(W * K)
• each column remains independent from the others

That keeps the render path simple and easy to reason about.

Code References

• srcs/render/raycast.c
• srcs/render/raycast_draw.c
• srcs/render/render_frame.c
• srcs_bonus/doors/doors_query.c