はじめに

ジョブカン事業部のアドベントカレンダー10日目の記事です

9日目の記事は @Larvesta636 さんによる「Cursor & GitHub Copilot でコードレビュー楽していこうぜ」でした。執筆お疲れ様でした。
チームのレビュアー各位は AI によってかなり負荷軽減したのではないでしょうか。私も恩恵を受けています（BIG感謝）

さて、今年は Rust で簡単なゲームを作ってみたくなったので、そこまで難しくないであろう15パズルをテーマにしてみます。
当初はマインスイーパーとかいわゆる落ち物パズルとかを考えていましたが、ロジックの説明だけで記事が長くなりそうなので15パズルにしました（あと私が解けるからです）

そもそも15パズルとは

多くの人が一度は見たことがある定番のスライドパズルです（※個人の感想です）
どんなゲームかを簡単に図を交えて示します

ランダムに配置された数字のタイルをスライドさせて

並べ替える

そんなゲームです。解法をわかってしまえばただの作業ゲーです。

15パズルは4×4の数字タイルが一般的ですが、3×3や画像を使ったものなど派生形も多く存在します。今回はなじみのある「4×4の数字タイル」で実装しました。

環境

言語: Rust 1.91
CPU: x86_64
OS: Arch Linux (VirtualBox)
エディター: Visual Studio Code (Windows 版)

設計

パフォーマンスを最優先させる状況でもなければコアロジック部とそれ以外（描画や操作入力など）を分離できると思っています。今回作る15パズルはパフォーマンス要件がフリーダムなので何も考えず完全にコアロジック部と描画部を分離させます。

とりあえず箱は3つです

※記載したハードウェア名称は一例です。今回は x86_64 アーキテクチャーのPCでのみ動作確認しています

コアロジック部

ゲーム本体です。クレート (ライブラリー) とします
タイル（スライドさせるやつ）の位置操作や完成判定、乱数生成部の呼び出し（シャッフル）をお任せします
標準ライブラリーに依存しないので #[no_std] を指定して30億のデバイスで動作できる状態にします

UI部

ユーザーからの入力をコアロジック部に反映させ、ロジック部の情報を画面出力します
コアロジックとは完全に分離します
抽象化はとても難しいと感じたのでトレイトなどは用意せず、環境に合った実装を都度します

乱数生成部

乱数生成をします
シャッフル時にコアロジック部から呼び出すため依存します
実行環境によって生成方法が変わる可能性があるのでトレイトとして切り出しておきます

実装

実装では以下を意識しました。できるだけ一貫性があるようにします

if を抑える
- 考えることを減らしたいためです（処理は極力ストレートにしたい）
行数を抑える
- 記事にする都合上です
  - unwrap() 多用、 use, where などの記述に統一感のなさもこのせいです
パフォーマンスと可読性なら前者を優先
- コアロジックが遅いのはコアとしてまずいのでパフォーマンス優先です
- チラツキやカクツキを抑えるため描画に係る箇所はパフォーマンス最優先です
- 計算精度が悪くてもパフォーマンスが上がるなら許容します
- なお、最優先事項は執筆の〆切です。執筆中に直したいコードを見つけても頑張って見なかったことにします

説明のためコードは最小限のみ掲載しています。
全文は付録に記載しているのでそちらを参照ください。

コアロジック部

現物の15パズルをそのまま落とし込んだ方がわかりやすいと思ったので、登場人物の紹介を兼ねてクラス図です（メンバーは主要のみ記載）

タイル

Tile は値 (value) をひとつのみ保持する構造体です。値は「本来そのタイルがいるべき場所のインデックス」を格納して、パズルの完成判定にも+1してタイルの数字の描画にも使用します。

pub struct Tile {
    value: usize,
}

ボード

Board は 4×4 の16マスを Option<Tile> の固定長配列で保持する構造体です。
現物の15パズルには「0タイル」が存在しないため、アキマスは None としています（「ないものはない」という考え方です）

二次元配列ではなく一次元配列を採用したのは、型や初期化の記述が楽だからです。

pub struct Board {
    tiles: [Option<Tile>; TILES],
}

加えて、平面座標の取り扱いを簡単にするため Point 構造体も用意しました。

pub struct Point {
    pub x: usize,
    pub y: usize,
}

タイルのスライド処理

タイルのスライドは「アキマスと入れ替える」という考え方で実装しています。
アキマスを探して、移動先が範囲内であれば swap() でタイルを入れ替えます。無駄がなくて良いですね。

fn move_empty(&mut self, dx: i8, dy: i8) -> bool {
    let empty_pos = self.get_empty_pos();

    let added_width: usize = match checked_add_in_range(empty_pos.x, dx, MAX_WIDTH) {
        Some(v) => v,
        None => return false,
    };

    let added_height = match checked_add_in_range(empty_pos.y, dy, MAX_HEIGHT) {
        Some(v) => v,
        None => return false,
    };

    let to = added_height * BOARD_WIDTH + added_width;
    self.swap_tile(empty_pos.to_index(), to); // swap() を呼ぶだけ

    true
}

範囲内であるかの判定で if が大量発生することを回避するため checked_add() みたいな関数を用意しました。0〜指定値の範囲内であれば加算結果、範囲外であれば None を返します。
（全体のコード記述量を削減するために型を調整したらグチャグチャになりました...）

pub fn checked_add_in_range(lhs: usize, rhs: i8, upper_bound: isize) -> Option<usize> {
    let added = lhs as isize + rhs as isize;
    (0 <= added && added <= upper_bound).then(|| added as usize)
}

タイルのスライドは専用メソッドを呼び出して行います。

    pub fn to_up(&mut self) -> bool {
        self.move_empty(0, 1) // タイルを上へ、アキマスを下へ
    }

    pub fn to_down(&mut self) -> bool {
        self.move_empty(0, -1) // タイルを下へ、アキマスを上へ
    }

    pub fn to_left(&mut self) -> bool {
        self.move_empty(1, 0) // タイルを左へ、アキマスを右へ
    }

    pub fn to_right(&mut self) -> bool {
        self.move_empty(-1, 0) // タイルを右へ、アキマスを左へ
    }

ゲーム

Game はボードの初期化、シャッフル、タイル移動、完成判定を担当します。使用する乱数生成器はジェネリクスで受け取り、乱数の実装を知らない状態にします。

pub struct Game<R: Randomize> {
    board: Board,
    random: R,
}

シャッフル処理

単純にシャッフルさせると絶対に解けないパターンが1/2の確率で発生します。これを回避するため「完成状態からランダム方向にスライドさせまくる」という原始的な方法を採用しました。単純明快です。
（数学的に判定する方法があるようですが、よく理解できなかったので採用は見送りました）

移動方向は乱数の下位2bitを参照します。移動方向がランダムなので直近の逆方向の移動（往復）が発生して無駄なので、往復は1/8の確率でのみ許可します。

このとき、逆方向のインデックスは 直近のインデックス XOR 1 で得ています。これにより if を排除できます。

pub const SHUFFLE_STEPS: usize = 65_536; // シャッフル回数。キリの良い回数

const DIRECTIONS: [fn(&mut Board) -> bool; 4] = [
    Board::to_up,
    Board::to_down,
    Board::to_left,
    Board::to_right,
];

fn get_reverse_direction_index(direction_index: usize) -> usize {
    direction_index ^ 0x01 // 下位 1bit を XOR すると逆方向になる (up, down, left, right を前提)
}

fn get_direction(&mut self) -> usize {
    loop {
        let rand = self.random.generate() as usize;
        let direction_index = rand & 0x03; // 下位 2bit を方向に使用

        // 直前の移動方向の逆でなければそのまま返す
        if direction_index != Self::get_reverse_direction_index(self.last_direction_index) {
            return direction_index;
        }

        // 逆方向でもたまには許可する。乱数の bit2～4 がすべて 0 なら許可
        if ((rand >> 2) & 0x07) == 0 {
            return direction_index;
        }

        // 逆方向なら別の方向を生成する
        continue;
    }
}

pub fn shuffle(&mut self) {
    for _ in 0..SHUFFLE_STEPS {
        let direction = self.get_direction();
        if Self::DIRECTIONS[direction](&mut self.board) {
            self.last_direction_index = direction;
        }
    }
}

完成判定

