How would we implement this? Graph search algorithms like A* are often used to find the shortest path from one point to another point. You can use this for each enemy to find a path to the goal. There are lots of different graph search algorithms we could use in this type of game. These are the classics: One source, all destinations, or all sources, one destination: Bellman-Ford - supports negative weights All sources, all destinations: A game like Desktop Tower Defense has lots of enemy positions (sources) and one destination for all of them. This puts it into the all sources, one destination category. Instead of running A* once per enemy, we can run an algorithm once, and it will calculate the path for all enemies. Even better, it will calculate the shortest path from every location, so as enemies get jostled around or new enemies created, their paths have already been computed. Let's explore Breadth First Search, which is sometimes called "flood fill" (FIFO variant).
Read full article from Pathfinding for Tower Defense
No comments:
Post a Comment