Story
Adding in the functionality for a player to influence the outcome of a game story can look much like a state machine as well. Usually, these state machines are much less complicated though. There are certain things that can't be generated well quite yet like voiceovers in terms of tone and conveying emotion.
Players have come to expect a certain level of storytelling so when certain things are difficult to produce, it narrows the availability of additions like multiple storylines. What keeps procedural storytelling to a minimum is the fact that what makes a good story is very subjective. Physics and graphics are all based on hard math but story is based on opinion. And we don't want to deliver a subpar story to our player.
With that in mind, we could map out elements to a story or several stories combined. Then, we could either randomly choose the arrangement of story path states that we want the player to follow, or we could react to the player's behavior in certain events. This is...