Abstract: Locomotion in Virtual Environments is currently a difficult and unnatural task to perform. Normally, researchers tend to devise ground-floor based metaphors, to constrain degrees of freedom (DoFs) during motion. These restrictions enable interactions closer to the way people walk in real life to provide high interaction fidelity. However, flying allows people to reach specific points in a virtual scene more expeditiously. Our experience suggests that high-fidelity techniques may also improve the flying experience, even though flying is not innate to humans, which requires the simultaneous control of multiple DoFs. We contribute the Magic Carpet, a family of methods that combines a floorproxy with a full-body representation, to avoid balance and cybersickness issues. This design allows separating degrees of freedom by addressing the indication direction and speed control travel phases travel separately. thereby promoting techniques with higher interaction fidelity. To choose the best representation suited for our design space, we implemented novel navigation metaphors while exploring different avatars with varying levels of either graphical or perspective fidelity. To validate our design space, we proposed two complementary studies, one for each travel phase. In our experimental evaluation, we present the results of both studies and identify the best suited techniques to be used in combination in the Magic Carpet approach. We applied both objective nd subjective measurements to evaluate efficiency, level of presence, and side-effects of the tested techniques inside our design space, such as physical fatigue and cybersickness. Our results show that the Magic Carpet family of methods supports novel techniques with a high degree of interaction fidelity for flying. While high interaction fidelity techniques are seemingly not the most efficient, the methods we explored allow a more precise speed control wrt other flying techniques. To prove the flexibility of our design space we conducted an additional evaluation with three Target-based techniques to assess both speed and transitions afforded by these techniques. Experimental Results show that methods that provide immediate user translation perform best and that phase transitions do not improve travel quality factors.