Agent-based, spatially-explicit models that incorporate movement rules are used across ecological disciplines for a variety of applications. However, appropriate movement rules may be difficult to implement due to the complexity of an individual's response to both proximate and ultimate cues, as well as the difficulty in directly assessing how organisms choose to move across their environment. Environmental cues may be complex and dynamic, and therefore, movement responses may require tradeoffs between preferred levels of different environmental variables (e.g., temperature, light level, and prey availability). Here, we present an approach to determine appropriate movement rules by setting them as heritable traits in an eco-genetic modeling framework and allowing movement rules to evolve during the model rather than setting them a priori. We modeled yellow perch, Perca flavescens, movement in a simulated environment and allowed perch to move in response to high-resolution vertical gradients in temperature, dissolved oxygen, light, predators, and prey. Evolving movement rules ultimately increased fish growth and survival over generations in our model, indicating that evolving movement rules led to improved individual performance. We found that emergent movement rules were consistent across trials, with evolved movement rules incorporating different weights of these environmental factors and the most rapid selection on temperature preference. This case study presents a flexible method using eco-genetic modeling to determine appropriate movement rules that can be applied to diverse scenarios in spatially-explicit ecological modeling.