Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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/):

Red path = A* generated path | Black path = Preferred path

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!

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer

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.
  3. Add all normals together.
  4. Scale resulting vector by appropriate scale (whatever the size of your AI unit is)
  5. Displace the navigation node by scaled vector.
  6. Check node to ensure no surfaces are within x distance, if surfaces found, remove node. This means that you're in a tight corridor that you can't fit a unit through.

You have some options for when to do this. You can do it when you generate your navigation mesh, or you can do it after a path has been found.

If you're doing this when the navigation mesh is generated, you'll have to use the size of the largest unit for your offset. That may negate some paths for smaller units. If you're doing it when finding a path, you may have to path more than once if you find that you've sent a unit down a path where it won't fit.

share|improve this answer

You can use an internal point in the triangle (like the centroid) as A* nodes instead of the vertexes. Also, you can pre-proccess the nodes and elimitante the ones that are too close to a wall (like <0.5 meters or something like that). This will ensure that the AI don't touch the walls.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.