About the "time wasting" complaint, I actually think HK circumvents the issue while remaining ridiculously non-linear in what is a stroke of pure genius.
The map mechanic. Maps are always close to area entrances, and very well hinted at through Cornifer's humming and his paper trails. This makes the act of finding him feel rewarding and engaging without it being a complete freebie for the player, and also one of your first priorities when entering one for the first place. So you get your map, but it's only partially filled, and with the quill you can sit at benches and update it with newly found rooms. So what makes exploration not a waste of time, even if you found one of the (very few) paths that are closed off to you? You backtrack to a bench to save and be able to start a new "expedition" in a new direction, and you still get *something*; the updated map, now a little more filled in.
The usual map mechanics where they get auto-added to your map don't quite work the same way, because they don't make you backtrack. You feel at a loss about what to do next when you hit a wall. But in Hollow Knight, the act of having to go back to a bench reorients and anchors you back at a place you know, or one that you just discovered that will branch off in different directions, and that's genius, IMO, it makes exploration never feel like a waste of time, and it lets backtracking always feel like it has a purpose. It's a small detail but it makes a huge difference.
