   AI-controlled beings finding ideal targets in a tile-based map
  I am working on a game (Titled Zombie City Tactics) that requires enemy AI more advanced than I'm used to working with. One particular thing is giving me trouble - the enemy units selecting the best target to approach.Take this situation, for example:http://img.photobucket.com/albums/v26/professorscissors/targetfind1.gifThe green square representing the moving unit, the red squares representing potential targets, and the gray squares representing walls. Now, a stupid AI would assume the target on the left was better, because it's two squares away, whereas the other target is three squares away. However, a decently intelligent AI would see it like this:http://img.photobucket.com/albums/v26/professorscissors/targetfind2.gifAnd see that when it comes to actualy path length, the target on the right is much closer.My problem is that I'm trying to find a way to do this *quickly.* My current method should work, but gets very slow in large maps with lots of beings. What it does is this:http://img.photobucket.com/albums/v26/professorscissors/targetfind3.gifThe yellow squares are the spaces it is looking at, because they are next to green squares. If it doesn't find any targets there, it marks the yellow squares as 'explored' squares, and iterates again:http://img.photobucket.com/albums/v26/professorscissors/targetfind4.gifStill no targets, so it iterates one more time:http://img.photobucket.com/albums/v26/professorscissors/targetfind5.gifAnd then it find the target on the right, and selects it. It wouldn't find the left target for another 3 iterations. If no new yellow squares are added in one iteration, it assumes no target and gives up.This works fairly well, but has the downside that it takes HUGE amounts of time in large, open areas. Can anyone here suggest a preferable method?Thanks in advance.   
  This article seems like what you are looking forhttp://www.gamedev.net/reference/articles/article2003.aspIt deals with A* and to make the search shorter it starts the search from both the "red squares" and the "green square"It also has some tips for speed boosting   ;  It looks like you're basically re-inventing A* (more or less), so that may be a good term to google for (try 'A pathfinding', 'A star pathfinding', or '"A*" pathfinding). It can be computationally intensive, but there are various things you can do (such as computing paths over the course of a few updates, or computing the path iteratively) that can improve performance. I'm not sure, but I think A* and its variants are commonly used in RTSs and other tile-based games, so it should perform adequately under the right circumstances.I don't have a lot of direct experience with A* though, so the above is partially guesswork. Also, there's an AI forum here on gdnet where subjects like this are often discussed; you might check there as well.[Edit: The AP's link looks like a good place to start.]   ;  ^same guys^on another note the title of your thread deals with an ideal target as you put it.if your ai unit is a zombie shouldnt it go for the most open and easily seen target (the one on the right) regardless of the distance?zombies are like people...lol...they go for what's shiniest not what's closest   ;  Actually, I am using A* for the pathfinding after it selects a target. But suppose there are 40 targets. Wouldn't it have to run the A* algorithm 40 times to find the closest one? If there are 40 humans and 40 zombies, that's about 1600 executions of A*, versus 40 executions of my algorithm. Is that really faster?   ;  Is the zombie supposed to know where you are even if it can't see you? If not, you can just do a visibility test on each enemy in turn, and the closest visible enemy (or the one closest and in its line of sight, or whatever) becomes the target.   ;  It being a pretty abstracted strategy game, effective gameplay challenge requires that the enemy, like you, always knows where you are.   ;  You could precalculate the shortest path from every tile to every other tile using something like the Floyd-Warshall algorithm before each level.   ;  I dunno, on a (for example) 20x20 map, there's 400 tiles... storing the shortest path from every tile to every other tile would mean storing over 150000(!) values - 399 distances per tile!   ;  Okay, scratch my previous response then! In that case I advise some sort of pre hoc (is that even a word? I mean either at load time or stored in the map file) merging of large open areas into 'megacells', and keeping track of which 'megacell' (maybe zone is a better word) each character is in. That should reduce the number of unnecessary checks you do.   