I think you would have to go back to more classic genetic algorithm/pet training methods: Iterate through increasing "distance" to the goal. Initially make the goal simple/immediately available, then slowly "distance" them from the goal, with more obstacles/etc introduced between, as you go.

For a homing pigeon, this would be literal, driving further and further each time you release them.

For an agent that you train to walk, this would be flat surface to past some line, then introduce speed reward, then non-flat surfaces, then obstacles, then curves, etc [1].

[1] "AI Warehouse" channel is all about training AI for light gaming tasks: https://www.youtube.com/watch?v=L_4BPjLBF4E