Trace fossils record foraging behaviors, the search for resources in patchy environments, of animals in the rock record. Quantification of the strength, density, and nature of foraging behaviors enables the investigation of how these may have changed through time. Here, we present a novel approach to explore such patterns using spatial point process analyses (SPPA) to quantify the relative lateral heterogeneity and optimisation of the foraging strategies employed by tracemakers. SPPA can be extended to trails, trackways and burrows, where the trace fossils are described by line segments. Mark Correlation Functions (MCF) are a type of SPPA which can quantify how spatial autocorrelation of segment lengths and absolute orientations vary with spatial scale. Under an optimal foraging strategy, a trace maker will adjust both the length and orientation of each segment to focus on a preferred resource. If they stray out of the resource area, they quickly turn back, resulting in high directionality of orientations. Therefore, the directionality of trace fossil orientations is expected to be spatially heterogeneous, mirroring the underlying resource, and accompanied by shorter segment lengths to maximize time spent in favourable resource patches. The optimisation of foraging requires two different aspects: the ability to find quality resources, assessed using segment midpoint SPPA; and the ability to focus on these, for which MCF is used. Combining these methods provides a novel approach for identifying the extent of foraging optimisation of tracemakers. To illustrate these methods, we have applied them to two trace fossil-rich horizons, from a critical time in the evolution of animal mobility – the Ediacaran-Cambrian transition. Trace fossils from this interval reveal crucial insights into the development of mobility, novel feeding behaviours and the putative appearance of crown-group metazoans. Indeed, adaptions to optimise foraging strategy – defined here as the exploitation of any resource distributed on the seafloor – have been suggested as potential drivers of early bilaterian evolution and diversification. These analyses hint at changes in the development and optimization of foraging at the Ediacaran/Cambrian transition and highlight the potential of SPPA to tease apart subtle differences in behavior in the trace fossil record.