Is the hex roll done by the GM or is it player facing in your group? I have a player that made an exploration focused character, and since we don’t use guns in this campaign, i want to allow him to put effort into travel.
Also, what other ways have you incorporated exploration with your party abilities?