[gjstein]

So far, no one has mentioned "Bug Algorithms", which have a similar structure of (1) walk in the direction of the goal, (2) walk around obstacles as they are encountered, (3) leave the obstacle to proceed when some condition is met. They are very simple to implement (though not optimal) and there are a number of variants to play around with. Howie Choset has some good lecture slides that describe them [1]. However, as some others have mentioned, something like Jump Point Search [2] is likely a better option given the described scenario.

[1] https://www.cs.cmu.edu/~motionplanning/lecture/Chap2-Bug-Alg... [2] https://en.wikipedia.org/wiki/Jump_point_search

[Animats]

I've done that something like that.[1] It's appropriate where there's a significant cost to detecting obstacles, because it tests few unnecessary cells.

It heads to the goal until an obstacle is reached, then follows the wall. Unusually, it forks and follows both the left and right wall simultaneously. It's not always optimal, but the optimal algorithms such as A* have to test more cells.

This algorithm runs my NPCs in Second Life.

[1] https://github.com/John-Nagle/lslutils/blob/master/npc/obsol...

[Farer]

Oh, thank you. I'll have to take a look at the source code as well.

[Farer]

Oh~ This is definitely worth referencing as well. Thank you for the information!