シンプルです。右下が None で、それ以外が順番通りであれば完成していると判断します。

// 最後 (右下) がアキマスでなければ未解決
if self.board.get_empty_pos().to_index() != (TILES - 1) {
    return false;
}

// タイルが正しい位置にないなら未解決
for i in 0..(TILES - 1) {
    let tile = self.board.get_tile_by_index(i);
    if tile.is_none() || tile.unwrap().value() != i {
        return false;
    }
}

乱数生成 (trait)

Randomize トレイトは乱数生成器を抽象化するためのものです。ここでうまく環境の差異を吸収します。

pub trait Randomize {
    type Error;

    fn new() -> Result<Self, Self::Error>
    fn generate(&mut self) -> u8;
}

できました

が、見えません。未確認ですが多分／部分的に15パズルです🧞‍♂️

以下のセクションでは、15パズルとして機能するようにこのクレートを参照する UI を持つアプリを作成します

TUI 化

リッチな GUI を作成する前に動作確認しておきたいので ratatui クレートで TUI (黒と白の画面) 化します。
TUI の名の通りターミナルで動作するので、Amazon EC2 あたりに置いておけば SSH 経由で15パズルできます。

ratatui の採用理由は公式サンプルがかなり映えていたからです。

描画部

ratatui の矩形描画機能を使ってボードとタイルを描画します。
ほぼセオリーに則るだけなので、少しだけ触れるのみにとどめてコードは折りたたんでいます。

TUI では基本単位がピクセルではなく文字 (数) です。
0.5文字のような半端な指定はできないので、数字が2桁になると中央揃えにならず微妙な印象です。
そこで15パズルの "15" にちなんで、タイルの値を16進数表記にして常に1桁表示にしました。

コード (抜粋)

main.rs

fn render(frame: &mut Frame, game: &TuiGame) {
    // セルサイズ (文字数)
    const CELL_WIDTH: u16 = 9;
    const CELL_HEIGHT: u16 = 5;

    // パディング
    const PADDING_WIDTH: u16 = 4;
    const PADDING_HEIGHT: u16 = 2;

    // グリッドサイズ
    const GRID_WIDTH: u16 = (BOARD_WIDTH as u16) * CELL_WIDTH;
    const GRID_HEIGHT: u16 = (BOARD_HEIGHT as u16) * CELL_HEIGHT;
    const OUTER_GRID_WIDTH: u16 = GRID_WIDTH + PADDING_WIDTH * 2;
    const OUTER_GRID_HEIGHT: u16 = GRID_HEIGHT + PADDING_HEIGHT * 2;

    let area = frame.area(); // 画面全体のサイズ

    let offset_x = area.width.saturating_sub(OUTER_GRID_WIDTH);
    let offset_y = area.height.saturating_sub(OUTER_GRID_HEIGHT);
    let outer_rect = Rect {
        x: area.x + offset_x / 2,
        y: area.y + offset_y / 2,
        width: OUTER_GRID_WIDTH,
        height: OUTER_GRID_HEIGHT,
    };

    let mut outer = Block::default()
        .borders(Borders::ALL)
        .border_type(BorderType::Rounded);

    if game.is_solved() {
        outer = outer.title(" Solved!! ").title_alignment(Alignment::Center);
    }

    frame.render_widget(outer, outer_rect);

    // 画面中央に配置
    let grid = Rect {
        x: area.x + area.width.saturating_sub(GRID_WIDTH) / 2,
        y: area.y + area.height.saturating_sub(GRID_HEIGHT) / 2,
        width: GRID_WIDTH,
        height: GRID_HEIGHT,
    };

    // 行を固定長で分割
    let row_chunks = Layout::default()
        .direction(Direction::Vertical)
        .constraints([Constraint::Length(CELL_HEIGHT); BOARD_HEIGHT as usize])
        .split(grid);

    for (r, row) in row_chunks.iter().enumerate() {
        // 各行を固定長で4分割
        let column_chunks = Layout::default()
            .direction(Direction::Horizontal)
            .constraints([Constraint::Length(CELL_WIDTH); BOARD_WIDTH as usize])
            .split(*row);

        for (c, cell_rect) in column_chunks.iter().enumerate() {
            if let Some(tile) = game.board().get_tile_by_pos(c, r) {
                let block = Block::default().borders(Borders::ALL);
                // block を描画させると所有権が移動する (ボローチェッカーが怒る) ので必要な情報を先に得ておく
                let inner = block.inner(*cell_rect);

                // block を描画
                frame.render_widget(block, *cell_rect);

                // 中央揃えの行を作ってそこにラベルを描画
                let label = format!("{:X}", tile.value() + 1);
                let paragraph = Paragraph::new(label).alignment(Alignment::Center);
                let label_area = Rect {
                    x: inner.x,
                    y: inner.y + inner.height.saturating_sub(1) / 2,
                    width: inner.width,
                    height: 1,
                };
                frame.render_widget(paragraph, label_area);
            }
        }
    }
}

乱数部

トレイトを実装するのみです。
乱数生成にはおなじみ rand クレートの ThreadRng::random() を呼ぶだけです。

struct PuzzleRandom {
    rng: rand::rngs::ThreadRng,
}

impl Randomize for PuzzleRandom {
    type Error = (); // 失敗しないので考慮しない

    fn new() -> Result<Self, Self::Error> {
        Ok(Self { rng: rand::rng() })
    }

    fn generate(&mut self) -> u8 {
        self.rng.random()
    }
}

入力部

キー入力を受け付けます。 ratatui ならお手軽に実装できます。

タイルは方向キーの入力に従ってスライドします。
方向キーが未搭載のキーボードでも遊べるように wasd と hjkl にも対応しました

match key.code {
    KeyCode::Up | KeyCode::Char('k') | KeyCode::Char('w') if can_move => game.move_up(),
    KeyCode::Down | KeyCode::Char('j') | KeyCode::Char('s') if can_move => game.move_down(),
    KeyCode::Left | KeyCode::Char('h') | KeyCode::Char('a') if can_move => game.move_left(),
    KeyCode::Right | KeyCode::Char('l') | KeyCode::Char('d') if can_move => game.move_right(),
    KeyCode::Char('n') => game.new_game(), // r だと誤爆しそうなので
    _ => {}
}

できました

スクショは Windows のターミナルアプリ (PowerShell) から SSH で Arch Linux に接続して cargo run した結果です

パズル完成時

外枠の上辺に Solved!! と表示します。アキマスを 10 (16進数表記) として埋める演出をよく見かけるのでマネしようと思いましたが、どうしても2桁を表示したくなかったので、このような演出になりました。
あと、サンプルコードを良い感じに流用できるからです。

グラフィカルにする

TUI 化までできたら GUI にしたいですね。

話は逸れますが、15パズルをするために OS を起動する必要があるのかと常々考えていました。

――そうだ、 UEFI アプリにしよう

※ UEFI アプリとは UEFI が起動している状態で動作するアプリのことです。ブートローダーや設定ツール（いわゆる BIOS 設定画面）もその仲間です。

これ以降ハード寄りになりますが、お付き合いいただけると幸いです。

追加のクレートなど

uefi クレートと x86_64-unknown-uefi ターゲット向けのツールチェーンがあれば OK です。また uefi-run もインストールしておくと QEMU による動作確認が容易です。
加えて、色を扱うので rgb クレートも追加しています。

uefi-run は以下のコマンドラインでインストールできます。

cargo install uefi-run

このセクションではグラフィカルに動作するアプリを作成するので、動作確認するにあたり QEMU はデスクトップ版だと確認しやすいです。聞きなじみがないかもしれませんが QEMU で UEFI を起動するために OVMF も必要です。もし Arch Linux をお使いでしたら以下のコマンドラインでインストールできます。

sudo pacman -S qemu-desktop edk2-ovmf

その後 OVMF ファイル（とりあえず）ホームディレクトリー直下に置いておきます。
※ ディストリビューションによってコピー元のパスやファイル名が異なる場合があります。

cp /usr/share/edk2/x64/OVMF.4m.fd ~/.

GUI 実装

GUI と言っていますがウィンドウやボタンはなくマウスカーソルすら出てきません。
ただグラフィカルに15パズルを表示するだけです。ご容赦下さい。

前提として

