We introduce a model of traveling agents ({it e.g.} frugivorous animals) who feed on randomly located vegetation patches and disperse their seeds, thus modifying the spatial distribution of resources in the long term. It is assumed that the survival probability of a seed increases with the distance to the parent patch and decreases with the size of the colonized patch. In turn, the foraging agents use a deterministic strategy with memory, that makes them visit the largest possible patches accessible within minimal travelling distances. The combination of these interactions produce complex spatio-temporal patterns. If the patches have a small initial size, the vegetation total mass (biomass) increases with time and reaches a maximum corresponding to a self-organized critical state with power-law distributed patch sizes and Levy-like movement patterns for the foragers. However, this state collapses as the biomass sharply decreases to reach a noisy stationary regime characterized by corrections to scaling. In systems with low plant competition, the efficiency of the foraging rules leads to the formation of heterogeneous vegetation patterns with $1/f^{alpha}$ frequency spectra, and contributes, rather counter-intuitively, to lower the biomass levels.