使用 Rust 中的 DDA 算法和 Raylib 实现简单的光线投射器时遇到的问题

Question

我正在尝试在基于 2D 网格的世界中实现简单的奇异光线投射的数字微分分析器算法（使用 raylib 的 Rust）。我有一个有效的暴力方法，所以我制作了具有基本相同函数签名的 DDA 版本，希望 DDA 版本可以作为替代品。 网格是一组 8x8 的布尔值，用 64x64 像素正方形绘制。

这是两个函数签名：

fn ray_cast_brute_force(&self, player: &Player, d: &mut RaylibDrawHandle) 

fn ray_cast_dda(&self, player: &Player, d: &mut RaylibDrawHandle)

如此相同（仅真正取决于此播放器结构）：

pub struct Player {
    x: f32,
    y: f32,
    angle: f32, // in radians
    direction: Vector2,
}

方向 Vector2 是两个浮点数。

以下是 100% 有效的暴力版本的结果： 结果

及其实施：

 pub fn ray_cast_brute_force(&self, player: &Player, d: &mut RaylibDrawHandle) {
        // Starting parameters
        let ray_start = Vector2::new(player.x + 32.0, player.y + 32.0);
        let mut ray_end = ray_start;
        let step_size: f32 = 2.0;

        // Check is there is a wall at the ray's position inside the grid map (1 or 0)
        // If not, increase the length of the ray.
        // self.data is referring to the data of the 2D grid array of booleans
        while self.data[ray_end.x as usize / 64][ray_end.y as usize / 64] == 0 {
            ray_end.x += player.direction.x * step_size;
            ray_end.y += player.direction.y * step_size;
        }

        d.draw_line_ex(ray_start, ray_end, 5.0, Color::RED);
    }

我这里有我的 DDA 版本，但效果并不好。它沿正确的方向绘制一条射线，并且该射线永远不会逃逸到其内部的 512x512 像素贴图之外，但它通常不会像应有的那样在墙壁处结束。您可以在下面看到：

结果1 结果2

我的（简单且可能是错误的）实现：

 fn ray_cast_dda(&self, player: &Player, d: &mut RaylibDrawHandle) {
        // Immutable starting parameters
        let ray_start = Vector2::new(player.x + 32.0, player.y + 32.0); // Start position
        let direction_x = player.angle.cos(); // Ray direction X
        let direction_y = player.angle.sin(); // Ray direction Y
        let step_x = if direction_x < 0.0 { -1 } else { 1 }; // These determine step direction
        let step_y = if direction_y < 0.0 { -1 } else { 1 };
        let t_delta_x = (64.0 / direction_x.abs()).abs(); // These are how far in "t" each time you cross a tile boundary in x or y
        let t_delta_y = (64.0 / direction_y.abs()).abs();

        // Mutable starting parameters
        let mut map_x = (ray_start.x / 64.0) as isize; // These determine the current map grid square the ray is in
        let mut map_y = (ray_start.y / 64.0) as isize;
        let mut t_max_x = {
            let boundary_x = if direction_x > 0.0 {
                (map_x + 1) as f32 * 64.0
            } else {
                map_x as f32 * 64.0
            };
            (boundary_x - ray_start.x) / direction_x
        };
        let mut t_max_y = {
            let boundary_y = if direction_y > 0.0 {
                (map_y + 1) as f32 * 64.0
            } else {
                map_y as f32 * 64.0
            };
            (boundary_y - ray_start.y) / direction_y
        };

        let mut hit = false;

        // DDA algorithm loop
        while !hit {
            if t_max_x < t_max_y {
                map_x += step_x; // Increment appropriate map coordinate by 1
                t_max_x += t_delta_x; // Increase size the ray in x or y depending on which is larger
            } else {
                map_y += step_y;
                t_max_y += t_delta_y;
            }

            // check to see if we found a wall
            if self.data[map_x as usize][map_y as usize] != 0 {
                hit = true;
            }
        }

        // Calculate the distance to the hit point
        let t_hit = t_max_x.min(t_max_y);

        // Calculate the end point of the ray
        let ray_end = Vector2::new(
            ray_start.x + t_hit * direction_x,
            ray_start.y + t_hit * direction_y,
        );

        // This draws a line with a varable thickness
        d.draw_line_ex(ray_start, ray_end, 5.0, Color::RED);
    }

我想我可能在这里做错了什么，但是这个特定的算法相当复杂，我一生都无法弄清楚发生了什么。如果需要，将提供更多源代码。

Answer 1

我无法理解代码中的所有细节，但从我的角度来看，命中检测似乎存在一个小错误：

在命中检测中，您要查看 x 或 y 步长是否必须按斜率增加。我想这个逻辑一定是颠倒过来的。

我建议在这种情况下考虑布雷森汉姆算法。它使用从线性方程导出的整数误差值来计算下一次迭代。这种方法比 DDA 快得多，因为它依赖于整数运算而不是浮点运算。