Maybe do it as a stacked maze, consisting of two or more levels?
Fighter in the narrow corridors of a maze below, the rest of the party is in a gallery-sized room above with a glass floor so the top group can watch the progress of the character below. The maze is divided into sections, so the person below has to reach certain points in the maze to open valves/doors that allow the group up top to enter a new gallery themselves.
Could be complicated by shifting walls, sections of mist-filled corridors, elevation changes, pits and other traps, etc.
Further, it could be the party in the section above has to figure out puzzles to aid the character in the maze below (buttons that open certain doors/move walls that could impede, open or alter the path - or even release monsters; a rubik's like cube that when solved transports a beneficial object to the character below, but if not solved quickly enough adds some element of danger to the mazewalker's trek; a dumbwaiter/chute that allows the party to pass down or extract an object - such as a key - if the mazewalker can reach the object, etc.)
The movie Labyrinth, Maze Runner and Cube (especially Cube Zero for your scenario) may have ideas worth pulling in - most of these have the concept of the "moving maze" in them as well.