here 4 schemas : (i'm not a real artist ^^)
http://dl.dropbox.com/u/12423314/tuto%20pathfinding/1-initial.svghttp://dl.dropbox.com/u/12423314/tuto%20pathfinding/2-first%20path.svghttp://dl.dropbox.com/u/12423314/tuto%20pathfinding/3-path%20found.svghttp://dl.dropbox.com/u/12423314/tuto%20pathfinding/4-explanations.svgthis algorithm is a graphnode.
the first thing to do is to find a polygon on the line from the start point, to the end point. (your "first" node)
Next, you need to circle the obstacle, so you find the segment, you create 2 nodes for the 2 points of the segment, and you place a distance equal to the radius of your shape on the 3 positions ( before, next to, after, schema 4 ) you've got by :
px => the segment point
pi => intersection point
p1, p2, p3 => the solutions
r => shape radius
if px.x > pi.x AND px.y < pi.y THEN
# \ ----- pi
# \ / we need that path
# \ px
# extend the straight line (pi;px) and find the point p1, extend the adjacent straight line, and find the bisector between them
p1.x = px + r
p1.y = px.y + r
p2.x = px.x +r
p2.y = px.y +r
// used to test if next position is valid
p3.x = px.x - r
p3.x = px.y + r
// and you always test if p1/p2/p3 is in a polygon
I know it's very expensive and do better, but i'll optimise after. There's also a problem because the radius is larger and is on the segment (p1, p2) and (p2, p3), but it's nearly nothing.
I may have done english mistakes (i'm French), and mathematics mistakes (i'm 15) so check all that on the paper
.
In addition, i use for the polygon a powerful class of my engine, and use a context to save them and use them in a query.