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

PUBLISHED ON JUL 17, 2018
FacebookTwitter 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;
    }
    

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

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