小女孩和面具小姐的repo~通过动态规划解决音游中按键的左右手分配问题，以《Deemo I：古树旋律》为例
音乐游戏（英语：music game，缩写MUG、日语：音楽ゲーム，缩写音ゲー）是一种游戏类型，或指属于这个类型的游戏。 在音乐游戏中，玩家需要配合音乐节奏、根据视觉提示做出正确的反应。通常，玩家的反应和节奏越吻合，得分越高。
纵向下落式音游（以下简称“下落式音游”）是音游中最早出现的类型之一(1997年)，也是当前音游中最为常见的类型。 （比较典型的下落式音游：《BeatMania》（KONAMI）、《节奏大师》（腾讯））而大部分移动端下落式音游的常用打法为通过左右手食指点击按键，因此对于关卡（即以下所称的“谱面”）中所有按键的左右手分配（决定采用左手还是右手点击该键）是下落式音游中最为重要的环节。
而我们所希望解决的问题，是根据动态规划算法设计一个尽可能适用于大多数音游的按键分配策略
附：
作为上述按键分配策略的实际提现，我们将以《Deemo I：古树旋律》为例建立动态规划模型并编程实现。
关于《Deemo I：古树旋律》的介绍：
- 目标函数说明文档中有对游戏机制的简要说明
- Deemo官网
- 萌娘百科-Deemo
采用《Deemo I：古树旋律》作为案例的原因：
- 按键简单，种类少（名义上三种，实际两种）
- 游戏机制简单（尤其是滑键机制简单）
- 谱面相对典型
为简化动态规划模型，我们不失一般性地做出如下假设：
- 在将本repo的策略作为实际游戏策略的情境下，我们假设玩家可以预先获知谱面的每一个细节，即
- 在算法层面，我们始终针对整个谱面进行分析，而不讨论仅对部分谱面数据已知时对整个谱面进行规划的情形
- 在实际游戏层面，我们不考虑玩家对于谱面的反映时间对游戏策略造成的直接影响
- 本repo仅讨论双指谱面，即不考虑需要同时按下三个或更多按键的谱面（如荒神/あらがみ的Ex难度谱面）
在运行主程序main.py前，应先现在依赖库与文件。所需要的依赖库包括：
- numpy
依赖文件包括：
- 若干Deemo谱面
- Deemo模拟器
上述内容可通过运行主文件夹下的批处理命令文件setup.sh完成安装
在主文件夹下执行以下命令以运行指法生成程序：
python main.py -c [谱面文件名] [-l [内存释放策略]]
其中，[谱面文件名]为谱面文件夹内的json文件名（不包含.json扩展名）；[内存释放策略]取值与对应策略如下：
-l 取值 |
压缩策略 | 最小压缩率 | 最终压缩率 | 运行时间 |
|---|---|---|---|---|
| 0 | 不释放废弃路径 | 0% | 0% | 1 |
| 1 | 每次迭代均释放上一次迭代产生的废弃路径 | ~50% | ~50% | ~15 |
| 2 | 每10次迭代释放前10次产生的废弃路径（默认） | ~60% | ~90% | ~4 |
| 3 | 迭代结束后释放所有废弃路径 | 0% | >99% | ~1.1 |
例如
python main.py -c purewhite.hard
python main.py -c samsaraamberwishes.hard -l 1
运行完成后，程序将会自动生成带有指法标定的.a&c文件。
预下载的谱面预览器支持对.json谱面与.a&c谱面进行预览。