本节书摘来异步社区《游戏编程模式》一书中的第7章，第7.10节，作者： 【美】Robert Nystrom （尼斯卓姆） 译者： 赵卫兵 , 许新星 , 姜召阳 , 陈侃 , 屈光辉 , 郑炯彬 责编： 陈冀康，更多章节内容可以访问云栖社区“异步社区”公众号查看。
7.10 下推自动机
还有一种有限状态机的扩展，它们也使用状态栈。容易让人混淆的是，这里的栈代表了完全不同的东西，且用于解决一个完全不同的问题。
它要解决的是有限状态机没有历史记录的问题。我们知道当前状态，但是，我们并不知道之前的状态是什么。而且，我们也没有简便的方法可以获取之前的状态。
举个例子：之前，让无畏的主角全副武装。当她开枪的时候，我们需要一种新的状态来播放开枪的动画，发射子弹并显示一些特效。因此，我们需要定义一个FiringState，并且所有的状态都可以切换到这个状态，只要有玩家按下开火按键就行了。
因为这个行为在许多状态里面都重复了，所以是个使用层次状态机来复用代码的好机会。
那么问题来了，当她开完枪后，她要回到什么状态呢？主角可以处于站立、躲避、俯冲和跳跃状态。但开火的动画播放完以后，她应该要回到之前的状态。
如果我们仍然坚持使用以前的有限状态机，那么我们将无法获得上一个状态的信息。为了保留上一个状态的信息，我们不得不定义一些几乎对等的状态，比如站立开火状态，跑步开火状态等。这样的话，当我们的开火状态完成以后，就可以切换回之前的状态了。
我们需要的仅仅是一种能够让我们可以保存开火前状态的方法，这样在开火状态完成之后可以回去。这里自动机理论再次帮上了我们的忙。相关的数据结构叫做下推自动机（pushdown automata）。
本来，有限状态机有一个指向当前状态的指针。而下推自动机则有一个状态栈。在一个有限状态机里面，当有一个状态切进来时，则替换掉之前的状态。下推自动机可以让你这样做，同时它还提供其他选择：
- 你可以把这个新的状态放入栈里面。当前的状态永远存在栈顶，所以你总能转换到当前状态。但是当前状态会将前一个状态压在栈中自身的下面而不是抛弃掉它。
- 你可以弹出栈顶的状态，该状态将被抛弃。与此同时，上一个状态就变成了新的栈顶状态了。
当开火按钮在任何一种状态下被按下的时候，我们把开火状态push到栈顶。当开火动画结束的时候，我们把这个开火状态pop出去。此时，状态机会自动切换到我们开火前的上一个状态。