UEFI と聞くと「あれって BIOS の進化形みたいなものだけどテキストしか扱えないのでは？」と思われるかもしれませんが、標準でグラフィカルな画面を扱う Graphics Output Protocol (以下 GOP) という機能が提供されているのでこちらを使用します。
ちなみにテキスト出力は Simple Text Output Protocol です。

描画周り

uefi クレートを使ってフレームバッファー (VRAM) の参照を得ることができるので、ここにデータを設定すると任意の画像を描画することができます。書き込むと即座に画面へ反映されます。再描画命令などは一切不要です。

UEFI の仕様によれば 1px あたりのデータサイズは 32bit (4バイト) です。が、そのうち 8bit は未使用 (UEFI 実装依存) なので触れないでおきます (なので実質 24bpp ビットマップです)
その4バイトにどの順番で色情報を持たせるかは RGB または BGR となります。ちなみに QEMU は BGR っぽいです。これはエンディアンの話ではなく1ピクセルの u32 にどの順番で色情報を格納するか、という話です。

ビットマップファイルについて

普通に数字を描くならフォント API で描画しますが GOP にはフォントの概念がありません。
そのため、タイルの数字を描画するには自前でビットマップデータを用意して画面に描画する必要があります。

アセットの埋め込み

以下のように include_bytes!() を使うと指定したファイルを埋め込むこと（コンパイル時展開）ができます

（つまりファイルシステムの実装が不要です。これは大変な偉業です）

// タイルに表示する文字の画像 (8bpp, グレースケール, ボトムアップ)
static DIGITS_BMP8: &[u8] = include_bytes!("../../assets/tiles.bmp");

なお、コメントの丸括弧内は今回の実装で期待するビットマップファイルの形式です。

データを準備する

ビットマップデータは Windows のペイントでも Vim+xxd でもお好きなツールでどうぞ。ただし、前述のとおり以下の形式で出力してください。

8bpp (256色インデックスカラー)
グレースケール（必須ではないが推奨程度）
ボトムアップ
無圧縮

24bpp はダイレクトカラーなので扱いやすそうですがバイナリサイズ削減のためインデックスカラーの 8bpp としています。今日のストレージ事情なら誤差の範囲ですがビルドや起動の高速化が見込めます。これは開発中でも恩恵があるのでうれしみポイントです。

今回は黒を透過色として半透明合成を行います。白を透明色にしなかったのはダークモード慣れしすぎて広範囲に白色があると目が痛むからです。半透明合成の処理ついては後述します。

パース

当然のように UEFI は「ビットマップファイル」を理解できないので自前でパースします。今回は記事にする都合上、先に示した入力形式以外や壊れたデータは panic とします（噂によると、一部の UEFI 実装ではビットマップファイルをパースできるらしいです）

BITMAPFILEHEADER 構造体と BITMAPINFOHEADER 構造体を参考にビットマップファイルの縦横 (width, height) を取得します。また、1行あたりのバイト数 (row_bytes) は4の倍数でなければならないので切り上げ処理を入れています。例えば 8bpp で幅 17px なら1行あたりのバイト数は20となります

蛇足

この仕様は古い Windows から続くもので、古文書に以下の記載があります。

The bitmap formats currently used are monochrome and color. The monochrome bitmap uses a one-bit, one-plane format. Each scan is a multiple of 32 bits.

引用元: Visual Studio 6.0 付属の MSDN より BITMAP (GDI: Platform SDK)

日本語版だと 16bit のままでした。これは Windows 3.1 SDK ヘルプから記述がほぼ変わっていません。

現在使われているビットマップの形式はモノクロとカラーです。モノクロのビットマップは、1 ビット、1 プレーンの形式を使います。各スキャンは 16 ビットの倍数です。

引用元: Visual Studio 6.0 付属の MSDN より BITMAP 構造体 (Microsoft Foundation Class リファレンス)

Windows 3.1 → Windows 95 / Windows NT 4 の時代背景が見え隠れしていて興味深いポイントです。

let width = Self::read_u32(data, BF_OFF_BITS_OFFSET + 8);
let height = Self::read_u32(data, BF_OFF_BITS_OFFSET + 8 + 4);
let row_bytes = (width + 3) & !0x03; // 4byte アライメント

同じような感じでパレットやビットマップデータの参照を取得します。

ピクセルオーダー

UEFI のフレームバッファーは1ピクセルを4バイト (u32) で保持しますが、内訳は RGB 順か BGR 順かは実装に依存します。これを描画の度に条件分岐して必要に応じて R⇔B 入れ替えなんてことをしていたら遅いし、コードが読みづらくなりそうです。今回は PixelOrder トレイトで抽象化して分岐を排除しています。

rgb クレートはここで活躍します。なんと BGR も対応していて into() すれば RGB8 に大変身です。すごいよね。

trait PixelOrder {
    fn from_rgb(r: u8, g: u8, b: u8) -> RGB8;
}

struct RgbOrder;
impl PixelOrder for RgbOrder {
    fn from_rgb(r: u8, g: u8, b: u8) -> RGB8 {
        RGB8::new(r, g, b)
    }
}

struct BgrOrder;
impl PixelOrder for BgrOrder {
    fn from_rgb(r: u8, g: u8, b: u8) -> RGB8 {
        BGR8::new_bgr(b, g, r).into()
    }
}

アルファ合成 (半透明合成)

前述の通り今回扱うビットマップは 8bpp グレースケールを想定します。正確には RGB で最も高い輝度をアルファ値とします。よって、黒=透明、白=不透明、中間=アルファ値となります。

アルファ合成をしている理由は数字のエッジをなめらかに描画させるためです。

アルファ合成自体は難しくありませんが、ビット演算のみで実現させるロマンを追い求めて固定小数点演算を採用しているため、記述がややこしくなっています。
FPUがない環境や、浮動小数点演算が激遅な環境下でも爆速でアルファ合成をします（精度は多少犠牲にします）

fn calc_alpha(color: u8, dest: u8, alpha: u8) -> u8 {
    const HALF: i32 = 1 << (u8::BITS - 1); // 四捨五入の0.5。Q0.8
    let c = (color as i32) * (alpha as i32) + (dest as i32) * (u8::MAX as i32 - (alpha as i32)); // アルファ合成の計算本体。Q9.8
    let r = c + HALF; // 四捨五入用の 0.5 を加算。Q9.8
    ((r + (r >> u8::BITS)) >> u8::BITS) as u8 // (color * alpha + dest * (255 - alpha)) / 255 相当。Q8.0
}

キャッシュ

タイルの数字を描画の度に合成していたら遅すぎるので、数字と背景を合成したタイル画像を起動時に用意します
（ダブルバッファリングとも違うし、スプライトは違うし...なので「キャッシュ」としました）

for i in 0..TILES {
    let mut ctx = TileCtx::<T>::new_for_index(i);
    let (sx, sy, sw_cell, sh_cell) = get_glyph_by_index(bmp, i);
    ctx.clear(RGB8::new(162, 204, 204));
    ctx.bitblt_bmp8_with_alpha(/* 省略 */);
}

描画部

GOP に直線や矩形などを描画する API は存在しないので、自力で書く (描く) 必要があります。ワクワクしますね。

ブラシ

塗りつぶしに使う色を保持する構造体です。
なお、Hatch はありません。今回は Solid で十分です。

struct Brush {
    color: RGB8,
}

情報保持

画像サイズや選択中のブラシなどを保持する構造体です。
後述の各コンテキストは同じ情報を持つので共通化しています。

struct CtxInfo {
    pub width: usize,
    pub height: usize,
    pub stride: usize,
    pub current_brush: Brush,
}

描画処理（トレイト）

描画処理のトレイトです。
後述の各コンテキスト側で差異を吸収して、描画処理そのものはトレイトに記述して共通化しています。

trait GraphicCtx<T: PixelOrder> {
    fn clear(&mut self, color: RGB8);
    fn set_pixel(&mut self, x: usize, y: usize, color: RGB8);
    fn select_brush(&mut self, brush: Brush) -> Brush;
    fn draw_rectangle(&mut self, x: usize, y: usize, width: usize, height: usize);
    fn bitblt<Ctx: GraphicCtx<T>>(
        &mut self,
        x: usize,
        y: usize,
        width: usize,
        height: usize,
        src: &Ctx,
        src_x: usize,
        src_y: usize,
    );
}

フレームバッファーコンテキスト

