采访问题：检测格斗游戏动作集

Question

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

假设您有一款格斗游戏，其中某些按钮组合代表一个特殊动作。实现 2 个函数 register_move([button combo],movename)，它接收按钮输入列表和 movename 字符串以及 on_keypress( button) 注册当前按键并在激活按钮组合时打印移动名称。按钮表示为字符：'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。初始状态为 "no keys recognised"。在每次按键时，转换到一个新状态；如果它是最终状态，则您可以采取行动。所有未定义的转换都转换到起始状态。例如，

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

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

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

Answer 2

考虑到移动次数有限，您不需要超级高效的有限状态机来处理这个问题。

您可以简单地将字符串存储在 register_move 中，并让 on_keypress 记住最后一个可能有效的序列。

如果当前键序列是至少一个动作的前缀（例如 "AB" 是 "ABU" 的前缀），你就完成了（只需等待下一次按键即可看到如果达到组合）。
如果序列没有前缀，将序列重置为最后一次按键（例如 "ABD" -> "D"）。这会清除之前对应于无移动的按键。
如果序列对应于一个移动，执行移动（好吧，至少打印它）并重置序列。

这需要对每个可能的移动组合进行前缀搜索，如果您只有十几个，这会非常快。如果出于某种原因你想要更快，你确实可以将你的组合列表变成一个前缀树，但是它需要更多的代码而收效甚微。

采访问题：检测格斗游戏动作集

Interview Q: Detecting a fighting game moveset

algorithm

state

data-structures