We will try a cartoon style in the texturing, perhaps cell shading. We have a lot of work here, because there will be different sets of textures in the different mazes.
Regarding the history, the reason why the main character is in the maze will be that he entered chasing his girlfriend. She thought it should be funny try to find the exit and the main character followed her after a while. With this idea we can use the voice of the girlfriend to guide across the maze, whispering "you will never find me" or "you are getting close".