描画処理の実装です。こちらの描画先は UEFI のフレームバッファーです。

struct GopCtx<T: PixelOrder> {
    frame_buffer: &'static mut [u8],
    info: CtxInfo,
}

タイルコンテキスト

描画処理の実装です。こちらの描画先はタイル画像 (キャッシュ) です。

struct TileCtx<T: PixelOrder> {
    buffer: *mut u8,
    info: CtxInfo,
}

画面クリアー

UEFI は1ピクセルあたり 4バイト (u32) が大前提なので memset() しています。
未測定ですが無駄がないので超高速だと思います。

fn clear(&mut self, color: RGB8) {
    let (_, pixels, _) = unsafe { self.raw_buffer_mut().align_to_mut::<u32>() };
    pixels.fill(T::to_u32(color)); // memset() / FillMemory() 相当
}

ブラシ選択

矩形描画でしか使っていませんが、塗りつぶしの色を設定します。
mem::replace() を使うと無駄なく変数の内容を入れ替えられます。最高ですね。

fn select_brush(&mut self, brush: Brush) -> Brush {
    mem::replace(&mut self.current_brush_mut(), brush)
}

さっきから既視感がある？さて何のことやら...

矩形描画

矩形を選択されたブラシの色で塗りつぶします。初期の実装がそのままになっているので clear() や bitblt() よりもシンプルでわかりやすい実装になっています。

let brush_color = self.current_brush().color();
for j in y..(y + height) {
    for i in x..(x + width) {
        self.set_pixel(i, j, brush_color);
    }
}

画像転送

指定した画像を別の場所にコピーする処理です。
とにかくパフォーマンス優先として、わかりやすさはどこかに置いてきました。

なんだか仰々しいような気がしますが、指定した領域を1行ずつ memcpy() しているだけです。

fn bitblt<Ctx: GraphicCtx<T>>(
    &mut self,
    x: usize,
    y: usize,
    width: usize,
    height: usize,
    src: &Ctx,
    src_x: usize,
    src_y: usize,
) {
    let bpp = self.bytes_per_pixel();
    let row_bytes = width * bpp;
    for row in 0..height {
        let src_offset = ((src_y + row) * src.stride() + src_x) * src.bytes_per_pixel();
        let dest_offset = ((y + row) * self.stride() + x) * bpp;
        let src_slice = &src.raw_buffer()[src_offset..src_offset + row_bytes];
        let dest_slice = &mut self.raw_buffer_mut()[dest_offset..dest_offset + row_bytes];
        dest_slice.copy_from_slice(src_slice);
    }
}

入力部

TUI と同じくキー入力によりタイルを動かせるようにします。
UEFI の Simple Text Input (Ex) を明示的に呼ぶ必要はなく uefi クレート側でよしなにやってくれます。

if let Ok(Some(key)) = input.read_key() {
    match key {
        Key::Printable(c) => match c.into() {
            'k' | 'w' if can_move => session.game.move_up(),
            'j' | 's' if can_move => session.game.move_down(),
            'h' | 'a' if can_move => session.game.move_left(),
            'l' | 'd' if can_move => session.game.move_right(),
            'n' => session.game.new_game(), // r だと誤爆しそうなので
            _ => {}
        },
        Key::Special(scan) => match scan {
            ScanCode::UP if can_move => session.game.move_up(),
            ScanCode::DOWN if can_move => session.game.move_down(),
            ScanCode::LEFT if can_move => session.game.move_left(),
            ScanCode::RIGHT if can_move => session.game.move_right(),
            _ => {}
        },
    }
}

乱数部

Rust で乱数といえば rand クレートですが #[no_std] かつ UEFI ターゲットではそのまま使えない可能性がありました。なので UEFI の乱数生成 API を呼び出して乱数を得るようにします。
設計段階で乱数生成ロジックを抽象化していたので UEFI 固有の処理をここに閉じ込められます。効果は抜群ですね。

当初は TPM に乱数生成をお任せするつもりでしたが QEMU で上手くいかなかったので泣く泣く UEFI にお願いする方針にしました。
※ TPM (Trusted Platform Module) ... Windows 11 で必須ハードウェア要件になったセキュリティのアレです。

struct UefiRandom {
    buffer: [u8; SHUFFLE_STEPS - 1], // 1ずらして New Game 時に参照先を変える
    index: usize,
}

impl puzzle_core::Randomize for UefiRandom {
    type Error = uefi::Error;
}

なんか遅い？

UEFI の乱数生成 API は IO を伴うため、大量に呼ぶと露骨に遅くなります (panic を疑うほど)
そこで、初期化時に乱数をまとめて取得→乱数テーブルとして自前で持つようにしました。 generate() ではテーブルを参照するだけなので数万回呼んでも気にならないほど高速です。

impl puzzle_core::Randomize for UefiRandom {
    fn new() -> Result<Self, Self::Error> {
        // 省略
        let mut buffer = [0u8; SHUFFLE_STEPS - 1];
        scoped_rng.get_rng(None, &mut buffer)?; // かなり遅いので初期化時に一度だけ呼んで乱数テーブルを作る
        Ok(Self { buffer, index: 0 })
    }

    fn generate(&mut self) -> u8 {
        let value = self.buffer[self.index];
        self.index = match checked_add_in_range(self.index, 1, (self.buffer.len() - 1) as isize) {
            Some(v) => v,
            None => 0,
        };
        value
    }
}

動作確認

ビルドします。

cargo build --release --target=x86_64-unknown-uefi

QEMU で実行します（パスは適宜変更してください）

uefi-run -b ~/OVMF.4m.fd target/x86_64-unknown-uefi/release/slide-puzzle-uefi.efi -- -serial mon:stdio -device virtio-rng-pci

動きました

パズル完成時

アキマスに16のタイルを表示します。こちらは描画の自由度が高いので、よく見かける 16 のタイルを描画して埋める演出としています。

感想

Rust でゲーム制作を完遂させたのも #[no_std] という制約強めのストロングスタイルで開発したのも今回が初なので、どこかで心が折れるのではないかと内心ヒヤヒヤでした。

計画ではスライド時にアニメーションさせるつもりでしたが、時間の都合で今回は断腸の思いで見送りました。

UEFI は標準で多様な API を提供していて色々遊べそうです。この記事を読んで意外とできそうと思ったら是非 UEFI アプリ開発をしてみてください。

さいごに

DONUTSでは一緒に働くメンバーを募集しています。
今年やこれまでのアドベントカレンダーをご覧になって「ここで働いてみたい」、「自分ならプロダクトをもっとよくできる」などジョインしたいという想いがありましたら、以下のページをご覧ください。お待ちしております。

明日の記事は @osakanabokujo さんによる「Docker Desktop MCP toolkitでMCPサーバーを管理しよう！」です。技術レイヤーが UEFI から MCP に急上昇しますが Docker と MCP で何ができるようになるのか楽しみですね。

長くなりましたが記事は以上です。鳩 (@djwq) でした。

付録

コード全文と画像データです

コアロジック

Cargo.toml

Cargo.toml

[package]
name = "puzzle_core"
version = "0.1.0"
edition = "2024"

[lib]
doctest = false

lib.rs

lib.rs

#![no_std]

pub const SHUFFLE_STEPS: usize = 65_536; // シャッフル回数。キリの良い回数

pub trait Randomize {
    type Error;

    fn new() -> Result<Self, Self::Error>
    where
        Self: Sized;
    fn generate(&mut self) -> u8;
}

#[derive(Copy, Clone)]
pub struct Tile {
    value: usize,
}

impl Tile {
    pub fn new(value: usize) -> Self {
        Self { value }
    }

    pub fn value(&self) -> usize {
        self.value
    }
}

pub const BOARD_WIDTH: usize = 4;
pub const BOARD_HEIGHT: usize = 4;
pub const TILES: usize = BOARD_WIDTH * BOARD_HEIGHT;

pub fn checked_add_in_range(lhs: usize, rhs: i8, upper_bound: isize) -> Option<usize> {
    let added = lhs as isize + rhs as isize;
    (0 <= added && added <= upper_bound).then(|| added as usize)
}

pub struct Point {
    pub x: usize,
    pub y: usize,
}

impl Point {
    pub fn new(x: usize, y: usize) -> Self {
        Self { x, y }
    }

