在Rust+Raylib中实现DDA光线投射算法的问题排查

背景 #

我在Rust结合Raylib框架中，为8×8的布尔值网格世界（每个网格单元为64×64像素）实现基于Digital Differential Analyzer（DDA）算法的单条光线投射功能。已有可正常运行的暴力实现版本，因此编写了函数签名完全一致的DDA版本，期望直接替代暴力版本。

函数签名 #

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

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

Player结构体定义 #

pub struct Player {
    x: f32,
    y: f32,
    angle: f32, // 弧度制
    direction: Vector2,
}

其中direction为包含两个浮点数的Vector2类型。

正常运行的暴力实现版本 #

暴力实现可100%正常运行，代码如下：

pub fn ray_cast_brute_force(&self, player: &Player, d: &mut RaylibDrawHandle) {
    // 初始参数
    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;

    // 检查射线当前位置是否在墙体上（1为墙体，0为空）
    // 若未命中墙体，则延长射线长度
    // self.data 是8×8的布尔值网格数组
    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版本问题 #

DDA版本无法正常工作：射线方向正确，且不会超出512×512像素的地图范围，但通常无法正确终止在墙体上。

DDA实现代码 #

fn ray_cast_dda(&self, player: &Player, d: &mut RaylibDrawHandle) {
    // 不可变初始参数
    let ray_start = Vector2::new(player.x + 32.0, player.y + 32.0); // 射线起点
    let direction_x = player.angle.cos(); // 射线X方向分量
    let direction_y = player.angle.sin(); // 射线Y方向分量
    let step_x = if direction_x < 0.0 { -1 } else { 1 }; // X方向步进方向
    let step_y = if direction_y < 0.0 { -1 } else { 1 }; // Y方向步进方向
    let t_delta_x = (64.0 / direction_x.abs()).abs(); // 穿越X方向网格边界所需的t增量
    let t_delta_y = (64.0 / direction_y.abs()).abs(); // 穿越Y方向网格边界所需的t增量

    // 可变初始参数
    let mut map_x = (ray_start.x / 64.0) as isize; // 当前射线所在的网格X坐标
    let mut map_y = (ray_start.y / 64.0) as isize; // 当前射线所在的网格Y坐标
    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算法循环
    while !hit {
        if t_max_x < t_max_y {
            map_x += step_x; // 更新当前网格X坐标
            t_max_x += t_delta_x; // 更新下一次X边界的t值
        } else {
            map_y += step_y; // 更新当前网格Y坐标
            t_max_y += t_delta_y; // 更新下一次Y边界的t值
        }

        // 检查是否命中墙体
        if self.data[map_x as usize][map_y as usize] != 0 {
            hit = true;
        }
    }

    // 计算命中点的t值
    let t_hit = t_max_x.min(t_max_y);

    // 计算射线终点
    let ray_end = Vector2::new(
        ray_start.x + t_hit * direction_x,
        ray_start.y + t_hit * direction_y,
    );

    // 绘制射线
    d.draw_line_ex(ray_start, ray_end, 5.0, Color::RED);
}

求助 #

我认为DDA实现存在问题，但无法定位具体错误，若需要可提供更多源码。

内容的提问来源于stack exchange，提问作者Cade Thornton