algorithm - 采访Q : Detecting a fighting game moveset

Question

这是一个面试问题，我想知道设计这个系统的最佳方式是什么。问题:

假设您有一款格斗游戏，其中某些按钮组合代表一个特殊 Action 。实现 2 个函数 register_move([button combo],movename) 接受按钮输入列表和 movename 字符串，以及 on_keypress(button) 注册当前按键并打印如果按钮组合已被激活，则为 movename。按钮表示为字符:'U'、'D'、'L'、'R'、'A'、'B'

例子:

register_move(['A','B','U'],"Uppercut")
on_keypress('A')
on_keypress('B')
on_keypress('U') -> print "Uppercut"

您可以假设移动是在 on_keypress 之前注册的，这样您就不必回头查看之前的按键操作。你可以使用任何你喜欢的语言

Answer 1

构建一个 Deterministic Finite State Automaton .初始状态是“未识别任何键”。在每次按键时，转换到一个新状态；如果它是最终状态，则您可以采取行动。所有未定义的转换都转换到起始状态。对于您的示例，

S --(a)--> A
A --(b)--> AB
AB --(u) --> ABU: process "Uppercut", move to S
X --(x)--> S

其中 X 是任何状态，x 是规则未涵盖的任何输入。

更实际而不是理论上，你最终会得到一个 trie ，所以使用 trie 库应该就足够了。 Root 是“无输入”，遍历它直到一片叶子，或者按错重新启动。