For some time I have been working on a framework which should make it possible to generate 2D levels based on a set of rules specified by level designers. You can read more about it here as I won't go into details: http://www.jorisdormans.nl/article.php?ref=engineering_emergence

Anyway, I'm now at the point of putting the framework to use and have trouble coming up with a solution for AI.

I decided to implement a NavigationMesh in the generated levels as I already have that information to start with. Consider the following image (borrowed from http://www.david-gouveia.com/pathfinding-on-a-2d-polygonal-map/):

When I run A* on the NavigationMesh, the red path would be suggested when I want to go from point A to B (either direction). However, I don't want my AI to walk that path directly and clipping corners, I'd rather want them to follow the more logical black path.

How would I go about going from the Red path to the Black path, are there any algorithms for this. Which steps do I take? Is A* the proper solution for this at all?

For some additional information: The proof-of-concept game is a 2D top-down game written in C#, but examples/references in any language are welcome!