Humans efficiently reason about space to navigate and forage in new environments, which may, at least in part, depend on an ability to generalize across tasks and organize observations into patterns that can be re-used. Generalization and transfer learning in spatial domains is evident in mirror-invariant neural scene representations, and in the reuse of reference frames and representations across similar environments. Shared reference frames appear in other mammals as well, as, for example, in rodents reusing grid-cell maps for different but perceptually similar environments. However, the field lacks conceptual and quantitative models of how the spatial system might discover patterns during spatial exploration, how seen patterns might be compositionally combined to represent complex spaces, or how they might be leveraged to represent and navigate through new spaces through reuse. Here we introduce a computational model of “Map Induction”, which involves the compositional formation of proposed maps of complex spaces based on already seen spaces through program induction in a Hierarchical Bayesian framework. The model thus explicitly reasons about unseen spaces through a distribution of strong spatial priors. We introduce a new behavioral Map Induction Task (MIT), and compare human performance with that of state-of-the-art Partially Observable Monte Carlo panning models as well as our Map Induction framework. We show that our computational framework better predicts human exploration behavior than non-inductive models. Understanding the computational mechanisms that support such map learning can generate hypotheses for circuit-level neural representations and dynamics, advance the study of the human mind, as well as support more efficient exploration algorithms.