A video game with nonlinear gameplay presents players with challenges that can be completed in a number of different sequences. Each player sees only some of the challenges possible, and the same challenges may be played in a different order. A video game with linear gameplay will confront a player with a fixed sequence of challenges. Every player sees every challenge and sees them in the same order.
A nonlinear game will allow greater player freedom than a linear game. For example, a nonlinear game may permit multiple sequences to finish the game, a choice between paths to victory, or optional side-quests and subplots. Some games feature both linear and nonlinear elements, and some games offer a sandbox mode that allows players to explore an open world game environment independently from the game's main objectives, if any objectives are provided at all.
A game that is significantly nonlinear is sometimes described as being open-ended or a sandbox, though that term is used incorrectly in those cases, and is characterized by there being no "right way" of playing the game. A common consequence (intentional or unintentional) of open-ended gameplay is emergent gameplay.
Read more about Nonlinear Gameplay: Early Examples