That works, but almost every method excluding brute force methods has a scenario where it doesn't work, or the character looks very silly finding its path

One scenario for such a method would have the hero running into a tunnel, only to run back out realizing it's a dead-end

Truth is, I don't think there's an all-powerful algorithm out there that can solve every situation efficiently

Best bet is to set up your own custom node tree such-and-such based on your level's design

Have a giant maze thing randomly in your level?
Don't waste resources trying to solve it during run-time, just hard-code the solution in there