测试 Super Mario Bro

截止时间 (Deadline)：TBD

Super Mario Bros 是任天堂 (Nintendo) 于 1985 年推出的经典横版动作平台游戏，作为电子游戏史上的里程碑作品，它使马里奥成为全球文化符号，并推动任天堂成为世界级游戏公司，被广泛认为是电子游戏从早期娱乐产品走向现代互动艺术的重要转折点。

在本实验中，我们将以一个基于 Python 开发的 Super Mario Bros 复刻版作为待测软件系统，基于实验提供的自动化测试框架，为其设计针对性和系统性的测试用例。

待测系统和测试框架

运行如下命令下载本实验的待测系统和测试框架：

$ git clone https://git.nju.edu.cn/course-lab/super-mario-lab.git
$ cd super-mario-lab

其中：

code 目录为原始的 super-mario-python 代码；
tests 目录为实验提供的自动化测试框架；
README.md 为项目相关的文档，具体包括：
- README.md：运行环境的配置、游戏的基本操作、以及测试框架的基本使用；
- tests/README.md：对该测试框架如何工作的简要解释；
- tests/test_spec/README.md：对测试用例集文件 test-suite.json 和测试关卡文件 LevelTest*.json 的格式说明。

测试框架仍处于不断完善阶段，可关注其更新状态并及时拉取新版本，大的版本更新将在课程群里通知。我们也非常欢迎大家反馈测试框架中遇到的 Bugs 和改进建议。

实验内容

在本实验中，你需要编写一个自动化测试用例生成算法，所生成的测试用例应能在有限的测试成本下，触发 Super Mario Bros 尽可能多样的行为，并能找到其中尽可能多的潜在故障。

测试输入

对于 Super Mario Bros，每个测试用例的测试输入就是一个事件序列 (a sequence of events)，其指明了在特定帧 (frame) 时应执行的具体事件操作，在测试框架中以类似如下 JSON 格式表示：

"events": [
  {"frame": 60, "type": "KEYDOWN", "key": "RETURN"},
  {"frame": 62, "type": "KEYUP", "key": "RETURN"},
  {"frame": 120, "type": "KEYDOWN", "key": "RETURN"},
  {"frame": 122, "type": "KEYUP", "key": "RETURN"},
  {"frame": 200, "type": "KEYDOWN", "key": "RIGHT"},
  {"frame": 221, "type": "MOUSEBUTTON", "button": 1, "position": [320, 240]},
  {"frame": 230, "type": "KEYUP", "key": "RIGHT"},
  {"frame": 250, "type": "QUIT"}
]

例如，对于上述测试序列，其指明在第 60 帧时执行按下 RETURN 键操作 (并保持一直按下状态)；在第 62 帧时执行放开 RETURN 键操作；在第 120 帧时执行按下 RETURN 键操作等，一直到第 250 帧时结束测试。

预期输出

测试用例的预期输出指定了在特定帧时 Super Mario Bros 应处于的状态，在测试框架中以类似如下 JSON 格式表示：

"expected": [
  {
    "at": "end",
    "condition": "mario.x > 0 and dashboard.points == 0"
  }
]

例如，上述预期输出表明在事件序列执行结束时，应满足 mario.x > 0 and dashboard.points == 0 这一预期条件，其中 mario.x 和 dashboard.points 是 Super Mario Bros 中可被观察到的一些变量。

自定义测试关卡

由于 Super Mario Bros 的特定行为会和具体关卡相关，因此在测试时可能还需考虑加载原始待测程序中没有包含的特定关卡。Super Mario Bros 的关卡以如下 JSON 格式表示，其中各字段指明了在关卡中的什么位置绘制一些什么样的对象：

{
  "id": 2,            
  "length": 60,       
  "level": {          
    "objects": {      
      "bush": [],
      "sky": [],
      "cloud": [],
      "pipe": [],
      "ground": []
    },
    "layers": {       
      "sky": {
        "x": [0, 60],
        "y": [0, 13]
      },
      "ground": {
        "x": [0, 60],
        "y": [14, 16]
      }
    },
    "entities": {     
      "CoinBox": [],
      "Goomba": [],
      "Koopa": [],
      "coin": [],
      "coinBrick": [],
      "RandomBox": []
    }
  }
}

详细格式说明

测试框架中的 test_spec/ 目录用于存储测试用例集和测试关卡，关于测试用例集和测试关卡的详细格式描述可在该目录下的 README.md 中查看。此外，该目录下的 test-suite.json 给出了一个包含两个测试用例的示例测试用例集，levels/LevelTest1.json 给出了一个示例关卡，可用于参考。

在设计和实现测试用例生成算法时，你需要确保算法最终生成的测试用例集和测试关卡文件符合上述格式要求 (即可以被实验自动化测试框架正确加载执行)。

测试执行成本控制

测试框架会通过 config.json 配置文件来控制测试执行成本，具体包括：

max_test_cases：test suite 文件中最多允许包含的 test case 个数；
max_events_per_case：单个 test case 最多允许执行的 event 个数；
max_frames_per_case：单个 test case 最多运行执行的 frame 个数

你实现的测试用例生成算法应能自动生成符合上述限定要求的测试用例集。

提交方式和评估指标

TBD