For most first-person video games it is important that players have a high level of feeling presence in the displayed game environment. Virtual reality (VR) technologies have enormous potential to enhance gameplay since players can experience the game immersively from the perspective of the player's virtual character. However, the VR technology itself, such as tracking devices and cabling, has until recently restricted the ability of users to really walk over long distances. In this paper we introduce a VR-based user interface for presenceenhancing gameplay with which players can explore the game environment in the most natural way, i. e., by real walking. While the player walks through the virtual game environment, we guide him/her on a physical path which is different from the virtual path and fits into the VR laboratory space. In order to further increase the VR experience, we introduce the concept of transitional environments. Such a transitional environment is a virtual replica of the laboratory environment, where the VR experience starts and which enables a gradual transition to the game environment. We have quantified how much humans can unknowingly be redirected and whether or not a gradual transition to a first-person game via a transitional environment increases the user's sense of presence.