    pub fn new_from_index(index: usize) -> Self {
        Self::new(index % BOARD_WIDTH, index / BOARD_WIDTH)
    }

    pub fn to_index(&self) -> usize {
        self.y * BOARD_WIDTH + self.x
    }
}

pub struct Board {
    tiles: [Option<Tile>; TILES],
}

impl Board {
    pub fn new() -> Self {
        let mut tiles = [None; TILES];
        for i in 0..(TILES - 1) {
            tiles[i] = Some(Tile::new(i));
        }
        tiles[TILES - 1] = None;

        Self { tiles }
    }

    pub fn get_tile_by_index(&self, index: usize) -> Option<&Tile> {
        self.tiles[index].as_ref()
    }

    pub fn get_tile_by_pos(&self, x: usize, y: usize) -> Option<&Tile> {
        let index = y * BOARD_WIDTH + x;
        self.get_tile_by_index(index)
    }

    fn get_empty_pos(&self) -> Point {
        Point::new_from_index(self.tiles.iter().position(|e| e.is_none()).unwrap())
    }

    fn swap_tile(&mut self, from: usize, to: usize) {
        self.tiles.swap(from, to);
    }

    fn move_empty(&mut self, dx: i8, dy: i8) -> bool {
        const MAX_WIDTH: isize = (BOARD_WIDTH - 1) as isize;
        const MAX_HEIGHT: isize = (BOARD_HEIGHT - 1) as isize;

        let empty_pos = self.get_empty_pos();

        let added_width: usize = match checked_add_in_range(empty_pos.x, dx, MAX_WIDTH) {
            Some(v) => v,
            None => return false,
        };

        let added_height = match checked_add_in_range(empty_pos.y, dy, MAX_HEIGHT) {
            Some(v) => v,
            None => return false,
        };

        let to = added_height * BOARD_WIDTH + added_width;
        self.swap_tile(empty_pos.to_index(), to);

        true
    }

    pub fn to_up(&mut self) -> bool {
        self.move_empty(0, 1) // タイルを上へ、アキマスを下へ
    }

    pub fn to_down(&mut self) -> bool {
        self.move_empty(0, -1) // タイルを下へ、アキマスを上へ
    }

    pub fn to_left(&mut self) -> bool {
        self.move_empty(1, 0) // タイルを左へ、アキマスを右へ
    }

    pub fn to_right(&mut self) -> bool {
        self.move_empty(-1, 0) // タイルを右へ、アキマスを左へ
    }
}

pub struct Game<R: Randomize> {
    board: Board,
    random: R,
    last_direction_index: usize,
}

impl<R> Game<R>
where
    R: Randomize,
{
    const DIRECTIONS: [fn(&mut Board) -> bool; 4] = [
        Board::to_up,
        Board::to_down,
        Board::to_left,
        Board::to_right,
    ];
    const INITIAL_LAST_DIRECTION_INDEX: usize = 1; // 最終入力が move_down だったことにする

    pub fn new() -> Result<Self, R::Error> {
        Ok(Self {
            board: Board::new(),
            random: R::new()?,
            last_direction_index: Self::INITIAL_LAST_DIRECTION_INDEX,
        })
    }

    pub fn board(&self) -> &Board {
        &self.board
    }

    pub fn board_mut(&mut self) -> &mut Board {
        &mut self.board
    }

    pub fn reset(&mut self) {
        self.board = Board::new();
        self.last_direction_index = Self::INITIAL_LAST_DIRECTION_INDEX;
    }

    pub fn new_game(&mut self) {
        self.reset();
        self.shuffle();
    }

    pub fn move_up(&mut self) {
        self.board.to_up();
    }

    pub fn move_down(&mut self) {
        self.board.to_down();
    }

    pub fn move_left(&mut self) {
        self.board.to_left();
    }

    pub fn move_right(&mut self) {
        self.board.to_right();
    }

    fn get_reverse_direction_index(direction_index: usize) -> usize {
        direction_index ^ 0x01 // 下位 1bit を XOR すると逆方向になる (up, down, left, right を前提)
    }

    fn get_direction(&mut self) -> usize {
        loop {
            let rand = self.random.generate() as usize;
            let direction_index = rand & 0x03; // 下位 2bit を方向に使用

            // 直前の移動方向の逆でなければそのまま返す
            if direction_index != Self::get_reverse_direction_index(self.last_direction_index) {
                return direction_index;
            }

            // 逆方向でもたまには許可する。乱数の bit2～4 がすべて 0 なら許可
            if ((rand >> 2) & 0x07) == 0 {
                return direction_index;
            }

            // 逆方向なら別の方向を生成する
            continue;
        }
    }

    pub fn shuffle(&mut self) {
        for _ in 0..SHUFFLE_STEPS {
            let direction = self.get_direction();
            if Self::DIRECTIONS[direction](&mut self.board) {
                self.last_direction_index = direction;
            }
        }
    }

    pub fn is_solved(&self) -> bool {
        // 最後 (右下) がアキマスでなければ未解決
        if self.board.get_empty_pos().to_index() != (TILES - 1) {
            return false;
        }

        // タイルが正しい位置にないなら未解決
        for i in 0..(TILES - 1) {
            let tile = self.board.get_tile_by_index(i);
            if tile.is_none() || tile.unwrap().value() != i {
                return false;
            }
        }

        true
    }
}

TUIアプリ

Cargo.toml

Cargo.toml

[package]
name = "cli"
version = "0.1.0"
edition = "2024"

[dependencies]
anyhow = "1.0.100"
color-eyre = "0.6.5"
puzzle_core = { version = "*", path = "../core" }
crossterm = "0.29.0"
rand = "0.9.2"
ratatui = "0.29.0"

main.rs

main.rs

use crossterm::{
    event::{self, Event, KeyCode, KeyEvent},
    execute, terminal,
};
use rand::Rng;
use ratatui::{
    prelude::*,
    widgets::{Block, BorderType, Borders, Paragraph},
};

use puzzle_core::{BOARD_HEIGHT, BOARD_WIDTH, Game, Randomize};

struct PuzzleRandom {
    rng: rand::rngs::ThreadRng,
}

impl Randomize for PuzzleRandom {
    type Error = (); // 失敗しないので考慮しない

    fn new() -> Result<Self, Self::Error> {
        Ok(Self { rng: rand::rng() })
    }

    fn generate(&mut self) -> u8 {
        self.rng.random()
    }
}

type TuiGame = Game<PuzzleRandom>; // 長いので型エイリアスを用意

fn main() -> anyhow::Result<()> {
    let mut game = TuiGame::new().unwrap();
    game.new_game();

    // 端末セットアップ
    terminal::enable_raw_mode()?;
    let mut out = std::io::stdout();
    execute!(out, terminal::EnterAlternateScreen)?;
    let backend = CrosstermBackend::new(out);
    let mut term = Terminal::new(backend)?;

    let result = game_loop(&mut term, &mut game); // ゲームループ

    // 後始末
    terminal::disable_raw_mode()?;
    execute!(std::io::stdout(), terminal::LeaveAlternateScreen)?;

    result
}

fn game_loop(
    term: &mut Terminal<CrosstermBackend<std::io::Stdout>>,
    game: &mut TuiGame,
) -> anyhow::Result<()> {
    loop {
        term.draw(|f| render(f, game))?;

        if event::poll(std::time::Duration::from_millis(50))? {
            if let Event::Key(k) = event::read()? {
                match k.code {
                    KeyCode::Esc | KeyCode::Enter => break,
                    _ => handle_key_event(k, game),
                }
            }
        }
    }

    Ok(())
}

fn handle_key_event(key: KeyEvent, game: &mut TuiGame) {
    let can_move = !game.is_solved();

    match key.code {
        KeyCode::Up | KeyCode::Char('k') | KeyCode::Char('w') if can_move => game.move_up(),
        KeyCode::Down | KeyCode::Char('j') | KeyCode::Char('s') if can_move => game.move_down(),
        KeyCode::Left | KeyCode::Char('h') | KeyCode::Char('a') if can_move => game.move_left(),
        KeyCode::Right | KeyCode::Char('l') | KeyCode::Char('d') if can_move => game.move_right(),
        KeyCode::Char('n') => game.new_game(), // r だと誤爆しそうなので
        _ => {}
    }
}

