While beneficial for spatial knowledge acquisition, the ability to walk freely in virtual reality (VR) can be impractical to implement. Several locomotion algorithms can reduce the amount of space necessary to allow for walking in VR, but it remains unclear how these techniques affect spatial cognition. We conducted an experiment to investigate whether redirected walking (RDW) techniques that preserve the ability to walk are a viable approach to train spatial knowledge. Fifty-nine participants completed virtual training scavenger hunts to find equipment in a submarine’s auxiliary machine room (AMR) in one of three conditions: one with resets only (Reset-Only), one with resets and RDW (RDW+R), and a third Freewalk condition where no RDW techniques were employed. Participants were later tested on their ability to locate the items in the virtual environment (VE) without aids, as well as complete a map placement test in which they placed icons representing the 16 pieces of equipment onto a 2D map of the AMR. Overall findings were mixed. On the VR search task, participants did not differ significantly in their ability to correctly locate scavenger hunt items. However, on the 2D map placement test, participants in the Freewalk condition significantly outperformed those in the RDW+R condition. Additionally, participants reported significantly higher levels of cybersickness in the two RDW conditions and cybersickness was negatively associated with performance on the map-test. Thus, locomotion methods that preserve physical space may be viable when space is limited, but potentially at the cost of learning outcomes and cybersickness.