Shortest Path Around Obstacles?


I’m making a game in Actionscript 3.0. It’s not the first time I’ve made a game, so I do have a bit of experience - but that bit is all I have. So, I apologize for any newbishness in my post.

Anyway, I am having problems moving an object from one point to another, with rectangular obstacles in between. So far, my code is something like this:

  1. If the object is moving towards an end point and is touching an obstacle…
    2) Send two “ghost” objects clockwise and counter-clockwise around the obstacle.
    3) Move the “ghosts” to the verticies of the rectangle (CW or CCW)
    4) Keep moving around the rectangle until this obstacle no longer obscures the path to the end point
    5) Return the shorter path around the rectangle (CW or CCW) to the object, and make the object move along this path.

For example:

Here, the object (red square) needs to get around the obstacle (black square) to the end point (green square). So, it follows the red path.

This is ok, but probably way too simple, and problems come up like this:

The second obstacle obscures the path of the ghost.

I don’t like this method at all, but it was the only thing I could come up with. Creating the “ghosts” and then moving them around verticies turns out to be pretty intensive too, and, as in the final project, I plan on including much movement and graphics, I want this to be as efficient as possible.

I need a way to efficiently make the red object find this path to the green square:

Or, whatever the shortest path around the obstacles happens to be. I want the object to be able to find the shortest, “smartest” path before it actually hits the obstacle.

If I could get some help with this problem, I would greatly appreciate it!