On flat substrates, several cell types exhibit amoeboid migration, which is characterized by restless stochastic successions of pseudopod protrusions. The orientation and frequency of new membrane protrusions characterize efficient search modes, which can respond to external chemical stimuli as observed during chemotaxis in amoebae. To quantify the influence of mechanical stimuli induced by surface topography on the migration modes of the amoeboid model organism Dictyostelium discoideum, we apply high resolution motion analysis in microfabricated pillar arrays of defined density and geometry. Cell motion is analyzed by a two-state motility-model, distinguishing directed cellular runs from phases of isotropic migration that are characterized by randomly oriented cellular protrusions. Cells lacking myosin II or cells deprived of microtubules show significantly different behavior concerning migration velocities and migrational angle distribution, without pronounced attraction to pillars. We conclude that microtubules enhance cellular ability to react with external 3D structures. Our experiments on wild-type cells show that the switching from randomly formed pseudopods to a stabilized leading pseudopod is triggered by contact with surface structures. These alternating processes guide cells according to the available surface in their 3D environment, which we observed dynamically and in steady-state situations. As a consequence, cells perform "home-runs" in low-density pillar arrays, crawling from pillar to pillar, with a characteristic dwell time of 75 s. At the boundary between a flat surface and a 3D structured substrate, cells preferentially localize in contact with micropillars, due to the additionally available surface in the microstructured arrays. Such responses of cell motility to microstructures might open new possibilities for cell sorting in surface structured arrays.