While only continuous motions are possible, the way in which contacts appear and disappear confers to legged locomotion a characteristic discontinuous nature that is traditionally shared by the algorithms used for legged locomotion planning. In this paper, we show that this discontinuous nature can disappear if the notion of collision is well redefined and we efficiently solve two different practical problems of legged locomotion planning with algorithms based on an approach that establishes a bridge between discrete and continuous planning. The first problem consists of reactive footstep planning with a biped robot and the second one consists of nongaited locomotion planning with a hexapod.