2
\$\begingroup\$

I'm trying to build a simple grid-based raycaster, but I'm having trouble with rendering block corners.

First of all, I want to change the color of all the y-axis walls. But a block's corner belongs to both the y and x axis, so it's never clear whether it should be recolored or not. Because of this, when I place several blocks in a row, I end up with a wall with a bunch of vertical stripes on it.

striped wall

The second issue is that when two blocks are placed in such a way that only their corners "touch", a ray can pass between them and hit something behind them, allowing the camera to see things it should not be able to.

ray corner miss

corner gap

Here is my current implementation of a raycaster that showcases these issues, written in Rust with Raylib:

use raylib::prelude::*;


struct Map {
    scale: i32,
    data: Vec<Vec<i32>>,
}


impl Map {
    fn get_tile(&self, mut x: i32, mut y: i32) -> i32 {
        (x, y) = (x / self.scale, y / self.scale);
        let (max_y, max_x) = (self.data.len(), self.data[0].len());
        if y >= 0 && x >= 0 && y < max_y as i32 && x < max_x as i32 {
            return self.data[y as usize][x as usize];
        }

        return 0;
    }
}


struct Camera {
    fov: i32,
    range: i32,
    h: i32,
    w: i32,
}


impl Camera {
    fn draw(&self, player: &Player, map: &Map, display: &mut RaylibDrawHandle) {
        display.draw_rectangle(0, 0, self.w, self.h / 2, Color::BLACK);
        display.draw_rectangle(0, self.h / 2, self.w, self.h / 2, Color::GRAY);

        for i in (-self.fov / 2)..(self.fov / 2) {
            let (mut rx, mut ry);
            let ra = player.direction + (i as f32).to_radians();

            // slow but simple
            for step in 1..self.range {
                rx = (player.x.round() + step as f32 * ra.cos()).round() as i32;
                ry = (player.y.round() + step as f32 * ra.sin()).round() as i32;

                // only recolors one side, but showcases issue well
                let mut color = Color::WHITE;
                if rx % map.scale == 0 {
                    color = Color::LIGHTGRAY;
                }

                if map.get_tile(rx, ry) > 0 {
                    let dist = (
                        step as f32 * (player.direction - ra).cos()
                    ).round() as i32;
                    let line_height = (map.scale * self.h / dist).clamp(0, self.h);
                    let line_width = self.w / self.fov;
                    display.draw_rectangle(
                        self.w / 2 + i * line_width,
                        self.h / 2 - line_height / 2,
                        line_width,
                        line_height,
                        color
                    );
                    break;
                }
            }
        }
    }
}


struct Player {
    speed: f32,
    rotation_speed: f32,
    direction: f32,
    x: f32,
    y: f32,
}


impl Player {
    fn move_relative(&mut self, side: f32, fwd: f32, delta: f32, map: &Map) {
        let normalized = Vector2::new(side, fwd).normalized();

        let speed = self.speed * delta;
        let mut nx = self.x + speed * normalized.y * self.direction.cos();
        let mut ny = self.y + speed * normalized.y * self.direction.sin();

        let side_direction = self.direction + 90_f32.to_radians();
        nx = nx + speed * normalized.x * side_direction.cos();
        ny = ny + speed * normalized.x * side_direction.sin();

        if map.get_tile(nx.round() as i32, ny.round() as i32) == 0 {
            (self.x, self.y) = (nx, ny);
        } else if map.get_tile(nx.round() as i32, self.y.round() as i32) == 0 {
            self.x = nx;
        } else if map.get_tile(self.x.round() as i32, ny.round() as i32) == 0 {
            self.y = ny;
        }
    }

    fn rotate(&mut self, r: f32, d: f32) {
        self.direction += r * self.rotation_speed * d;
    }
}


fn main() {
    let (mut rl, thread) = raylib::init()
        .size(800, 450)
        .resizable()
        .title("rustcast")
        .build();

    rl.set_window_min_size(64, 64);
    //rl.set_target_fps(60);

    let map = Map {
        scale: 40,
        data: vec![
            vec![1,1,1,1,1,1,1,1,1],
            vec![1,0,0,0,0,0,0,0,1],
            vec![1,0,0,0,0,0,0,0,1],
            vec![1,0,0,0,0,0,0,0,1],
            vec![1,0,0,0,0,0,0,0,1],
            vec![1,0,0,0,0,0,0,0,1],
            vec![1,0,0,0,1,0,0,0,1],
            vec![1,0,0,0,0,1,0,0,1],
            vec![1,0,0,0,0,0,0,0,1],
            vec![1,1,1,1,1,1,1,1,1],
        ]
    };
    let camera = Camera {
        fov: 80,
        range: 600,
        w: 800,
        h: 450
    };
    let mut player = Player {
        speed: 50.0,
        rotation_speed: 10.0,
        direction: 0.0,
        x: 100.0,
        y: 100.0,
    };

    while !rl.window_should_close() {
        let delta_time = rl.get_frame_time();

        let (mut move_h, mut move_v, mut rotate) = (0, 0, 0);
        if rl.is_key_down(KeyboardKey::KEY_A) { move_h -= 1 };
        if rl.is_key_down(KeyboardKey::KEY_D) { move_h += 1 };
        if rl.is_key_down(KeyboardKey::KEY_W) { move_v += 1 };
        if rl.is_key_down(KeyboardKey::KEY_S) { move_v -= 1 };
        if rl.is_key_down(KeyboardKey::KEY_Q) { rotate -= 1 };
        if rl.is_key_down(KeyboardKey::KEY_E) { rotate += 1 };
        player.rotate(rotate as f32, delta_time);
        player.move_relative(move_h as f32, move_v as f32, delta_time, &map);

        let mut dis = rl.begin_drawing(&thread);

        dis.clear_background(Color::BLACK);
        camera.draw(&player, &map, &mut dis);
        dis.draw_fps(0, 0);
    }
}

What can I do to fix these issues? And is it possible to do that without adding a lot of complexity?

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Since you have a grid, you know something important: the ray is passing through a series of adjacent grid cells. You can fix both of your problem cases by making your code obey this rule.

Right now you're sampling along a fixed step size, which can skip over corners. A way to patch this algorithm to succeed would be to notice whenever the previous grid cell and the current grid cell are diagonally adjacent, and pretend the ray hit the one of the two diagonal cells in the mean time, thus making each individual step cross a specific, single face of a grid cell.

bad       patched
\ ##      \ ##
 \##  ->   `\#
##\       ##|
## \      ## \

Then, while you're doing this adjacency analysis, you can also determine which face of a grid cell is being entered (= which coordinate is changing and whether it is incrementing or decrementing). Then, you can choose colors according to that face and the cell coordinates, rather than only using the cell coordinates. If you do this, you will never see vertical stripes.


However, there is a better algorithm which not only inherently doesn't have this problem, but is also more efficient and precise because it takes exactly one step per grid cell examined (rather than taking steps smaller than cells). It is the algorithm presented in "A Fast Voxel Traversal Algorithm for Ray Tracing" by John Amanatides and Andrew Woo, 1987, and which I wrote up a practical example of in this answer, and later wrote a Rust version (though that is complicated with additional requirements, so it may not be the clearest sample).

While this algorithm as described is for 3D, you can make it 2D by just deleting the “Z” branch from the comparisons.

\$\endgroup\$
1
  • \$\begingroup\$ I took the first, simpler approach of patching my current algorithm. That fixed both my issues. \$\endgroup\$
    – user169549
    Jan 13, 2023 at 19:45

You must log in to answer this question.