The role of stochasticity and spatial heterogeneity in foraging systems is investigated. We formulate a spatially explicit model which describes the behaviour of grazing animals in response to local information using simple stochastic rules. In particular the model reflects the biology in that decisions to move to a new location are based on visual assessment of the sward height in a surrounding neighbourhood, whilst the decision to graze the current location is based on the residual sward height and olfactory assessment of local faecal contamination. It is assumed that animals do not interact directly, but do so through modification of, and response to a common environment. Spatial heterogeneity is shown to have significant effects including reducing the equilibrium intake rate and increasing the optimal stocking density, and must therefore be taken into account by resource managers. We demonstrate the relationship between the stochastic spatial model and its non-spatial deterministic counterpart, and in the process derive a moment-closure approximation to the full process, which can be regarded as an intermediate, or pseudo-spatial model. The role of spatial heterogeneity is emphasized, and better understood by comparing the results obtained from each approach. The relative efficiency of random and directed searching behaviour in spatially heterogeneous environments is explored for both clean and contaminated pastures, and the impact of faecal avoidance behaviour assessed.