This paper describes how a cognitive architecture builds a spatial model and navigates from it without a map. Each constructed model is a collage of spatial affordances that describes how the environment has been sensed and traversed. The system exploits the evolving model while it directs an agent to explore the environment. Effective models are learned quickly during travel. Moreover, when combined with simple heuristics, the learned spatial model supports effective navigation. In three simple environments, these learned models describe space in ways familiar to people, and often produce near-optimal travel times