The point about Mark of the Ninja and available information is spot on. Hiding information makes it more difficult for players to predict the outcome of their actions, which easily (usually) feels like removal of control for the player. Losing the feeling of control, and a lack of predictability toward the outcome of your actions is what is frustrating. Exposing all of the important information, even if it needs to be in heavy-handed HUD elements, empowers the player.

“Maybe if the AI were more complex” is a common pitfall. Complex AI/behavior routines that boil down to ‘walk here, play animation’ are effectively hidden information, and result in the unpredictable behavior mentioned above. Giving the AI more ‘verbs’ to think about in the environment (think health terminals in BioShock), can help, but is a post for a different day.

AI complexity isn’t really the issue, and isn’t the fix. Creating a compelling ‘stealth’ moment isn’t difficult. It boils down to giving the player control over when they engage, and a chance for them to be interrupted.

Max Payne 1 and 2 (I haven’t played 3 yet) aren’t stealth games, but they excel at this. At a high level their bread and butter encounters are:

1. Max enters the scene undetected.
2. Enemy characters are walking around/standing, while delivering dialogue.
3. Player chooses whether or not to interrupt their conversation about Pokemon, how and when to engage.
4. Occasionally the designers throw in a patrol character to disrupt/interrupt your choice.

Simple, effective, gives authorial control to your designers while still making every encounter feel dynamic. Awesome.

Tangent point: The silly lights on Sam Fischer’s outfit have an easy explanation. You need to be able to see your orientation while moving around in darkness. Narratively they make no sense, but that is hardly a new thing for games.