Some games might still follow a linear narrative, but the player explore the surroundings. In terms of narrative though, the linearity is still given by the fact that this freedom of exploration doesn't impact the storyline. The story doesn't move forward by exploring; some more story details might be acquired by the player, but there is no overall impact on the story.
A great example of exploration that enhances the storyline without affecting its course are books, documents, or audio files with bits of information scattered around levels. They reward players who explore the game maps, but they don't change anything story-wise. This practice is widely used, especially in FPS games with a linear storyline. ...
