Labyrinth
A Labyrinth, also called a Barrier, is an otherworld used by witches to conceal themselves. Should a normal human wander in by accident, it is impossible for them to escape.
In the anime, these locations are designed and animated by Gekidan Inu Curry in a style vastly different from that of the rest of the series in order to reinforce the otherworldly aspect. Inside and outside of the anime they are commonly referred to as barriers, likely because they have a barrier element to them, or sometimes as "mazes" (迷路 meiro) or "wards".
According to the January 2012 Dengeki PlayStation, the Barrier is "a space resembling the Magical Girl's mental landscape before they became a Witch", but the landscape often mirrors the labyrinth's location in the real world, twisting it with its own imagery. The barrier's imagery can be based off a lot of things, such as where the girl became a Witch, what their Soul Gem or Grief Seed motifs were, who they were as a person, and/or what their wish was.”
This can be seen by looking at Oktavia von Seckendorff's barrier which has a theme of longing for Kyosuke, since Sayaka's wish was to heal his hand. The ulterior motive behind the wish was for Kyosuke to love her, but this didn't happen. There is a Kyosuke-like figure shown in her barrier. Additionally, she became a witch at a train station, and at the beginning of episode 8 we see trains in Oktavia's barrier, only for them to be missing when its location changes.
A labyrinth's layout is both based on the Witch herself, and also reflects the real-world locations the barrier is situated around, usually changing as it moves. The labyrinth of the same witch can have a completely different layout depending on the location it warps. Barriers can be mobile in various ways, some even capable of direct flight, and the space within them is usually much bigger than the space which they occupy in the real world.
See also: Madoka Magica Trivia#Witch's Labyrinth