# Making an AI walk on a NavigationMesh (2D/Top-Down game)

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!

-

I would keep the A* algorithm as it is and calculate the tangents to the white circles or to other circles with an appriopriate size. You can then either connect the tangents with sharp angles or walk along the cirlce up to the next tangent.

The radius of the circles have to be less or equal to the half distance of the next point.

-

Yes, A* is still suitable for this. If you don't want your AI to "cut corners" you need modify the navigation mesh to remove corners. You just need to make sure your navigation mesh only has nodes that are a minimum distance from solid objects. These are the steps I would add to your current algorithm:

1. Generate nodes as you do above.
2. For each surface the node touches, collect its normal.