Space Engine. It's not quite a game, but rather an accurate simulation of the known universe. Anything beyond what we know is procedurally generated. The first time I played it it made me feel so small.

I started at Earth and flew around the solar system, then picked a star and flew towards it. You have to increase your speed by multiples of the speed if light to get them to move. The stars started moving and then moving past, me, but the star I chose wasn't moving. I realised it was actually different galaxy, so increased my speed by many many multiples of the speed of light until eventually it dwarves to move. I flee over to it, and then slowed and explored a few star systems there, I found a binary star system, that was really cool.

Then I had a realisation. If I didn't use the search function, and I just flew around trying to find my way back to Earth, I just never would. I could play it for the rest of my life and be certain that I wouldn't find it. The odds are that small. That thought scared the shit our of me and I closed the game and couldn't okay it again for a few days.

Don't know if that's what you're looking for but I do recommend the experience!