The Bug Algorithm

I found this super blog post by Matthew Klingensmith on how to implement motion planning. Be warned that his is a long and detailed post on the subject. I found the first few ideas very nice. Then things got a bit complicated. The best part was when he was explaining the theory behind "the bug algorithm". This is a technique for a computer controlled player to get from point A to B if there is an obstacle in the way.

I was happy when reading about the bug algorithm because I realized that I had implemented such a technique when coding up some Angband monster AI. Well let's just say that I implemented a poor man's version of the bug algorithm. I had found that when multiple monsters are trying to move toward the player, they get in each other's way. If I did not code in some smarts to their logic, they would crowd up in a long line. Fail.

But if the monsters could "walk around" obstacles in their way, they could get to the player better. It would look a lot better than the dumb monsters lining up. However I only got around to implementing the monsters going a few positions out of their way to try to avoid the obstacles. The bug algorithm theory let's an AI track the perimeter of an obstacle to get back on the optimal path towards the player. Great stuff I tell ya.