This paper presents an adaptive foothold planning method for a hexapod walking robot. A local terrain map acquired with an inexpensive structured light sensor is exploited as the information source for the planning algorithm, which uses a polynomial-based approximation method to create a decision surface. The robot learns from simulations, therefore no a priori knowledge is required. The results show that the method is general enough to work on various types of terrain. The planned footholds enable the robot to walk more stable, avoiding slippages and fall-downs.