fn render(frame: &mut Frame, game: &TuiGame) {
    // セルサイズ (文字数)
    const CELL_WIDTH: u16 = 9;
    const CELL_HEIGHT: u16 = 5;

    // パディング
    const PADDING_WIDTH: u16 = 4;
    const PADDING_HEIGHT: u16 = 2;

    // グリッドサイズ
    const GRID_WIDTH: u16 = (BOARD_WIDTH as u16) * CELL_WIDTH;
    const GRID_HEIGHT: u16 = (BOARD_HEIGHT as u16) * CELL_HEIGHT;
    const OUTER_GRID_WIDTH: u16 = GRID_WIDTH + PADDING_WIDTH * 2;
    const OUTER_GRID_HEIGHT: u16 = GRID_HEIGHT + PADDING_HEIGHT * 2;

    let area = frame.area(); // 画面全体のサイズ

    let offset_x = area.width.saturating_sub(OUTER_GRID_WIDTH);
    let offset_y = area.height.saturating_sub(OUTER_GRID_HEIGHT);
    let outer_rect = Rect {
        x: area.x + offset_x / 2,
        y: area.y + offset_y / 2,
        width: OUTER_GRID_WIDTH,
        height: OUTER_GRID_HEIGHT,
    };

    let mut outer = Block::default()
        .borders(Borders::ALL)
        .border_type(BorderType::Rounded);

    if game.is_solved() {
        outer = outer.title(" Solved!! ").title_alignment(Alignment::Center);
    }

    frame.render_widget(outer, outer_rect);

    // 画面中央に配置
    let grid = Rect {
        x: area.x + area.width.saturating_sub(GRID_WIDTH) / 2,
        y: area.y + area.height.saturating_sub(GRID_HEIGHT) / 2,
        width: GRID_WIDTH,
        height: GRID_HEIGHT,
    };

    // 行を固定長で分割
    let row_chunks = Layout::default()
        .direction(Direction::Vertical)
        .constraints([Constraint::Length(CELL_HEIGHT); BOARD_HEIGHT as usize])
        .split(grid);

    for (r, row) in row_chunks.iter().enumerate() {
        // 各行を固定長で4分割
        let column_chunks = Layout::default()
            .direction(Direction::Horizontal)
            .constraints([Constraint::Length(CELL_WIDTH); BOARD_WIDTH as usize])
            .split(*row);

        for (c, cell_rect) in column_chunks.iter().enumerate() {
            if let Some(tile) = game.board().get_tile_by_pos(c, r) {
                let block = Block::default().borders(Borders::ALL);
                // block を描画させると所有権が移動する (ボローチェッカーが怒る) ので必要な情報を先に得ておく
                let inner = block.inner(*cell_rect);

                // block を描画
                frame.render_widget(block, *cell_rect);

                // 中央揃えの行を作ってそこにラベルを描画
                let label = format!("{:X}", tile.value() + 1);
                let paragraph = Paragraph::new(label).alignment(Alignment::Center);
                let label_area = Rect {
                    x: inner.x,
                    y: inner.y + inner.height.saturating_sub(1) / 2,
                    width: inner.width,
                    height: 1,
                };
                frame.render_widget(paragraph, label_area);
            }
        }
    }
}

GUIアプリ

Cargo.toml

Cargo.toml

[package]
name = "slide-puzzle-uefi"
version = "0.1.0"
edition = "2024"

[dependencies]
rgb = { version = "0.8.52", default-features = false }
uefi = { version = "0.36.1", default-features = false }
puzzle_core = { version = "*", path = "../core" }


[profile.release]
lto = true
codegen-units = 1
panic = "abort"

main.rs

main.rs

#![no_std]
#![no_main]

use core::marker::PhantomData;
use core::{mem, panic, ptr, slice};
use puzzle_core::{BOARD_HEIGHT, BOARD_WIDTH, SHUFFLE_STEPS, TILES, checked_add_in_range};
use rgb::RGB8;
use rgb::alt::BGR8;
use uefi::prelude::*;
use uefi::proto::console::gop::{GraphicsOutput, ModeInfo, PixelFormat};
use uefi::proto::console::text::{Input, Key, ScanCode};
use uefi::proto::rng::Rng;

const BORDER_WIDTH: usize = 36;
const BORDER_HEIGHT: usize = 36;
const BASE_BPP: usize = 4; // UEFI を前提とする

const GLYPH_WIDTH: usize = 128;
const GLYPH_HEIGHT: usize = 128;
const TILE_WIDTH: usize = GLYPH_WIDTH;
const TILE_HEIGHT: usize = GLYPH_HEIGHT;
const TILE_BUFFER_SIZE: usize = TILE_WIDTH * TILE_HEIGHT * BASE_BPP;

type UefiGame = puzzle_core::Game<UefiRandom>; // 長いので型エイリアスを用意

// タイルに表示する文字の画像 (8bpp, グレースケール, ボトムアップ)
static DIGITS_BMP8: &[u8] = include_bytes!("../../assets/tiles.bmp");
static mut TILE_BUFFER: [[u8; TILE_BUFFER_SIZE]; TILES] = [[0; TILE_BUFFER_SIZE]; TILES];

struct UefiRandom {
    buffer: [u8; SHUFFLE_STEPS - 1], // 1ずらして New Game 時に参照先を変える
    index: usize,
}

impl puzzle_core::Randomize for UefiRandom {
    type Error = uefi::Error;

    fn new() -> Result<Self, Self::Error> {
        let h_rng = match boot::get_handle_for_protocol::<Rng>() {
            Ok(h) => h,
            Err(e) => return Err(e),
        };

        let mut scoped_rng = match boot::open_protocol_exclusive::<Rng>(h_rng) {
            Ok(p) => p,
            Err(e) => return Err(e),
        };

        let mut buffer = [0u8; SHUFFLE_STEPS - 1];
        scoped_rng.get_rng(None, &mut buffer)?; // かなり遅いので初期化時に一度だけ呼んで乱数テーブルを作る
        Ok(Self { buffer, index: 0 })
    }

    fn generate(&mut self) -> u8 {
        let value = self.buffer[self.index];
        self.index = match checked_add_in_range(self.index, 1, (self.buffer.len() - 1) as isize) {
            Some(v) => v,
            None => 0,
        };
        value
    }
}

trait PixelOrder {
    fn from_rgb(r: u8, g: u8, b: u8) -> RGB8;
    fn from_u32(rgb_: u32) -> RGB8;

    fn to_u32(rgb8: RGB8) -> u32;
}

struct RgbOrder;
impl PixelOrder for RgbOrder {
    fn from_rgb(r: u8, g: u8, b: u8) -> RGB8 {
        RGB8::new(r, g, b)
    }

    fn from_u32(rgb_: u32) -> RGB8 {
        let r = (0xFF & rgb_) as u8;
        let g = ((0xFF00 & rgb_) >> 8) as u8;
        let b = ((0xFF0000 & rgb_) >> 16) as u8;
        Self::from_rgb(r, g, b)
    }

    fn to_u32(rgb8: RGB8) -> u32 {
        ((rgb8.r as u32) << 0) | ((rgb8.g as u32) << 8) | ((rgb8.b as u32) << 16)
    }
}

struct BgrOrder;
impl PixelOrder for BgrOrder {
    fn from_rgb(r: u8, g: u8, b: u8) -> RGB8 {
        BGR8::new_bgr(b, g, r).into()
    }

    fn from_u32(rgb_: u32) -> RGB8 {
        let b = (0xFF & rgb_) as u8;
        let g = ((0xFF00 & rgb_) >> 8) as u8;
        let r = ((0xFF0000 & rgb_) >> 16) as u8;
        Self::from_rgb(r, g, b)
    }

    fn to_u32(rgb8: RGB8) -> u32 {
        ((rgb8.b as u32) << 0) | ((rgb8.g as u32) << 8) | ((rgb8.r as u32) << 16)
    }
}

struct Brush {
    color: RGB8,
}

impl Brush {
    pub fn new(color: RGB8) -> Self {
        Self { color }
    }

    pub fn color(&self) -> RGB8 {
        self.color
    }
}

impl Default for Brush {
    fn default() -> Self {
        Self::new(RGB8::new(0, 0, 0))
    }
}

struct CtxInfo {
    pub width: usize,
    pub height: usize,
    pub stride: usize,
    pub current_brush: Brush,
}

