Designing for embodied physical interaction is just as important at a coarse level of spatial navigation as in the minutiae of object exploration. We created interactive embedded interfaces called 'Navitiles' that can be suspended in a floor to support navigation of a building. Our design uses capacitance and RFID sensors to determine users' location and LEDs to indicate possible directions. We determine whether Navitile cues could help users understand spatial relationships between points of interest. We based our study on a previous experiment that used a simulated VR maze to test whether users were able to exhibit 'shortcut' behaviour that would indicate the formation of spatial maps. Our hypothesis was that the physicality of embodied spatial navigation directed by the Navitiles in a real maze would enable users to achieve similar spatial shortcut behaviours to those found in the virtual task. We found significant evidence that sufficient spatial knowledge was acquired to enable successful shortcut performance between unexplored routes. However, further work is required to measure the effect of physical body movement on spatial skills development.