Encounters between groups of wild chacma baboons (Papio ursinus) can be viewed as a natural experiment to investigate the nature of these primates' mental representations of large-scale space. During a 16-month field study in a high population density habitat we recorded the foraging routes and the most important resources of a group of 25 individuals. Also, we estimated the locations of additional baboon groups relative to the study group. Routes were less linear, travel speed was higher, and inter-resource distances were larger when other groups were present within 500 m of the focal group; thus, the study group avoided others by taking detours. We predicted that evasive manoeuvres would be characteristic of different possible orientation mechanisms, and compared them with our observations. We analysed 34 evasive manoeuvres in detail. In an area that lacked prominent landmarks, detours were small; larger detours occurred when resources were directly visible, or in the vicinity of a hill offering conspicuous landmarks. In areas without prominent landmarks, detours were along familiar routes and waiting bouts of up to 60 min occurred; on one occasion the study group aborted their entire day's journey. We discuss these findings in the light of time and energy costs and suggest that the baboons lack the ability to compute Euclidean relations among locations, but use network maps to find their way to out-of-sight locations.