技术杂谈:以 C 语言实现龙与地下城 (Dragons and Dungeons) 风格的骰子

PUBLISHED ON JUL 17, 2018

    学习程序设计时,除了学习其语法外,运用已知的语法来实现一些小型程序,更有助于澄清我们对于程序语言的理解是否正确。在本例中,我们使用 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;
    }
    

    程序代码会这么短是因为大部分的苦工都由函式库处理掉了,在这里只是调用现有的函式。

    笔者写完后发现这篇文章稍微长了一点,如果之后碰到比较长的范例,或许我们会将其拆成一系列文章,而不会用单篇来呈现。