Walking has always been the most common locomotion mode for humans in the real world. For this reason, walking has also been considered as the ideal condition in a large body of VR research involving navigation. Physical walking provides body-based sensory information about both the translational and rotational components of locomotion. Though the rotational body-based information has been shown to be important for several spatial tasks, the benefit of the translational component is still unclear with mixed results from previous studies. In this study, we aim to investigate how much translational body-based sensory information is required for people to efficiently navigate the virtual world, given full rotational information. Depending on the locomotion interface used, more or less translational body-based information might be provided at different levels of accuracy. The current mixed method study investigated how different levels of translational body-based information might influence the performance of participants in a navigational search task in a HMD-based virtual environment. Participants were asked to find eight balls hidden in 16 target boxes randomly positioned in a two-meter radius circular area. To check whether there is a ball inside a target box, participants must stand right in front of the box within 0.80 meter and look at it. If there is a ball, they can collect it by touching the ball with a wand controller. The environment has been designed not to provide any additional orientation cue other than the optic flow from the fireflies. Participants could not see targets farther than two meter from them. In other words, they were not able to see all targets at a time, hence, they had to build up their spatial awareness gradually along with their locomotion. In this within-subject experiment, there were four levels of translational body-based information: none (participants used the trackpad of an HTC Vive wand controller to visually translate), upper-body leaning (participants sitting on a Swopper chair, used their upper-body leaning to control their visual translation), whole-body leaning (participants standing on a platform called NaviBoard, used their whole body leaning or stepping to navigate the virtual environment), and actual walking (participants physically walk with a wireless HMD on). Every participant performed a navigational search task once in every condition in a counter-balance order. All 24 participants finished all four trials (even with more or less fatigue). Results showed that locomotion mode had significant effects on various measures including task performance, task load, and simulator sickness. While participants performed significantly worse when they used joystick-based interface with no body-based information, compared to the other conditions, there was no significant difference between leaning-based interfaces and actual walking. More data in other measures are still in need for a more concrete conclusion. However, current results also suggested that body-based information from a leaning-based interface might suffice for a cost-effective alternative to actual walking in spatial cognition research and applications in VR.