   A* Chunky Search Problem
  Here is the situation. I have a randomly generated tile map with some areas of it *potentialy* being unreachable. There are for simplicity two types of tiles: open and blocked. I want to speed up my current pathfinder by using a preliminary "chunky search" in say 3x3 or 5x5 "super nodes" instead of searching each individual tile. Now lets say i have a map like this:***********  S**   **   **   *******   **    *   **    *   **F   *   ***********  Where F and S are Start and Finish. With a regular tile search, the A* algorithm will seach every tile frantically trying to reach the Finish. It will eventually realize it cannot move to the goal however.With a chunky search, the pathfinder has the chance of "jumping the wall" in the middle and *believing* it can make it to the Finish, but when it actually does the supernode-to-supernode connections, it will realize it cannot. At that point, it seems to me that i have effectively wasted a step (by doing the chunky search at all). Does this method of speeding up the algorithm only work if your map is mostly open terrain? My map may be mostly closed with networks of "tunnels", and there is no way to know about the map beforehand since it is randomly generated, so placing hidden AI hints into it is not a possibility.Is the chunky search precalculation method for me? 
  What I plan on doing for 'my RTS' will work that out nicely.When creating 'supernodes', make them arbitrary sizes rather than on a grid each representing the same number of 'subnodes'. I'm going to do it by rectangles, so the Supernodes would be shown by the following diagram:***********11111111**11111111**11111111**11111111*******222**3333*222**3333*222**3333*222***********   Remeber that A* has no concept of space, size, shape, etc. All it knows about are nodes and links between them. You could thus expand the algorithm to combine 1 and 2 into a single supernode. The reason I'm probably not going to do that is because it is probably faster to create the rectangles, and I'm going to recreate the supernodes each time a relatively permanent, stationary path-blocker (a structure) is placed. It also makes it easier to estimate the cost from supernode to supernode, since you can just use the center of each as a rough representation (though it might over-estimate that way, I think it will still work satisfactorily).   [edited by - extrarius on February 3, 2004 1:03:10 PM];  Remeber this fact and you should be able to work out a solution to your problem...A* is an optimally efficient search algorithm for finding the lowest cost path through a graph  . If you have regions in your maps that are not connected to each other, then they aren''t part of the same graph, since a graph is defined as a set of connected nodes. Thus, you obviously cannot apply A* directly to this problem unless   you know that the start and finish lie in the same graph.Clearly, you need to determine if your start and finish lie in independent graphs and if they do, you don''t need to search, since their is no path between the start and finish. How you do this is up to you, although I would perform a bidirectional connectivity check by building, for both the start and goal nodes, the largest super-node that contains each and then check if these super-nodes overlap.Cheers,Timkin ;  Good idea on pre-defined rectangles. On a randomly generated map, it''s more difficult, but somewhat doable.Now with my game, it''s a TBS game, so raw speed is not an issue. In the game however, there are units that can lay down blocked tiles as barricades, thus altering the landscape and pathfinding, potentially "splitting the graph" into two. When i create a path, i usually check from one unit to another (set intercept) or to a tile (set destination). I do not know at the time if there even *is* a path from A to B (may be blocked permanently, temporarily, or another unit is in the way blocking what *would* be a good path). The only way for me to know is if the algorithm exhausts it''s OPEN list and no more children can be made. I have also put a TIMEOUT number of tiles on it since it will foolishly attempt to search *every* tile on the map trying to get to the goal if there is no route.Is there a way to know if there is a path ahead of time without having to exhaust the algorithm (and wasting a lot of time doing so)? ;quote:Original post by leiavoia   Now with my game, it's a TBS game, so raw speed is not an issue. In the game however, there are units that can lay down blocked tiles as barricades, thus altering the landscape and pathfinding, potentially "splitting the graph" into two. You should most certainly look into D* (Dynamic A*), which will give you updated path costs as information about changes in the connectivity of the world is obtained (resulting in changed path costs).quote:Original post by leiavoia   Is there a way to know if there is a path ahead of time without having to exhaust the algorithm (and wasting a lot of time doing so)?   How big are your tile maps? A few hundred tiles, a few thousand maybe? A flood fill type algorithm, like the Distance Transform Algorithm, will tell you if a path exists or not. Since your domain is dynamic, you will face some problems in bookkeeping with this sort of algorithm.  I highly recommend you go and read a lot of Sven Koenig's work... its online... he's done a lot of research in this area and you should be able to find something there to help you.Cheers,Timkin   [edited by - Timkin on February 5, 2004 8:48:43 PM];  Spend the extra time upfront and create a walkablity set upon starting a new map. It''s just a recurisve flood fill until there are no more free tiles, to determine all the walkablity sets. Once you''ve identify the sets, give each node a set id. If start and end nodes dont have the same set id, they can''t be reached, unless they have a brdige set (see below)Handle the case of tiles becomeing walkable by checking the walking sets they touch and create a brdige connecton. When a blocking tile  comes into existence, check the touching walkablity sets, and repeat the flood fill to determine the walkablity sets.Good Luck.-ddn;quote:Original post by ddn3  Spend the extra time upfront and create a walkablity set upon starting a new map. It''s just a recurisve flood fill until there are no more free tiles, to determine all the walkablity sets.Sheesh, didn''t I just say that in my post??? ;  Sorry Timkin, from last i check, your post was just quotes of previous post. It must have been a message board error. This is the first time i seen your post corretly.-ddn 