My take is that rather than trying to faithfully represent the challenges and obstacles of navigating unknown territory, we should focus on creating the feeling of exploration. And in my evaluation, that feeling comes from the choice to go out of your way to look into something that caught your interest. When you have a clear goal or objective, and you notice something that piques your curiosity but is unrelated to your objective, and you make the conscious decision to put your objective on hold in order to satisfy that curiosity, that feels like you’re exploring.
This is why sandbox video games give you a quest marker on a compass or mini-map, and then litter that compass or mini-map with markers indicating points of interest that aren’t related to your active quest. To give you opportunities to decide to go investigate a point of interest instead of following your quest marker. When this is done really well, you can end up on digressions to your digressions, where you ever off the main quest to check something else out, and then veer off of doing that to go check something else out. And theoretically you could digress off of that, ad infinitum. The more nesting regressions you get, the deeper the exploration feels.