The spatial structure of the environment (e.g., the configuration of habitat patches) may play an important role in determining the strength of local adaptation. However, previous studies of habitat heterogeneity and local adaptation have largely been limited to simple landscapes, which poorly represent the multi-scale habitat structure common in nature. Here, we use simulations to pursue two goals: (1) we explore how landscape heterogeneity, dispersal ability, and selection affect the strength of local adaptation, and (2) we evaluate the performance of several genotype-environment association (GEA) methods for detecting loci involved in local adaptation. We found that the strength of local adaptation increased in spatially aggregated selection regimes, but remained strong in patchy landscapes when selection was moderate to strong. Weak selection resulted in weak local adaptation that was relatively unaffected by landscape heterogeneity. In general, the power of detection methods closely reflected levels of local adaptation. False positive rates (FPRs), however, showed distinct differences across GEA methods based on levels of population structure. The univariate GEA approach had high FPRs (up to 55%) under limited dispersal scenarios, due to strong isolation by distance. By contrast, multivariate, ordination-based methods had uniformly low FPRs (0-2%), suggesting these approaches can effectively control for population structure. Specifically, constrained ordinations had the best balance of high detection and low FPRs, and will be a useful addition to the GEA toolkit. Our results provide both theoretical and practical insights into the conditions that shape local adaptation and how these conditions impact our ability to detect selection.