Spatial computing systems are characterized by the extended physical environment in which they exist and function. Often this environment can be manipulated in various ways by the computing agents. We argue that it is important to consider the potential use of the environment for coordination and indirect communication in such systems. For inherently spatial problems, it can be more effective to store spatially relevant information in the environment rather than in the computing devices, as in the case of mobile agents or long-term physical structures. In scientific settings, considering the role of the environment can illuminate mechanisms or processes that might otherwise be overlooked; in engineering problems, it can provide simpler and more effective solutions than could be achieved by relying on the computing devices alone. We give as examples problems related to foraging, collective construction, simultaneous localization and mapping, object tracking, and behaviors of living tissues. We suggest in closing a classification scheme for capabilities of environmental elements, relevant to the design of physically embodied spatial computing systems.