Hi, I'm currently programming a Tower Defense game in OpenGL for my computer graphics course and I have a question concerning A*. I would first like to mention that I'm not using any external libraries for this project as I have to program the game myself for marks. Also I have little experience beyond coding to basic A* algorithm, so please be explicit in your response. I would like to know how I should use the A* algorithm when I'm dealing with many units. Do each of the units have to calculate a separate path, or is there a better way to update the paths when a new tower is added to the map. I'm assuming that each unit is using tiles that are 4 times smaller then the tower tiles, and that paths are recalculated when a new tower is added. Any advice or information would be greatly appreciated. Here is a link to the game I'm trying to remake for my project. http://www.handdrawngames.com/DesktopTD/Game.asp Thanking you in advance

Since all the units are going to the same place, you can run Dijkstra's algorithm from the goal, to find the distance from each tile to the goal. Then the units can access that map of distances to the goal to decide at each step where to go next. When the user puts a new turret down, rerun Dijkstra's algorithm.

If it helps you in your googling, the distance from the goal is called the cost-to-go, and a Dijkstra-like algorithm used to calculate it is sometimes called the brushfire algorithm or distance transform. The idea is that once you have the cost-to-go function, the optimal thing for any agent to do, no matter where it is, is to look at its neighbor tiles and to move to whichever of those has the lowest cost. Such a rule for what to do no matter where you are is called a policy.

Given that tower defense maps are usually small and are most of the time static, it may pay off to create a table of paths from each point in the map to the end. Each time a gamer places a new tower you'll need to update the paths on the table that use that tile, and you won't be able to have moving towers (or any other path blocking object for that matter) in your game, but you'll be able to add has many creatures as you want to the map without worrying about performance.

You could check http://www.cgf-ai.com/ which currently has 'Multi-Unit Planning with HTN and A*'
There used to be a couple of good articles by Dave Pottinger in the Resources list called Coordinated Unit Movement and Implementing Coordinated Movement but the links no longer go to the papers. You might search for them.

With such a small map A* should perform flawlessly.
Simply disable nodes where towers are added and enable nodes when towers are destroyed.
Should be no problem! :)

Thanks for the replies. I also wanted to know if I should use a fixed size grid for the A* or if a quadtree would help improve performance. If quadtrees are the better solution, I was wondering if someone would have some sample code that would show how the A* algorithm traverses a quadtree. I've read a few articles on the subject but I still lack a complete example that shows how they are integrated.

Quote: Original post by nietger
Thanks for the replies. I also wanted to know if I should use a fixed size grid for the A* or if a quadtree would help improve performance.

Depends how big your grid is. I'd be very surprised if a tower defence game had a grid large enough to warrant the extra complexity of doing it over a hierarchical structure. (Which is what I assume the quad-tree would be for - the typical quad-tree properties would seem to be less useful for A* really.)

Just got my A* to run with a binary heap for the open list and a hash map for the closed list. Improved performance by just over 30%

Excellent! Do you think it would be possible to post some code using your heap and hash table?