In natural settings, animals navigate richly-structured sensory surroundings and rapidly adapt to changes in these surroundings. While many studies have explored navigation in mazes and open arenas, relatively little is known about how animals navigate in terrain that lacks defined routes and is too complex to trivially memorize. Here, we probe the structure of mouse behavior in a complex, reconfigurable 3D arena in darkness and without explicit reinforcement. Within the first several hours, mice quickly explore the whole arena and converge on a sparse set of running and jumping paths. Surprisingly, after this initial phase of exploration, mice continue to generate new long paths for several days. To capture this structure in the behavior, we develop algorithms to investigate if the learning of these long repeating paths could be based on hierarchical compositions of shorter repeated sub-paths, or "motifs". To study the evolving dynamics of these compositions, we extract the times at which individual motifs occur. By comparing the emergence timing among sets of connected motifs, we find at least three classes of dynamics: motif emergence, motif replacement, and motif composition. To gain insight into the learning rules that might underlie these compositions, we introduced a local perturbation to the arena that interacted with existing composite paths. Surprisingly, this small change caused a rapid global reconfiguration of composite paths. The fast emergence of these novel paths suggests mice learn a large latent reservoir of spatially extended motifs that could be used to quickly respond to new environmental changes. More generally, our results provide a lens for studying complex, long-timescale behavior by quantifying its compositional structure.