V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
netcan
V2EX  ›  Rust

用 Rust 写一个斗兽棋游戏

  •  4
     
  •   netcan · 2020-06-07 20:38:29 +08:00 · 4622 次点击
    这是一个创建于 1390 天前的主题,其中的信息可能已经有所发展或是发生改变。

    博客原文地址:Rust 写一个斗兽棋游戏

    项目地址:

    好久没更新 blog 了,主要技术文章都是在公司内部写,后面看看有没有机会同步到 blog 上。

    现在利用业余时间写了棋类游戏,起初是因为部门最近举行编程大赛,主题是写一个中国象棋 AI,这期间偷偷参加了比赛,参考了国际、中国象棋的相关算法,最后利用alpha beta剪枝算法,取得了总决赛季军名次,这个名次对我们来说还可以,因为八强中有七强是直接拿开源代码稍微改改就比赛了的,我们全靠自己写,拿到这个名次还算可以。

    还是要吐槽这次比赛的,毕竟海思部门是第一次举办软件大赛,选了这种网上代码一大堆的题目实在没意思。还是无线的软件大赛有意思,题目比较偏门,比如 18 年那次比赛是写一个 RTS 对抗游戏的 ai,网上没有现成的代码可利用,全靠手写,就这样拿了冠军。

    编码是我的爱好,业余时间想写点什么来消遣一下,正好最近这个象棋游戏给了我启发,不如直接也从头写一个玩玩,既然写就需要考虑用什么语言写了,C/C++是我的强项,写了对我来说没任何编码技巧上的提升,就用Rust来试试手,看看编码体验如何吧,于是有了下面的项目:

    把 GUI 写完后,发现在写下去没意思,因为在比赛的时候已经用C++把 AI 写过一编,于是就先搁置了。

    ChineseChess.png

    后来想起了小学爱玩的斗兽棋,心血来潮,规则比较简单,分支因子也小,相对象棋来说简单多了,然后就收集素材,很快把象棋的 GUI 改成了斗兽棋的,并添加了 AI 。虽然目前的 AI 比较弱智,但是我目前已经很难赢了😂。

    animal_chess.png

    模块划分

    接下来讲讲实现部分。目前项目由四部分实现:

    src
    ├── ai.rs    # AI 实现
    ├── chess.rs # 棋子的定义
    ├── game.rs  # 核心框架、图像渲染
    └── main.rs  # 程序主入口
    

    首先需要 GUI 来交互,我考虑了SDL框架,因为上手简单,很快仿着rust-sdl2例子写了个 gui 出来:https://docs.rs/sdl2/0.34.0/sdl2/#getting-started

    类型别名

    和 C 的typedef,C++的using类似,Rust 也支持别名:

    pub type POS = u8;
    pub type MOVE = u16;
    pub type ScoreType = i32;
    

    异常处理

    来看看异常处理,Rust 有个语法糖?可以很简单的处理异常:

    fn main() -> Result<(), String> {
        let sdl_ctx = sdl2::init()?;
        let video_sys = sdl_ctx.video()?;
    
        let windows = video_sys.window("AnimalChess", WINDOW_WIDTH, WINDOW_HEIGHT)
            .position_centered()
            // .resizable()
            .allow_highdpi()
            .build().expect("could not initialize video subsystem");
    
        let mut game = Game::new(windows, sdl_ctx.event_pump()?);
    
        game.run()?;
    
        Ok(())
    }
    

    其中sdl2::init()?表达了init可能失败导致panic,我也不处理这个异常,直接通过?扔出去。

    结构体定义

    然后把 GUI 部分从main提取出来,封装到Game类中:

    pub struct Game {
        pub chesses: [[ChessId; COL_NUM]; ROW_NUM],
        chesses_textures: Vec<Texture>,
        pub role: Role, // 轮到谁下
        board: Texture,
        canvas: WindowCanvas,
        event_pump: EventPump,
        selected_chess: Option<POS>,
        selected_frame: Texture,
        movable_pos: Vec<MOVE>,
        pub compture_turn: bool,
        pub compture_mv: Option<MOVE>,
        ctx: VecDeque<Context>,
        pub history_table: HisTblType,
    }
    

    if-let表达式,结构化绑定

    其中棋子、棋盘的素材存到了chesses_textures, board成员中,并用chesses存放了棋盘内容。selected_chess存的是当前用户点击的棋子,movable_pos存放的是当前选中棋子可走的格子,当用户点击棋盘的时候,可能是选中棋子,也可能是移动棋子,如下实现:

    fn process_click(&mut self, pos: (i32, i32)) {
        if let Some(dst) = self.get_click_rect(pos) {
            if get_chess_role(self.chesses[dst.0][dst.1]) != self.role {
                // may be move
                if let Some(_) = self.movable_pos.iter().find(|&&mv| { return get_dst_pos(mv) == to_pos(&dst) }) {
                    let src = self.selected_chess.unwrap();
                    self.move_chess(to_move(&(get_pos(src), dst)));
                }
                self.selected_chess = None;
            } else { // must be selected, because role is same as chess
                println!("selected_chess: {:?}", to_pos(&dst));
                self.selected_chess = Some(to_pos(&dst));
            }
    
            self.movable_pos.clear();
        }
    }
    

    这时候看到结构绑定的好处了,get_click_rect返回一个Option<(usize, usize)>值,将用户的鼠标位置转换成棋盘的行列位置。通过if let语句来获得Some里面的值并取出,接着进行判断。若用户没有选中棋子,这可能是移动棋子,这时候通过查找movable_pos来判断是否移动。

    再来看一个例子:

    for event in self.event_pump.poll_iter() {
        match event {
            // ...
            Event::KeyDown { keycode: Some(keycode), .. } => {
                match keycode {
                    Keycode::Escape => { break;       }
                    Keycode::U      => { undo = true; }
                    _ => {}
                }
            }
            Event::MouseButtonDown {x, y, ..} => { click_pos = (x, y); }
            _ => {}
        }
    }
    

    结构化绑定,可以分别取出结构体Event::KeyDown, Event::MouseButtonDown对象里的成员变量:keycode, x, y

    通过结构化绑定,写起来很爽。目前 C++ 17 也有了结构化绑定,但是没有 Rust 那么强大。对于Option这个表达可有的概念,C++17 也有了std::optional

    match 表达式

    Rust 还有一个强大的语句,那就是match,前面例子已经介绍过了,写起来是这样的。判断棋子是否进入了对方的兽穴:

    pub fn check_in_den(&self, pos: POS) -> bool {
        let pos_ = get_pos(pos);
        match (get_chess_role(self.chesses[pos_.0][pos_.1]), pos) {
            (RED, BLACK_DEN) | (BLACK, RED_DEN) => return true,
            _ => { return false }
        }
    }
    

    其中(RED, BLACK_DEN) | (BLACK, RED_DEN) => return true语义很清晰,如果红色棋子进了黑色兽穴,或者黑色棋子进了红色兽穴,则为真;其他情况为假。如果换成if-else语句,写出来就很丑了。

    还有check_movable里的判断吃子代码也很简洁:

    match (src_chess_type, dst_chess_type) {
        (RAT, ELEPHANT) => ! Self::check_in_water(src),
        (ELEPHANT, RAT) => false,
        (s, d)          => s <= d || self.check_in_traps(dst)
    }
    
    • 老鼠若不在水里则能够吃大象:(RAT, ELEPHANT) => ! Self::check_in_water(src)
    • 大象在任何情况下都不能吃老鼠:(ELEPHANT, RAT) => false
    • 其他场景按照大子吃小子规则,若对方在陷阱里,无视这个规则:(s, d) => s <= d || self.check_in_traps(dst)

    再来看看一个例子,就是根据 fen 串来初始化棋盘。fen 串是用字符串记录了棋子在棋盘中的位置,例如初始化的 fen 串是这样的:l5t/1d3c1/r1p1w1e/7/7/7/E1W1P1R/1C3D1/T5L,小写表示黑方,大写表示红方。一个字母表示一个棋子,如果没有棋子,则用数字表示出相邻连续的空位数。斗兽棋共有九行,每行都用一个字符串表示,行间使用正斜杠分割。

    解析fen串的代码是这样的,很清爽:

    fn load_fen(&mut self, fen: &str) {
        let fen_u8 = fen.as_bytes();
        let mut fen_idx = 0;
    
        let get_role = |c: u8| -> Role {
            if (c as char).is_lowercase() { BLACK }
            else { RED }
        };
    
        let mut pos = 0usize;
        while fen_idx < fen_u8.len() {
            let mut chess_id = EMPTY;
            match fen_u8[fen_idx] {
                c @ b'e' | c @ b'E' => { chess_id = get_chess_id(get_role(c), ELEPHANT); }
                c @ b'l' | c @ b'L' => { chess_id = get_chess_id(get_role(c), LION);     }
                c @ b't' | c @ b'T' => { chess_id = get_chess_id(get_role(c), TIGER);    }
                c @ b'p' | c @ b'P' => { chess_id = get_chess_id(get_role(c), PANTHER);  }
                c @ b'w' | c @ b'W' => { chess_id = get_chess_id(get_role(c), WOLF);     }
                c @ b'd' | c @ b'D' => { chess_id = get_chess_id(get_role(c), DOG);      }
                c @ b'c' | c @ b'C' => { chess_id = get_chess_id(get_role(c), CAT);      }
                c @ b'r' | c @ b'R' => { chess_id = get_chess_id(get_role(c), RAT);      }
                n @ b'1' ..= b'9'   => { pos += (n - b'0') as usize; }
                b'/' => { }
                b' ' => { break; }
                _    => { unreachable!() }
            }
    
            if chess_id != EMPTY {
                self.chesses[pos / COL_NUM][pos % COL_NUM] = chess_id;
                pos += 1;
            }
            fen_idx += 1;
        }
        fen_idx += 1; // eat ' '
        self.role = if fen_u8[fen_idx] == b'w' { RED }
                    else { BLACK };
    
    }
    

    c @ b'e' | c @ b'E' => { chess_id = get_chess_id(get_role(c), ELEPHANT); }这句表达了若为e或者E,则通过颜色来得到对应的棋子 id 。可惜 Rust 目前还不支持这种写法:c @ (b'e' | b'E'),目前 or-patterns syntax is experimental,暂时这么写了。

    lambda 表达式

    let get_role = |c: u8| -> Role {
    	if (c as char).is_lowercase() { BLACK }
    	else { RED }
    };
    

    lambda表达式封装get_role来通过字符大小写判断红黑色,避免重复代码,因为这个函数只有内部使用,没必要封装成一个单独函数。

    迭代器

    Rust 的迭代器也很爽,目前 C++ 20 的std::views也简化了这种操作,看看例子。

    来看看基本走法的生成,也就是只能走十字,每次只能走一格,老鼠可以进河。

    fn generate_basic_steps(&self, src: POS, to_water: bool) -> Vec<MOVE> {
        const DX: [i32; 4] = [1, 0, -1, 0];
        const DY: [i32; 4] = [0, 1, 0, -1];
        let src_ = get_pos(src);
        let (x, y) = (src_.0 as i32, src_.1 as i32);
    
        (0..4).into_iter().map(|idx| {
            to_move(&(get_pos(src), ((x + DX[idx]) as usize, (y + DY[idx]) as usize)))
        }).filter(|&mv| {
            let (_, dst) = get_move(mv);
            dst.0 < ROW_NUM && dst.1 < COL_NUM &&
            self.check_movable(src, get_dst_pos(mv)) &&
            (! Self::check_in_water(to_pos(&dst)) || to_water)
        }).collect()
    }
    

    (0..4).into_iter()生成[0,4)的 range,然后基于 range 做计算。

    通过idx得到四个方向的坐标,生成(src, dst)移动向量。

    .map(|idx| {
        to_move(&(get_pos(src), ((x + DX[idx]) as usize, (y + DY[idx]) as usize)))
    })
    

    过滤四个方向,只有在范围内、可以吃掉对方、能过河的结果保留下来:

    .filter(|&mv| {
        let (_, dst) = get_move(mv);
        dst.0 < ROW_NUM && dst.1 < COL_NUM &&
        self.check_movable(src, get_dst_pos(mv)) &&
        (! Self::check_in_water(to_pos(&dst)) || to_water)
    })
    

    接下来是狮子、老虎的走法生成:

    fn generate_tl_steps(&self, src: POS) -> Vec<MOVE> {
        let mut basic_steps = self.generate_basic_steps(src, false);
        let src_ = get_pos(src);
        if Self::check_at_bank(src) {
            // [2, 6]
            if (src_.0 + 2) % 4 == 0 {
                basic_steps.push(to_move(&(src_, ((src_.0 + 4) % 8, src_.1))));
            } else {
                if src_.1 % 6 == 0 {
                    basic_steps.push(to_move(&(src_, (src_.0, 3))));
                } else {
                    basic_steps.push(to_move(&(src_, (src_.0, 0))));
                    basic_steps.push(to_move(&(src_, (src_.0, 6))));
                }
            }
    
            basic_steps = basic_steps.into_iter().filter(|&mv| {
                let (src, dst) = (get_src_pos(mv), get_dst_pos(mv));
                self.check_movable(src, dst) && !self.check_rat(src, dst)
            }).collect()
        }
        basic_steps
    }
    

    首先得到基本走法,然后生成跳河走法。最后的filter过滤无效的移动,例如狮子老虎跳河的时候中间不能有老鼠,对岸的棋子比自己小时。

    basic_steps.into_iter().filter(|&mv| {
        let (src, dst) = (get_src_pos(mv), get_dst_pos(mv));
        self.check_movable(src, dst) && !self.check_rat(src, dst)
    }).collect()
    

    通过迭代器的map可以做类型转换,从而传参给指定类型的接口。例如fn draw_frame(&mut self, tgt_pos: &Vec<POS>)接口,需要的参数类型为Vec<POS>,可实际参数是Vec<MOVE>,通过如下转换:

    fn process_selected_chess(&mut self) -> Result<(), String> {
        if let Some(pos) = self.selected_chess {
            self.draw_frame(&vec![pos])?;
    
            self.movable_pos = self.generate_steps(pos);
            self.draw_frame(&self.movable_pos.iter().map(|&mv| { get_dst_pos(mv) }).collect())?;
        }
        Ok(())
    }
    

    这个接口绘制选中的棋子、以及可移动的格子的框框,self.movable_pos.iter().map(|&mv| { get_dst_pos(mv) }).collect()进行类型转换,只保留dst的坐标。

    Borrow Checker

    Rust 通过借用检查来避免写出不安全的代码:

    • 第一,任何借用必须位于比拥有者更小的作用域
    • 第二,对于同一个资源( resource )的借用,即同一个作用域下,要么只有一个对资源 A 的可变引用(&mut T),要么有 N 个不可变引用(&T),但不能同时存在可变和不可变的引用

    所以如下代码:

    let mut undo = false;
    for event in self.event_pump.poll_iter() {
        match event {
            // ...
            Event::KeyDown { keycode: Some(keycode), .. } => {
                match keycode {
                    Keycode::U      => { undo = true; }
                    _ => {}
                }
            }
            _ => {}
        }
    }
    if undo {
        self.undo_move();
        if self.compture_turn { self.undo_move(); }
    }
    

    不能直接写成:

    for event in self.event_pump.poll_iter() {
        match event {
            // ...
            Event::KeyDown { keycode: Some(keycode), .. } => {
                match keycode {
                    Keycode::U      => {
                        self.undo_move();
                        if self.compture_turn { self.undo_move(); }
                    }
                    _ => {}
                }
            }
            _ => {}
        }
    }
    

    因为self.event_pump.poll_iter()拿到了&mut self,而self.undo_move()也拿到了&mut self,这在 Rust 是绝对不允许的。

    error[E0499]: cannot borrow `*self` as mutable more than once at a time
       --> src/game.rs:440:33
        |
    433 |             for event in self.event_pump.poll_iter() {
        |                          ---------------------------
        |                          |
        |                          first mutable borrow occurs here
        |                          first borrow later used here
    ...
    440 |                                 self.undo_move();
        |                                 ^^^^ second mutable borrow occurs here
    
    error[E0499]: cannot borrow `*self` as mutable more than once at a time
       --> src/game.rs:441:57
        |
    433 |             for event in self.event_pump.poll_iter() {
        |                          ---------------------------
        |                          |
        |                          first mutable borrow occurs here
        |                          first borrow later used here
    ...
    441 |                                 if self.compture_turn { self.undo_move(); }
        |                                                         ^^^^ second mutable borrow occurs here
    

    吐槽

    开发过程还是很爽的,但是也有一些小问题,记录在这。

    cargo publish发布包的时候,没考虑assets的情况,所以cargo install后图片资源没法定位,目前没什么好的方案,所以最好通过下载源代码cargo run的形式来运行。

    相对 C++来说标准库不够完善,很多基本接口都没有,例如std::collections::LinkedList连排序接口都没有,导致只能使用Vec这种简单的数据类型。估计是鼓励用第三方库吧,毕竟 Rust 对依赖处理的很好。

    标准库里的容器没有统一的Trait,导致写不出泛型参数,比如 C++会通过begin()/end()接口来统一类型,C++ 20 有Concepts来约束类型,而 Rust 的链表迭代器Trait都是链表自有的。

    C++代码是这样:

    template<T>
    void process(T& container) {
        for (auto iter = container.begin(); iter != container.end(); iter += 1) {
            // ...
        }
    }
    

    Rust 写不出来:

    fn process<T>(container: &T)
        where T: ??
    {
        for data in container {
        }
    }
    

    关于内存安全性,例如开发过程中数组越界访问了,会导致panic然后挂掉,这应该是最好结果。如果是 C 语言的话,数组越界访问是不会直接挂掉,这就留下了隐患让别有用心的人利用了。

    后续

    接下来要做的是继续优化 AI,可以考虑将 AI 模块分离出来,抽象Trait接口,实现类似于 C++的pImpl模式,也就是策略模式吧。也不知道好不好做,毕竟这两个模块存在相互依赖的关系。

    总的来说用 Rust 写起来很舒服,结合了很多语言的优点,从而有足够的表达力,期待今后发展会越来越好吧。

    通过这个项目也认识到了封装的重要性,哪怕再小的数据结构,封装也有利于维护与演进。例如最初的坐标是(usize, usize),移动向量是((usize, usize), (usize, usize)),通过类型别名POSMOVE,后来分别压缩成u8u16,重构后也没出现过问题。

    第 1 条附言  ·  2020-06-09 22:17:54 +08:00
    后续计划
    - [ ] 分离 game.rsgui.rsboard.rs ,解耦 gui
    - [ ] 添加蒙特卡罗书搜索算法
    27 条回复    2021-10-10 04:45:43 +08:00
    fengjianxinghun
        1
    fengjianxinghun  
       2020-06-07 20:51:47 +08:00
    不错,我最近一直在用 rust 的 async/await 写网络程序,深有同感
    aloxaf
        2
    aloxaf  
       2020-06-07 21:05:43 +08:00
    写的不错呢,回复一下吐槽中的问题:

    > 例如 std::collections::LinkedList 连排序接口都没有

    Rust 推荐大多数情况下使用 Vec 或者 VecDeque,如果你真的遇到了需要链表的场景,那自己写一个通常比标准库提供的通用链表更适合。标准库的链表只是一个吉祥物,没人疼没人爱,别说排序了,连 remove 都是 experimental 状态,完全是不可用状态。

    > 标准库里的容器没有统一的 Trait,导致写不出泛型参数,比如 C++会通过 begin()/end()接口来统一类型,C++ 20 有 Concepts 来约束类型,而 Rust 的链表迭代器 Trait 都是链表自有的。

    ```
    fn process<'a, I>(container: I)
    where
    I: Iterator<Item = &'a i32>,
    {
    for data in container {
    println!("{}", data);
    }
    }

    fn main() {
    process(vec![1, 2, 3].iter());
    }
    ```
    hst001
        3
    hst001  
       2020-06-07 21:07:44 +08:00
    让人怀念的游戏
    netcan
        4
    netcan  
    OP
       2020-06-07 21:18:15 +08:00
    @aloxaf 有个问题,如果不限定 i32 呢?
    fengjianxinghun
        5
    fengjianxinghun  
       2020-06-07 21:23:12 +08:00
    Anthony117
        6
    Anthony117  
       2020-06-07 21:24:11 +08:00 via Android
    已 Star
    fengjianxinghun
        7
    fengjianxinghun  
       2020-06-07 21:24:18 +08:00
    @netcan @aloxaf 你们的都不太泛型。。
    pliex
        8
    pliex  
       2020-06-07 21:25:32 +08:00 via Android
    反手就是一个牛逼
    netcan
        9
    netcan  
    OP
       2020-06-07 21:30:04 +08:00
    @fengjianxinghun 哈哈,我试过 IntoIterator,一开始编译不过去。。可能是因为我入参采用引用而不是移动?
    fengjianxinghun
        10
    fengjianxinghun  
       2020-06-07 21:41:50 +08:00   ❤️ 1
    @netcan 其实还是有一些不够 rust 的地方。。v2 不让我贴代码太无语了。
    netcan
        11
    netcan  
    OP
       2020-06-07 21:46:07 +08:00
    @fengjianxinghun 如果可以的话,直接就地贴吧,学习一下。。
    VDimos
        12
    VDimos  
       2020-06-07 21:50:15 +08:00 via Android
    哈哈,老哥,我在 Reddit 上逮到你了
    VDimos
        13
    VDimos  
       2020-06-07 21:51:54 +08:00 via Android
    @aloxaf std 的链表,这玩意儿真的太鸡肋了
    aloxaf
        14
    aloxaf  
       2020-06-07 21:53:57 +08:00
    @fengjianxinghun 啊,IntoIterator 确实更好,太久没写 Rust 手生了…
    netcan
        15
    netcan  
    OP
       2020-06-07 21:54:32 +08:00
    @VDimos 是啊,标准库还是 C++的好使。。
    qbiloveyou
        16
    qbiloveyou  
       2020-06-07 21:55:39 +08:00 via Android
    太强了
    aloxaf
        17
    aloxaf  
       2020-06-07 22:00:01 +08:00
    @netcan 只是随便举个例子,实际类型该填啥取决于你这个函数需要这个类型满足哪些约束。比如想要对于所有整数类型都适用的话,就可以使用 num-traits 提供的 PrimInt Trait 。
    salamanderMH
        18
    salamanderMH  
       2020-06-07 22:50:01 +08:00
    学习。
    lance6716
        19
    lance6716  
       2020-06-08 00:14:53 +08:00
    @fengjianxinghun

    ```rust
    use std::fmt::Debug;

    fn process<'a, I, T:'a + Debug>(container: I)
    where
    I: Iterator<Item = &'a T>,
    {
    for data in container {
    println!("{:?}", data);
    }
    }

    fn main() {
    process(vec![1, 2].iter());
    process(vec!['a', 'b'].iter())
    }
    ```
    lance6716
        20
    lance6716  
       2020-06-08 00:17:38 +08:00
    dodo2012
        21
    dodo2012  
       2020-06-08 00:20:34 +08:00
    牛 b class
    lance6716
        22
    lance6716  
       2020-06-08 00:20:58 +08:00
    @fengjianxinghun 大晚上的眼花了,把你看成作者了……
    lithbitren
        23
    lithbitren  
       2020-06-08 05:10:33 +08:00
    牛逼,学习了
    netcan
        24
    netcan  
    OP
       2020-06-08 08:56:35 +08:00 via Android
    @lance6716 还是你这个比 Intoterator 好多了
    LaureatePoet
        25
    LaureatePoet  
       2020-06-08 09:02:51 +08:00
    v2ex 上捕捉到学长
    netcan
        26
    netcan  
    OP
       2020-06-09 22:20:07 +08:00
    后续计划
    - [ ] 分离 game.rsgui.rsboard.rs ,解耦 gui
    - [ ] 添加蒙特卡罗树搜索算法
    KennyDiff
        27
    KennyDiff  
       2021-10-10 04:45:43 +08:00 via iPhone
    哈哈哈
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3781 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 00:54 · PVG 08:54 · LAX 17:54 · JFK 20:54
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.