Rudimentary pathfinding/collision detection

[Thurinus]

hey everyone,

I have a question regarding seemingly relatively simple collision detection and pathfinding. Thus far I've been doing pathfinding using the A* algorithm and nodes, but I want to do something simpler for a current project.

Simply put, I just want a character to traverse directly from point A to point B, and pillar-hump around any obstacles he encounters. Of course, if the unfortunate character walks into a concave area, he would never be able to get out... that's fine. Here's an illustration of the initial setup, what A* will do, and what I actually want to do:

http://thurinusworks.com/public/pathfinding.jpg

I was wondering if anyone here has ever done this, and if so, could suggest the best way to go about doing it?

Thanks for any suggestions folks!

Jay

[Sirisian]

I've heard of the algorithm called a few things. A book I have calls it the crash and turn algorithm. It's really simple.

while(!reached the destination)
{
if you can move in a straight line to the destination do so.
else
{
go left or right and move along the direction of the wall (the tangent of the circle in your example)
When you can go straight again go towards the target.
}
}
I used this algorithm in a game I made before. Works well.

http://sirisian.pastebin.com/f2d380dd3 Also I'll leave this link here in case you need 2D intersection functions. (For instance, finding where a ray intersects a circle and such). Might be useful.

[Thurinus]

Thanks for the reply, Sirisian :)

In my example I had used a circle for simplicity's sake, but if the obstacle's shape is irregular, I'd imagine that calculating the normal of point at which the player hits an obstacle to determine a pillar-humping path would be more accurate. Is this easily possible in Flash/AS3? If so, how would you do it?

I'm not good at uber-advanced mathematics, so any algorithm help would be great, I think!