Hi, total AI noob here. I'm working on a Tower Defense game in C++ right now, and I've gotten to the point of worrying how my units will decide what path to follow. It's your typical "Desktop Tower Defense" type game. Tile-based level layouts, towers can be built right on the enemies' playing field, as long as placing a tower there won't make it impossible for them to reach their goal, since the towers themselves will become obstacles. The project uses SFML and OpenGL, if that's relevant. Not asking to have it spoon-fed to me. I'm not against learning on my own, I'm just wondering what I should be looking to learn. I don't want to go and learn A* or something and find out it won't work for this situation. Thanks in advance, -Ninja

A* will work ;)

I've seen quite a few A* tutorials that actually use a grid for path-finding/collision, which should work nicely for you.

When the player tries to place a tower mark the grid-square as "blocked", do an A* search from monster-spawn to monster-target. If the search fails, then you know the player has blocked their path and you should delete the tower ("un-block" the grid-square).

Awesome, thanks!

Though that option scales with the number of baddies and can slow down loads if you plan on having a screenful, even if you don't call it every frame.

A big optimisation is to store the paths in each monster and only update when a gun is added or removed.

An even bigger optimisation is to store data in the map instead. If you do a breadth-first search(google) working backwards from the exit, you can store direction arrows in your map, which leaves all the monsters just needing a look up. Fill any unreachable tiles with -1 or something and if a monster ends up in one of those then you just blocked him in.

I do this in my free 3D td game that you can get at http://www.rubicondev.com/Products/defender.htm