Enhancing the A* Search

When you run the PathFindingTest demo, you might notice some strange behavior in the bots related to the portals. Because the BSP building process splits polygons, sometimes a few portals can exist within a convex room. So, when the bot travels from portal to portal, it occasionally won't travel in a straight line from the bot to the player, even though it looks like it should. You can fix this in a few ways. One way is to do extra checks at runtime to see if you can skip a portal in the path. For instance, instead of traveling from portal A to B to C, you would just travel from A to C if there was nothing in the way to block you. Another way is to just define the portals yourself by hand, like we mentioned before. Yuck, right? A third way to fix this is what we implement in the next chapter. In that chapter, if a bot can "see" the player, it can just head straight toward it. This isn't a perfect solution, considering things such as small holes the bot could see though but not travel though, but combined with other AI abilities, it works well. Another idea is to enhance a path by smoothing out the corners using a Bézier curve. This way, instead of making sharp turns, the bot gradually turns around a corner, presenting a more natural movement. Finally, some larger worlds might be so big that doing an A* search between frames could cause a visible slowdown. What you could do is create a low-priority "worker" thread which has the sole job of calculating paths. A bot could make the request to the worker to calculate a path, and later the worker would signal to the bot that the path was found. Keep in mind that this worker thread would work only if there was just one of them. Only one path should be found at a time because various fields of AStarNode are changed during the searching process. Two threads modifying nodes at the same time will destroy the path. So, the worker thread could hold requests in a queue (such as a one-thread ThreadPool from , "Java Threads") and perform all path calculations in that thread. Also, remember that the PathBot knows nothing of the A* search—all it does is follow the path given to it by a PathFinder. As we mentioned earlier, this means you can modify your underlying search algorithm or give a bot other interesting paths to follow. You'll actually create several different path patterns in the next chapter.