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. We demonstrate the relationship between the stochastic spatial model and its nonspatial 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 optimal stocking density is shown to be different in the spatial and nonspatial models. The relative efficiency of random and directed searching behaviour on both clean and contaminated pastures is explored, and the impact of faecal avoidance behaviour assessed.