Expire them by time, refresh them by range (can see as they move). Constantly replan and I bet you'd get something reasonable looking, but _only_ if you add an obstacle that represents only what the creature can see. If you add the whole obstacle (regardless of what it can see), it'll just do the optimal thing, which is fine but may not "look right". So clip visibility with obstacle, add that, and union it with all known obstacles, then replan. Keep it fast by doing a union "in place" with known obstacles so your obstacle list doesn't grow unbounded.
You can imagine it would walk toward the goal until it sees a wall, then it would go either left or right for a step, then back for two steps, then left for 4 steps, then back for 8 ... because the A* "frontier" keeps expanding so it keeps searching along that frontier.
And if you're lucky, you just discovered the optimal search variant of the "Drunkards walk" search problem.
I've worked in planning for a bit, mostly for robotics. I can honestly say that the _planning_ side of making interesting behaviors is really simple. It's the world representation that is hard. In the real world it's hard to build up a good enough representation to do smart things. Most robots can't reasonably see longer than 50 yards/100 yards. In games is hard to build up a bad enough representation to match the partial information in the real world - running just about any planner on the map will just work and probably look too good.
It errs on the side of "stupid" but is much easier to implement.
Ah, I did hear about the Visibility Graph through AI. I didn’t fully understand it due to my lack of knowledge. But with you bringing it up again, I think I should look into that as well. Thank you for your kind response.
https://en.wikipedia.org/wiki/Visibility_graph
On a visibility graph you can run any search algorithm. The key thing is this graph is sparse (the number of nodes is really limited by the amount and complexity of the obstacles, not the distances).
This algorithm follows almost perfectly your outlined steps. In particular it draws a line to the destination, and if it encounters an obstacle it "walks" paths (generates successors for A*) along the exterior of an obstacle until it can "See" (draw a straight line to) the destination or another obstacle. By using "obstacle free distance to destination" as a heuristic at each node, this will provide optimal paths.
You can, just from the wikipedia page, deduce a good response to the problem of "select the optimal point for bypassing the obstacle". (Maybe try the vertices of the convex hull / AABB - and don't worry, it may take a few iterations to truly wrap around an obstacle)
This will perform much, much better on sparse environments than a grid, because a grid has to iterate O(n) for n grid cells, while a visibility graph has to iterate O(n) for n obstacles (of a given complexity).
Very nice!