impl CtxInfo {
    pub fn new(width: usize, height: usize, stride: usize) -> Self {
        Self {
            width,
            height,
            stride,
            current_brush: Brush::default(),
        }
    }

    pub fn new_from_gop(info: &ModeInfo) -> Self {
        Self::new(info.resolution().0, info.resolution().1, info.stride())
    }
}

fn calc_alpha(color: u8, dest: u8, alpha: u8) -> u8 {
    const HALF: i32 = 1 << (u8::BITS - 1); // 四捨五入の0.5。Q0.8
    let c = (color as i32) * (alpha as i32) + (dest as i32) * (u8::MAX as i32 - (alpha as i32)); // アルファ合成の計算本体。Q9.8
    let r = c + HALF; // 四捨五入用の 0.5 を加算。Q9.8
    ((r + (r >> u8::BITS)) >> u8::BITS) as u8 // (color * alpha + dest * (255 - alpha)) / 255 相当。Q8.0
}

fn get_glyph_by_index(bmp: &Bmp8, index: usize) -> (usize, usize, usize, usize) {
    let cell_width = bmp.width() / BOARD_WIDTH;
    let cell_height = bmp.height() / BOARD_HEIGHT;

    let cx = index % BOARD_WIDTH;
    let cy = index / BOARD_WIDTH;

    (cx * cell_width, cy * cell_height, cell_width, cell_height)
}

trait GraphicCtx<T: PixelOrder> {
    fn info(&self) -> &CtxInfo;
    fn info_mut(&mut self) -> &mut CtxInfo;

    fn width(&self) -> usize {
        self.info().width
    }

    fn height(&self) -> usize {
        self.info().height
    }

    fn bytes_per_pixel(&self) -> usize {
        BASE_BPP
    }

    fn stride(&self) -> usize {
        self.info().stride // ピクセル単位
    }

    fn raw_buffer(&self) -> &[u8];
    fn raw_buffer_mut(&mut self) -> &mut [u8];

    fn calc_pixel_index(&self, x: usize, y: usize) -> usize {
        y * self.stride() + x
    }
    fn calc_bytes_index(&self, x: usize, y: usize) -> usize {
        self.calc_pixel_index(x, y) * self.bytes_per_pixel()
    }

    fn set_pixel_by_bytes_index(&mut self, index: usize, color: RGB8) {
        let pixel = T::to_u32(color);
        unsafe {
            *(self.raw_buffer_mut().as_mut_ptr().add(index) as *mut u32) = pixel;
        }
    }

    fn clear(&mut self, color: RGB8) {
        let (_, pixels, _) = unsafe { self.raw_buffer_mut().align_to_mut::<u32>() }; // やはり UEFI 前提なので u32 固定
        pixels.fill(T::to_u32(color)); // memset() / FillMemory() 相当
    }

    fn set_pixel(&mut self, x: usize, y: usize, color: RGB8) {
        self.set_pixel_by_bytes_index(self.calc_bytes_index(x, y), color);
    }

    fn current_brush(&self) -> &Brush {
        &self.info().current_brush
    }
    fn current_brush_mut(&mut self) -> &mut Brush {
        &mut self.info_mut().current_brush
    }

    fn select_brush(&mut self, brush: Brush) -> Brush {
        mem::replace(&mut self.current_brush_mut(), brush)
    }

    fn draw_rectangle(&mut self, x: usize, y: usize, width: usize, height: usize) {
        let brush_color = self.current_brush().color();
        for j in y..(y + height) {
            for i in x..(x + width) {
                self.set_pixel(i, j, brush_color);
            }
        }
    }

    fn bitblt<Ctx: GraphicCtx<T>>(
        &mut self,
        x: usize,
        y: usize,
        width: usize,
        height: usize,
        src: &Ctx,
        src_x: usize,
        src_y: usize,
    ) {
        let bpp = self.bytes_per_pixel();
        let row_bytes = width * bpp;
        for row in 0..height {
            let src_offset = ((src_y + row) * src.stride() + src_x) * src.bytes_per_pixel();
            let dest_offset = ((y + row) * self.stride() + x) * bpp;
            let src_slice = &src.raw_buffer()[src_offset..src_offset + row_bytes];
            let dest_slice = &mut self.raw_buffer_mut()[dest_offset..dest_offset + row_bytes];
            dest_slice.copy_from_slice(src_slice);
        }
    }

    fn bitblt_bmp8_with_alpha(
        &mut self,
        x: usize,
        y: usize,
        width: usize,
        height: usize,
        src_bottom_up_bmp: &Bmp8,
        src_x: usize,
        src_y: usize,
        color: RGB8,
    ) {
        for row in 0..height {
            let src_row = src_bottom_up_bmp.height() - 1 - (src_y + row);
            let dest_row = y + row;

            let src_y_offset = src_row * src_bottom_up_bmp.row_bytes() + src_x;
            let dest_y_offset = (dest_row * self.stride() + x) * self.bytes_per_pixel();

            for col in 0..width {
                let alpha = src_bottom_up_bmp.alpha_from_palette(src_y_offset + col);
                if alpha == 0 {
                    continue; // 出力そのまま
                }

                let dest_bytes_offset = dest_y_offset + col * self.bytes_per_pixel();
                let dest_ptr = unsafe {
                    self.raw_buffer_mut().as_mut_ptr().add(dest_bytes_offset) as *mut u32
                };

                let out = if alpha < 255 {
                    let dest_u32 = unsafe { ptr::read_unaligned(dest_ptr) };
                    let dest_rgb = T::from_u32(dest_u32);

                    T::to_u32(RGB8::new(
                        calc_alpha(color.r, dest_rgb.r, alpha),
                        calc_alpha(color.g, dest_rgb.g, alpha),
                        calc_alpha(color.b, dest_rgb.b, alpha),
                    ))
                } else {
                    T::to_u32(color) // 入力そのまま
                };

                unsafe {
                    ptr::write_unaligned(dest_ptr, out);
                }
            }
        }
    }
}

struct GopCtx<T: PixelOrder> {
    frame_buffer: &'static mut [u8],
    info: CtxInfo,
    _pixel_order_marker: PhantomData<T>, // T を保持し続ける
}

impl<T> GopCtx<T>
where
    T: PixelOrder,
{
    pub fn new_from_gop(gop: &mut boot::ScopedProtocol<GraphicsOutput>) -> Self {
        let info = gop.current_mode_info();
        let ptr = gop.frame_buffer().as_mut_ptr();
        let frame_buffer = unsafe { slice::from_raw_parts_mut(ptr, gop.frame_buffer().size()) };

        Self {
            frame_buffer,
            info: CtxInfo::new_from_gop(&info),
            _pixel_order_marker: PhantomData,
        }
    }
}

impl<T> GraphicCtx<T> for GopCtx<T>
where
    T: PixelOrder,
{
    fn info(&self) -> &CtxInfo {
        &self.info
    }

    fn info_mut(&mut self) -> &mut CtxInfo {
        &mut self.info
    }

    fn raw_buffer(&self) -> &[u8] {
        &self.frame_buffer
    }

    fn raw_buffer_mut(&mut self) -> &mut [u8] {
        &mut self.frame_buffer
    }
}

struct TileCtx<T: PixelOrder> {
    buffer: *mut u8,
    info: CtxInfo,
    _pixel_order_marker: PhantomData<T>, // T を保持し続ける
}

impl<T> TileCtx<T>
where
    T: PixelOrder,
{
    pub fn new_for_index(index: usize) -> Self {
        Self {
            buffer: unsafe { core::ptr::addr_of_mut!(TILE_BUFFER[index]) as *mut u8 },
            info: CtxInfo::new(TILE_WIDTH, TILE_HEIGHT, TILE_WIDTH),
            _pixel_order_marker: PhantomData,
        }
    }
}

impl<T> GraphicCtx<T> for TileCtx<T>
where
    T: PixelOrder,
{
    fn info(&self) -> &CtxInfo {
        &self.info
    }

    fn info_mut(&mut self) -> &mut CtxInfo {
        &mut self.info
    }

    fn raw_buffer(&self) -> &[u8] {
        unsafe { slice::from_raw_parts(self.buffer, TILE_BUFFER_SIZE) }
    }

    fn raw_buffer_mut(&mut self) -> &mut [u8] {
        unsafe { slice::from_raw_parts_mut(self.buffer, TILE_BUFFER_SIZE) }
    }
}

