We study the behaviour of interacting self-propelled particles, whose self-propulsion speed decreases with their local density. By combining direct simulations of the microscopic model with an analysis of the hydrodynamic equations obtained by explicitly coarse graining the model, we show that interactions lead generically to the formation of a host of patterns, including moving clumps, active lanes and asters. This general mechanism could explain many of the patterns seen in recent experiments and simulations.