Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can someone suggest papers or algorithms about calculating shortest paths in Euclidean spaces with non-convex polygon as obstacles?

share|improve this question
Note that unless your start point, end point or another polygon lies in the space between a non-convex polygon and its convex hull, you can replace the non-convex polygon by its complex hull. Easy to see by just drawing a non-convex polygon and its convex hull, then considering which shortest paths go through the difference. – MSalters Jan 24 '14 at 8:28

The simplest approach is to turn the non-convex polygons into multiple convex ones, then do normal convex collision and pathfinding (via A* or D* or whatever). The first process is often called triangulation in computational geometry, and there are several common ways to do it.

share|improve this answer

This may not be the exact answer to your question but I may suggest you an approach on this issue.

Actually your problem is two problems combined.

  1. Finding shortest paths
  2. Finding collisions

And the second problem is embedded into first. I may recommend understanding blind search first. Here's a very simple presentation about it: Blind Search

If you read the document for building the state space, you will need to generate state points and they must be legal meaning these states can be on your shortest path so they shouldn't collide with any objects in your space. From now on you can continue with Euclidian collision algorithms. After building your state space and search tree restricted with collisions you may chose any of the shortest path algorithms or one of your own or a modified hybrid one.

share|improve this answer

Your Answer


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.