The inability to navigate independently and interact with the wider world is one of the most significant handicaps that can be caused by blindness, second only to the inability to communicate through reading and writing. Many difficulties are encountered when visually impaired people (VIP) need to visit new and unknown places. Current speech or haptics technology does not provide a good solution. Our approach is to use treadmill-style locomotion interface, unconstrained walking plane (UWP), to allow a richer and more immersive form of virtual environment (VE) exploration to enable VIP to create cognitive maps efficiently and thereby to enhance their mobility. An experimental study is reported that tests design of UWP for both straight walking and turning motions. Two groups of participants, blind-folded-sighted and blind, learned spatial layout in VE using two exploration modes: guided (training phase) and unguided (testing phase). Spatial layout knowledge was assessed by asking participants to perform object-localization task and target-object task. Our results showed a significant decrease in time and helps taken to complete tasks, subjective workload, and errors in a post-training trial as compared to a partial-training trial. UWP has been found to significantly improve interaction with VE with visualizations such as spatial information. (Contains 4 tables and 7 figures.)