美思 [技術雜談] 以 C 語言實作龍與地下城 (Dragons and Dungeons) 風格的骰子

Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

前言

學習程式設計時,除了學習其語法外,運用已知的語法來實作一些小型程式,更有助於澄清我們對於程式語言的理解是否正確。在本例中,我們使用 C 語言來實作龍與地下城 (Dragons and Dungeons) 遊戲中著名的 d20 骰子系統,雖然在這麼短的範例無法做出電腦遊戲,實作遊戲中的骰子也是程式設計中常見的一項課題。

介紹

在遊戲中,隨機性 (randomness) 可增加遊戲的趣味,避免遊戲結果太過固定、可預期而感到乏味。在桌上遊戲中,透過 (公正的) 骰子來達到隨機性,在電腦程式中,則是透過隨機函式來生成亂數。龍與地下城原本是桌上遊戲,後來有數家電腦遊戲廠商將其做成電腦遊戲,像是柏德之門 (Baldur's Gate)、冰風之谷 (Icewind Dale)、絕冬城之夜 (Neverwinter Nights) 等。但這些遊戲仍然保有原本的規則,像是繼續延用 d20 骰子系統等。

整個龍與地下城規則相當龐大,超出本文所要討論的範圍,本文僅就 d20 部分來討論。一些 d20 的實例如下:

  • 1d8:代表投擲一個骰子,其面額可能為 1 至 8,故結果可能為 1 至 8
  • 2d6:代表投擲兩個骰子,其面額可能為 1 至 6,故結果可能為 2 至 12
  • 1d10+2:代表投擲一個骰子,其面額可能為 1 至 10,另外再加上 +2 的修正值,故結果可能為 3 至 12

在龍與地下城遊戲中,+1 以上的武器視為魔法武器 (magic weapons),但本範例不會用到這項特性。

除了 d20 規則外,我們也要知道如何以程式產生亂數。自行實作亂數生成的演算法超出本文所要討論的範圍,本文僅簡要說明如何使用亂數函式:

  • 給予函式一個初始值,做為種子 (seed)
  • 將種子餵給亂數產生函式,產生一個數值
  • 將前述數值做為新的種子,再產生另一個值

程式展示

本範例實作一個終端機程式 d20,該程式可在終端機中模擬擲骰子的動作。

在預設情形下,本程式模擬中型生物 (如人類) 使用短劍 (short swords) 造成 1d6 的傷害:

$ d20
3

使用者可輸入 d20 風格的字串,以使用不同的擲骰:

$ d20 "1d8+1"
7

也可輸入參數,像本例中模擬 2d8+2 的擲骰:

$ d20 -r 2 -d 8 -m 2
11

本程式參數如下:

  • -v--version:顯示版本號
  • -h--help:顯示說明文件
  • -r n--roll n:擲骰 n 次,n 為正整數
  • -d n--dice n:骰子的最大面值為 nn 為正整數 (最小值皆為 1)
  • -m n--modifier n:修正值為 nn 可為正或負整數或零

未輸入的參數,皆以 1d6 為準。像以下例子模擬 3d6 的擲骰:

$ d20 -r 3
15

但字串需完整,像以下例子會引發錯誤:

$ d20 "2d"
2d
  ^ -- no valid dice face at 3

設計概念

本程式中重要的部分如下:

  • 解析命令列參數
  • 解析 d20 字串
  • 產生特定範圍的亂數

解析命令列是終端機程式常見的子任務,但常見的函式庫 GetoptArgp 皆依賴於 POSIX 環境,如果該程式要在 Windows 下執行,就必需自行實作。因為我們希望這個程式在 Windows 上也能執行,本文將會自行實作這個部分,但不會特地將其做成函式庫,因為後者需要考慮的事情超出本範例的範圍太多。

解析 d20 字串算是比較 niche 的子任務,需要自行實作。由於 d20 字串的規則相當簡單,可以使用常規表示式 (regular expression) 直接抓取子字串或是手動解析。前者程式碼看起來短,但需要引入整個常規表示式函式庫,反而執行檔會比較肥大;後者的程式碼當然會長很多,但整體的程式碼量會比直接用 regex 來得少。本文會展示一個手動解析的流程。

產生亂數的部分則會使用標準函式庫附帶的亂數函式,表面上看起來程式碼不長,但內部會用到標準函式庫的東西,實際的程式量不一定比較短。一般來說,較少程式設計者自行實作亂數產生函式庫,而會使用現有的函式庫。本文使用 C 標準函式庫內建的亂數產生函式 (位於 stdlib.h)。

程式碼範例

本節展示其中一種做法,讀者可以試著先用自己的方式實作看看,之後再和我們的方法比較。

本節會導引讀者閱讀程式碼,想自行追蹤程式碼的讀者,請到這裡觀看專案。

主程式的主要流程如下:

int main(int argc, char *argv[])
{
    // Parse command-line arguments.

    // Branch the program as needed.

    // Parse d20 string if needed.

    // Roll the dice.

    // Free system resources.
}

原本程式碼略長,我們放在這裡,此處不重覆貼出。

C 語言用兩個變數儲存命令列參數,argc 儲存命令列參數的數量,argv 儲存由命令列參數所組成的字串陣列。因為 C 語言的陣列本身不儲存陣列長度的資訊,故要使用另一個變數來存。解析命令列參數就是走訪這個陣列,藉此得知程式使用者所下的指令。我們這裡節錄解析參數的主要程式:

PARSING_EVENT argument_pasre(ParsingResult *pr, char **args, int size)
{

    for (int i = 1; i < size; i++) {
        // Show version number.
        if (strcmp(args[i], "-v") == 0 || strcmp(args[i], "--version") == 0) {
            return PARSING_EVENT_VERSION;
        }
        // Show help message.
        else if (strcmp(args[i], "-h") == 0 || strcmp(args[i], "--help") == 0) {
            return PARSING_EVENT_HELP;
        }
        // Roll
        else if (strcmp(args[i], "-r") == 0 || strcmp(args[i], "--roll") == 0) {
            // Check if any available value.
            if (i+1 >= size) {
                fprintf(stderr, "No valid roll%s", SEP);
                return PARSING_EVENT_ERROR;
            }

            // Convert the value from string to unsigned int.
            unsigned int r = strtoul(args[i+1], NULL, 10);
            if (args[i+1][0] == '-' || r == 0) {
                fprintf(stderr, "Invalid roll: %s%s", args[i+1], SEP);
                errno = 0;
                return PARSING_EVENT_ERROR;
            }

            // Set the ParsingResult object.
            parsing_result_set_roll(pr, r);

            i++;  // Go one step further.
        }
        // Dice
        else if (strcmp(args[i], "-d") == 0 || strcmp(args[i], "--dice") == 0) {
            // Check if any available value.

            // Convert the value from string to unsigned int. 

            // Set the ParsingResult object.

            i++;  // Go one step further.
        }
        // Modifier
        else if (strcmp(args[i], "-m") == 0 || strcmp(args[i], "--modifier") == 0) {
            // Check if any available value.

            // Convert the value from string to int.

            // Set the ParsingResult object.

            i++;  // Go one step further.
        } else {
            // Set d20 string.
            pr->str = args[i];
            break;
        }
    }

    return PARSING_EVENT_SUCCESS;
}

我們用一個略長的 for 迴圈解析命令列參數,根據不同的參數進行不同的動作。解析完會得到兩個值,一個是解析結果 (包在 ParsingResult 物件中),一個是解析事件 (PARSING_EVENT),前者將解析結果儲存起來,供後續程式使用,後者則記錄解析的狀態,做為後續分支條件的判斷依據。完整的程式碼請看這裡

分支條件部分的程式碼相當短,我們將其直接貼出:

int main(int argc, char *argv[])
{
    // Parse command-line arguments.

    if (pv == PARSING_EVENT_VERSION) {
        printf("%s%s", VERSION, SEP);
        goto FREE;
    }
    else if (pv == PARSING_EVENT_HELP) {
        print_help(stdout);
        goto FREE;
    }
    else if (pv == PARSING_EVENT_ERROR) {
        parsing_result_free(pr);
        return EXIT_FAILURE;
    }

    // Parse d20 string if needed.

    // Roll the dice.

    // Free system resources.
}

在顯示程式版本號和顯示幫助文件時,我們直接進行相對應的動作,然後跳到釋放資源部分的程式。在解析命令列參數出錯時,我們會提早結束程式,在先前的程式中,我們已經印出相對應的錯誤訊息,此處就不重覆印出。

為了要解析 d20 字串,我們內部實作一個微型的直譯器,這個直譯器分為兩個部分:

  • 詞法分析器 (lexer):將字串轉為 token 流
  • 語法分析器 (parser) 加直譯器 (interpreter):解析 token 流,將其轉為 ParsingResult 物件

一般在實作直譯器時,會將 lexer、parser、interpreter 等模組拆開,但 d20 字串格式比較簡單,所以我們直接將後兩者做成同一個模組。

在進行詞法分析前,要先定義該直譯器所接受的 token 種類:

typedef enum {
    TOKEN_INT,
    TOKEN_DICE,
    TOKEN_SIGN
} TOKEN_TYPE;

d20 字串中的 token 種類很少,只有三種,分別對應整數 (TOKEN_INT)、骰字字串 (TOKEN_DICE)、正負符號 (TOKEN_SIGN)。完整的程式碼可見這裡

註:骰子字串的例子像是 1d6 之中的 d 字母。

Token 的定義如下:

struct token {
    char * str;
    TOKEN_TYPE t;
    unsigned loc;
};

其內有三個屬性,分別為 token 類別、token 所包含的字串、token 所在的位置。一般來說,token 所在的位置包含行 (column) 和列 (row) 兩個面向的資訊,但此處的 d20 字串僅有單行,故我們省略列相關的資訊。完整的程式碼可看這裡

定義好 Token 類別後,就可以開始寫詞法分析器。此處將詞法分析器的主要程式節錄如下:

ObjLex * lex_new(char *input)
{
    ObjLex *obj = (ObjLex *) malloc(sizeof(ObjLex));
    if (!obj) {
        return obj;
    }

    // Init obj.

    STATE s;
    size_t sz = strlen(input);
    // Lex the input string by a finite automata.
    while (obj->curr < sz) {
        if (is_num(input[obj->curr])) {
            s = lex_num(obj);
        } else if (is_dice(input[obj->curr])) {
            s = lex_dice(obj);
        } else if (is_sign(input[obj->curr])) {
            s = lex_sign(obj);
        } else {
            s = STATE_ERROR;
        }

        // Show an error message if something wrong.
        if (s == STATE_ERROR) {
            // Show some error message.

            // Exit the automata.
            goto FAIL;
        }
        else if (s == STATE_INVALID) {
            // Exit the automata.
            goto FAIL;
        }
        // Stop the automata.
        else if (s == STATE_END) {
            break;
        }
    }

    return obj;

FAIL:
    lex_free(obj);
    obj = NULL;
    return obj;
}

我們在做詞法分析 (lexing) 時,要走訪輸入字串,將其逐一轉成 token。在這個過程中,要追蹤兩個狀態,一個是走訪輸入字串的指標位置 (在本例為 curr),一個是詞法分析器本身的狀態 (在本例為變數 s,其型別為列舉 STATE)。在走訪輸入字串的過程中,詞法分析器本身的狀態會改變,以本例來說,當狀態變成 STATE_ERRORSTATE_INVALID 時會提早結束分析過程,而變成 STATE_END 時代表整個過程順利結束。完整的程式碼請看這裡

由於詞法分析器的寫法相當固定,在實務上,我們較少手寫詞法分析器,而會借助一些現有的工具;以 C 語言來說,常見的工具像是 LexFlex 等。不過,自己手寫一次詞法分析器有助於了解其行為。

接著,我們來看語法分析器和直譯器 (以下簡稱 eval) 的主要程式:

bool eval(char *input, ParsingResult *out)
{
    // Check whether input is empty.

    // Lex input to get oLex object.

    Token *tn;
    char *str_r;
    char *str_d;
    char *str_sign;
    char *str_m;

    // 1st token is mandatory.
    tn = lex_next(oLex);
    if (!tn) {
        // Show some error message.

        goto PARSE_FAIL;
    }

    // 1st token should be TOKEN_INT, e.g. 1d6.    
    if (token_type(tn) != TOKEN_INT) {
        show_error(input, tn);
        goto PARSE_FAIL;
    }

    str_r = token_str(tn);

    // 2nd token is mandatory.
    tn = lex_next(oLex);
    if (!tn) {
        // Show some error message.

        goto PARSE_FAIL;
    }

    // 2nd token should be TOKEN_DICE, e.g. 1d6.
    if (token_type(tn) != TOKEN_DICE) {
        show_error(input, tn);
        goto PARSE_FAIL;
    }

    // Discard 'd' (dice string).

    // 3rd token is mandatory.
    tn = lex_next(oLex);
    if (!tn) {
        // Show some error message.

        goto PARSE_FAIL;
    }

    // 3rd token should be TOKEN_INT, e.g. 1d6.
    if (token_type(tn) != TOKEN_INT) {
        show_error(input, tn);
        goto PARSE_FAIL;
    }

    str_d = token_str(tn);

    // 4th token is optional.
    tn = lex_next(oLex);
    if (!tn) {
        goto PARSE_END;
    }

    // 4th token should be TOKEN_SIGN, e.g. 1d6+2.
    if (token_type(tn) != TOKEN_SIGN) {
        show_error(input, tn);
        goto PARSE_FAIL;
    }

    str_sign = token_str(tn);

    // 5th token is mandatory when 4th token exists.
    tn = lex_next(oLex);
    if (!tn) {
        // Some some error message.

        goto PARSE_FAIL;
    }

    // 5th token should be TOKEN_INT, e.g. 1d6+2.
    if (token_type(tn) != TOKEN_INT) {
        show_error(input, tn);
        goto PARSE_FAIL;
    }

    str_m = token_str(tn);

    // 6th or further token is invalid.
    tn = lex_next(oLex);
    if (tn) {
        show_error(input, tn);
        goto PARSE_FAIL;
    }

    // Update modifier.

PARSE_END:    
    // Update roll.

    // Update dice.

    lex_free(oLex);

    return true;

PARSE_FAIL:
    lex_free(oLex);

    return false;
}

eval 沒有採用正規的語法分析器和直譯器的寫法,這是因為 d20 字串的格式相當固定,我們只要將 token 串流逐一取出後檢查其格式即可。確認格式正確後將結果輸出轉換到 ParsingResult 即可。完整的程式碼可見這裡

同樣地,實務上我們也不會手動撰寫語法分析器,而會借助一些現有的工具;以 C 語言來說,常見的工具像是 YaccBison 等。由於 eval 的功能較簡單,我們就自行手刻,也算是一個練習。

雖然前面的程式碼有點長,實際擲骰的程式碼卻相對短得多:

int dice_roll(unsigned roll, unsigned dice, int modifier)
{
    srand((unsigned) time(NULL));

    int result = 0;

    for (unsigned i = 0; i < roll; i++) {
        result += rand() % dice + 1;
    }

    result += modifier;

    return result;
}

程式碼會這麼短是因為大部分的苦工都由函式庫處理掉了,在這裡只是呼叫現有的函式。

筆者寫完後發現這篇文章稍微長了一點,如果之後碰到比較長的範例,或許我們會將其拆成一系列文章,而不會用單篇來呈現。

關於作者

身為資訊領域碩士,美思認為開發應用程式的目的是為社會帶來價值。如果在這個過程中該軟體能成為永續經營的項目,那就是開發者和使用者雙贏的局面。

美思喜歡用開源技術來解決各式各樣的問題,但必要時對專有技術也不排斥。閒暇之餘,美思將所學寫成文章,放在這個網站上和大家分享。