Step 4 is going to be tough. How do you handle concave obstacles?

The article mentions wolves and rabbits, what if a rabbit is in a cave. That is to say the obstacle you need to waypoint around is in fact something you need to go inside of. The wrong waypoints to navigate around the obstacle becomes circle the obstacle indefinitely.

I would probably go with a hierarchical A* that way you can get the high level path quickly and do the local fine grain pathfinding in small chunks as you go.