I was wondering how to identify these (what to name the tag as). Nonlinearity doesn't actually mean this. Open world definitely doesn't. Metroidvania's specifically are not like this despite the superficial appearance of such.
Examples:
* Demon's Souls
* Terraria
* Minecraft
* Tales of Maj'Eyal
... none of these are perfect any order examples AFAIK.
This is fairly standard I believe in exploration and 4X games, but I'm not sure if even they have it universally.
Conversely there's plenty of games where there Is only one thing to do, so there's nothing to do out of order, for example FTL, The Sims, and such.
Requires that there are no mandatory equipment, abilities, keys or such blocking you from going to most places. It's fine if lack of such block optional areas, but not if they block progress in main plot related things.
Games that can be completed in (almost) any order
What about variable practical barriers? For instance, an RPG without keys, required items, or anything except a final boss. The player could literally start the game, walk out of town, walk straight to the evil wizard's lair, navigate to the thrown room, and confront foozle. Except for their lack of power means they will die fighting the 2nd enemy they meet. And beyond stats and equipment, a repertoire of spells/abilities, items, artifacts, pantaloons, are all advantageous to winning and a minimum combination of one or more of them is required yet lacking any one of these will not cause failure by itself.
For instance, an RPG without keys, required items, or anything except a final boss. The player could literally start the game, walk out of town, walk straight to the evil wizard's lair, navigate to the thrown room, and confront foozle.
Would be specifically instance of premature challenge
But as long as they can do the required things in any order it would be fine for this. See Demon's Souls example, it's far from perfect and you can just choose which of the 5 worlds you progress in and you can swap between them whenever you want and continue where you left off in each, but not the sections of said worlds (and you're required to beat them all before you go to the final boss).
I'm mostly wanting some tag for where players can for the most part complete the game in any order even if the final boss will always be final rather than being forced in linear path.
Consider like mission-based games, but all or most of the mandatory missions or mission-chains are available right after you get past the prologue/tutorial. You aren't following a strict linear progression like you would in a movie/book or gamebook.