Instead of a maze with impenetrable walls, make them of varying heights which can climbed over with varying amounts of effort.
Inspired by labyrinths in Zelda BOTW whose walls can be climbed over (though they are all the same height).
Get to the goal with the least amount of effort. Or, the player can choose how difficult the maze is by self-imposing constraints on the amount of climbing.
From another perspective, it's a 3D shortest path problem, especially if you are allowed to walk on top of walls.
This simplifies the problem for the maze designer who doesn't have to worry about making a maze that is accidentally unsolvable or too easy.
What distribution of wall heights yield entertaining mazes?
EmoticonEmoticon