struct GameSession<T: PixelOrder> {
    game: UefiGame,
    gop_ctx: GopCtx<T>,
    tile_ctx_array: [TileCtx<T>; TILES],
}

fn game_loop<T: PixelOrder>(session: &mut GameSession<T>) {
    system::with_stdin(|input| {
        loop {
            render::<T>(session);

            let mut events = [input.wait_for_key_event().unwrap()];
            boot::wait_for_event(&mut events).discard_errdata().unwrap();

            handle_key_event::<T>(input, session);
        }
    });
}

fn handle_key_event<T: PixelOrder>(input: &mut Input, session: &mut GameSession<T>) {
    let can_move = !session.game.is_solved();

    if let Ok(Some(key)) = input.read_key() {
        match key {
            Key::Printable(c) => match c.into() {
                'k' | 'w' if can_move => session.game.move_up(),
                'j' | 's' if can_move => session.game.move_down(),
                'h' | 'a' if can_move => session.game.move_left(),
                'l' | 'd' if can_move => session.game.move_right(),
                'n' => session.game.new_game(), // r だと誤爆しそうなので
                _ => {}
            },
            Key::Special(scan) => match scan {
                ScanCode::UP if can_move => session.game.move_up(),
                ScanCode::DOWN if can_move => session.game.move_down(),
                ScanCode::LEFT if can_move => session.game.move_left(),
                ScanCode::RIGHT if can_move => session.game.move_right(),
                _ => {}
            },
        }
    }
}

fn render<T: PixelOrder>(session: &mut GameSession<T>) {
    const BOARD_PIXEL_WIDTH: usize = BOARD_WIDTH * TILE_WIDTH;
    const BOARD_PIXEL_HEIGHT: usize = BOARD_HEIGHT * TILE_HEIGHT;

    let ctx = &mut session.gop_ctx;
    ctx.clear(RGB8::new(42, 53, 53));

    let half_view_width = ctx.width() / 2;
    let half_view_height = ctx.height() / 2;

    let brush = Brush::new(RGB8::new(82, 102, 102));
    let _ = ctx.select_brush(brush);

    // 外枠
    let board_offset_x = half_view_width - (BOARD_PIXEL_WIDTH + BORDER_WIDTH * 2) / 2;
    let board_offset_y = half_view_height - (BOARD_PIXEL_HEIGHT + BORDER_HEIGHT * 2) / 2;
    ctx.draw_rectangle(
        board_offset_x,
        board_offset_y,
        BOARD_PIXEL_WIDTH + BORDER_WIDTH * 2,
        BOARD_PIXEL_HEIGHT + BORDER_HEIGHT * 2,
    );

    // スライドさせるやつ
    let tile_offset_x = half_view_width - BOARD_PIXEL_WIDTH / 2;
    let tile_offset_y = half_view_height - BOARD_PIXEL_HEIGHT / 2;
    for r in 0..BOARD_HEIGHT {
        for c in 0..BOARD_WIDTH {
            let tile_x = tile_offset_x + c * TILE_WIDTH;
            let tile_y = tile_offset_y + r * TILE_HEIGHT;

            if let Some(tile_index) = session.game.board().get_tile_by_pos(c, r) {
                let tile_ctx = &session.tile_ctx_array[tile_index.value()];
                ctx.bitblt(tile_x, tile_y, TILE_WIDTH, TILE_HEIGHT, tile_ctx, 0, 0);
            } else if session.game.is_solved() {
                let tile_ctx = &session.tile_ctx_array[TILES - 1];
                ctx.bitblt(tile_x, tile_y, TILE_WIDTH, TILE_HEIGHT, tile_ctx, 0, 0);
            }
        }
    }
}

fn init_tiles<T: PixelOrder>(bmp: &Bmp8) -> [TileCtx<T>; TILES] {
    let mut array = [const { None }; TILES];

    for i in 0..TILES {
        let mut ctx = TileCtx::<T>::new_for_index(i);
        let (sx, sy, sw_cell, sh_cell) = get_glyph_by_index(bmp, i);
        ctx.clear(RGB8::new(162, 204, 204));
        ctx.bitblt_bmp8_with_alpha(
            0,
            0,
            sw_cell,
            sh_cell,
            bmp,
            sx,
            sy,
            T::from_rgb(255, 255, 255),
        );
        array[i] = Some(ctx);
    }

    array.map(|x| x.unwrap())
}

#[entry]
fn main() -> Status {
    uefi::helpers::init().expect("initialize failed");

    let handle = match boot::get_handle_for_protocol::<GraphicsOutput>() {
        Ok(h) => h,
        Err(e) => return e.status(),
    };
    let mut gop = match boot::open_protocol_exclusive::<GraphicsOutput>(handle) {
        Ok(p) => p,
        Err(e) => return e.status(),
    };

    let mut game = match UefiGame::new() {
        Ok(r) => r,
        Err(s) => return s.status(),
    };
    game.shuffle();

    // 画面情報
    let bmp = Bmp8::parse_bmp8(DIGITS_BMP8).expect("bmp8 parse failed");
    let info = gop.current_mode_info();
    match info.pixel_format() {
        PixelFormat::Rgb => {
            type P = RgbOrder;
            let mut session = GameSession {
                game,
                gop_ctx: GopCtx::new_from_gop(&mut gop),
                tile_ctx_array: init_tiles::<P>(&bmp),
            };
            game_loop(&mut session);
        }
        PixelFormat::Bgr => {
            type P = BgrOrder;
            let mut session = GameSession {
                game,
                gop_ctx: GopCtx::new_from_gop(&mut gop),
                tile_ctx_array: init_tiles::<P>(&bmp),
            };
            game_loop(&mut session);
        }
        _ => panic!("Unsupported pixel format"),
    }

    Status::SUCCESS
}

struct Bmp8<'a> {
    width: usize,
    height: usize,
    row_bytes: usize,
    palette: &'a [u8],
    data: &'a [u8],
}

impl<'a> Bmp8<'a> {
    pub fn width(&self) -> usize {
        self.width
    }

    pub fn height(&self) -> usize {
        self.height
    }

    pub fn row_bytes(&self) -> usize {
        self.row_bytes
    }

    fn read_u32(b: &[u8], o: usize) -> u32 {
        u32::from_le_bytes([b[o], b[o + 1], b[o + 2], b[o + 3]])
    }

    pub fn parse_bmp8(data: &'a [u8]) -> Option<Self> {
        // "BM" (Windows形式) を前提とする。詳細は BITMAPFILEHEADER 構造体を参照
        const BF_OFF_BITS_OFFSET: usize = 2 + 4 + 2 + 2; // 10

        let pixel_offset = Self::read_u32(data, BF_OFF_BITS_OFFSET) as usize;
        let dib_header_size = Self::read_u32(data, BF_OFF_BITS_OFFSET + 4) as usize;
        let width = Self::read_u32(data, BF_OFF_BITS_OFFSET + 8);
        let height = Self::read_u32(data, BF_OFF_BITS_OFFSET + 8 + 4);
        let row_bytes = (width + 3) & !0x03; // 4byte アライメント
        let need = pixel_offset.checked_add(row_bytes.checked_mul(height)? as usize)?;

        Some(Bmp8 {
            width: width as usize,
            height: height as usize,
            row_bytes: row_bytes as usize,
            palette: &data[(BF_OFF_BITS_OFFSET + 4 + dib_header_size)..pixel_offset],
            data: &data[pixel_offset..need],
        })
    }

    pub fn alpha_from_palette(&self, index: usize) -> u8 {
        let palette_index = self.data[index] as usize * 4;
        let m = core::cmp::max(self.palette[palette_index], self.palette[palette_index + 1]);
        core::cmp::max(m, self.palette[palette_index + 2])
    }
}

#[cfg(not(test))]
#[panic_handler]
fn panic_handler(_info: &core::panic::PanicInfo) -> ! {
    loop {}
}

tiles.bmp

Adobe Illustrator で作成しました。
記事に載せる都合で PNG ファイルにしています。ビルドされる際には 8bpp、グレースケールなビットマップファイルに変換してください。
ペイントなら 256 色のビットマップ形式で保存すれば動作するはずです。