Not a fan of ruby but sounds to me the classic A* path finder is the best solution for this type of issue.
Here is an abstract version I created in C# a while back
I will be re-writing this in F# at some point in my Building a roguelike in F# from scratch series :)
The C# one could be better but I was playing with immutable state in C# at the time so this one is a little over verbose, no native immutable state in C#.
Well the twist is that the maze is hidden. So you have to discover before you can path :)
If you want, you could port the game logic to C# or F# so others can participate too :)