Path Finding

KEY TOPICS

• Path-Finding Basics
• Some Initial Path-Finding Attempts
• Basics of the A* Algorithm
• Applying the A* Algorithm
• Using the A* Algorithm with a BSP Tree
• Generic Path Finding
• Making a PathBot
• Enhancing the A* Search
• Summary

Don't you just hate it when you're just hanging around the city, minding your own business, when all of a sudden a bunch of ninjas jump out and attack you? You knock a few of them out and make a quick getaway, running around buildings and diving in alleys, but next thing you know, a bunch of ninjas jump out at you again. No matter what you do, the ninjas find you. Does this ever happen to you? Anyone? What you might be wondering is how those ninjas always seem to find you, what they could possibly want, and whether the writer of this tutorial has questionable sanity. In this chapter, we deal with the first thing you might be wondering: how the ninjas found you. Specifically, we talk about some path-finding algorithms and implement a generic A* search. This search algorithm allows ninjas to find you no matter where you are. Also, a good path-finding algorithm is essential to artificial intelligence, so we'll use what we create in this chapter when we talk about AI in , "Artificial Intelligence."