Walking is the most natural way of moving within a virtual environment (VE). Mapping the user's movement one-to-one to the real world clearly has the drawback that the limited range of the tracking sensors and a rather small working space in the real word restrict the user's interaction. In this paper we introduce concepts for virtual locomotion interfaces that support exploration of large-scale virtual environments by redirected walking. Based on the results of a user study we have quantified to which degree users can unknowingly be redirected in order to guide them through an arbitrarily sized VE in which virtual paths differ from the paths tracked in the real working space. We describe the concepts of generic redirected walking in detail and present implications that have been derived from the initially conducted user study. Furthermore we discuss example applications from different domains in order to point out the benefits of our approach.