Procedural doesn’t mean random, just generated from a set of rules. These rules can have inputs that lead to different results and you get randomness by randomising those inputs.
What’s Intresting is this this exactly how most random number generators work because computers can’t be random. They take a “seed” value and will always produce the same list of “random” numbers for a given seed. This means you can randomise all kinds of numbers in your procedural generation code but always get the same output if you give the random number generator the same seed.
So in No Man’s Sky, for example, each planet basically has a set seed so the game will generate the same planet, on the fly, for everyone one who visits it in game. Which is why them tooting their own horn about having a whole galaxy to explore was a bit of red flag. All it meant was they generated a massive list of seeds which would have results limited by the tooling next to none of which they’d have been able to review etc.
Which is a long winded way of saying they’ll basically create the world using procedural tools and save the inputs used so the game can generate the same fixed map for everyone that plays with out having to store/load a world’s worth of data.
The obvious suggestion is Destiny 2, it’s a coop Bungie shooter with emphasis on movement. The expansion campaigns are fun and challanging on Legendary difficulty. Only thing it’s missing is the physics sandbox.
Epic is currently giving away the the Legacy collection for free which has three of the four current expansions. Absolutely worth grabbing and giving a go as I’d recommend to anyone starting the game to just focusing on going through the campaign as you’ll probably have a good, if confusing, time. The big downside is the fact you get thrown in half way through the second game in the serise so if you want to understand the story you will need to look things up.