Hi, if i have some rectangular region defined or just one tile in grid-based system, how could i find path to that region(region or tile is impassable)?

Same as usual, mostly. Start at your start node; maintain OPEN and CLOSED lists as usual; just stop when you reach a node adjacent to this place you want to get to. Only one change: You may need to alter (or eliminate) your heuristic (as it may no longer be admissable), in which case your A* will reduce to Dijkstra's algorithm.

Though actually, an admissible heuristic should be possible. One such heuristic would be to bound the region by a circle, and then compute the Euclidean distance to the edge of the circle (just the distance to its center, minus a constant). This would be admissible, since it would never overestimate.

Oh, you have a RECTANGULAR goal region? And a 4-connected grid? Then computing the Manhattan distance to the closest point on the perimeter of the goal region should be possible (and superior to what I mentioned about the Euclidean distance.)

Quote: Original post by Semeii
Hi, if i have some rectangular region defined or just one tile in grid-based system, how could i find path to that region(region or tile is impassable)?

An easier algorithm to implement, which might potentially serve your purposes well, is a simple breadth-first search on the grid. This is usually called a flood-fill pathfinder, the wavefront pathfinding algorithm, or Lee's algorithm (all names for the same thing).

You can find links to this algorithm, along with a description of how to implement it in a more memory-efficient manner in my blog post on memory-efficient pathfinding.

Thanks for answers, I will go with finding full path, then removing nodes that are inside region, i think that would be work nice and will be fast to compute.

just(if my nodes are stored in list - nodes at end first):

//Find first node that is in not in region and remove all nodes form that pointfor (int i = 0; i < nodes.Count; i += 1){    if (!InsideRectRegion(nodes))    {        //Then remove nodes from 0 - that would be last node in path        // to first node found in region        nodes.RemoveRange(0, i);        break;    }}

Note that it wold be faster (a lot? - nodes would be removed from end not start of list...) if i stored my nodes in logical order, first path node first, but this is how the A* works - could anyone give a hint how to traverse A* nodes so i could end up with logical order of path nodes? I could just reverse whole list at the end, but maybe there is another way?

Quote: Original post by Semeii
Thanks for answers, I will go with finding full path, then removing nodes that are inside region, i think that would be work nice and will be fast to compute.

No problem. But, I'm a tiny concerned by your answer: Do you mean that you'll pick some arbitrary point inside your rectangle, pathfind to that, and then remove all the nodes in the rectangle as a post-processing step? If so, you should know that this will not generally be optimal (nor will it be faster!).

Here's an example to show that this is not generally optimal (ASCII art, below). The 'X's represent the goal rectangle, and 'S' represents your starting position. Now let's say you pathfind from S to some point '*' inside the rectangle. One optimal path (for a 4-connected grid with Manhattan distance) is given by the '.' characters. So if you run A*, and truncate your path, you'll end up at B. However, the shortest path to the closest point on the rectangle is given by the '|' characters, and ends at A. You can see that it's much shorter.

  XXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXX  XXXXXXX*XXXXXXXXX  XXXXXXX.XXXXXXXXX  XXXXXXX.XXXXXXXXX  A      B  |      .  |      .  S.......

However, doing this the right way requires only two very simple modifications tothe A* algorithm:
1. Stop expanding nodes when you reach ANY 'X', not just the '*'
2. Either set your heuristic function equal to zero, or choose another admissible heuristic.

Of course, if I've misinterpreted what you intend to do, my apologies.

Cheers!

Thanks, I see, but turning off heuristic is not-for-me as it jumps form path find time form 0.4msec to 2.4 and that is not cool. 6(!) times slower. no no no :D Also im using diagonals to, and rectangle regions will be like 1x1 2x2, ... max of 5x5 maybe.

Quote: Original post by Semeii
Thanks, I see, but turning off heuristic is not-for-me as it jumps form path find time form 0.4msec to 2.4 and that is not cool. 6(!) times slower. no no no :D Also im using diagonals to, and rectangle regions will be like 1x1 2x2, ... max of 5x5 maybe.

Ah, I see what you mean; the rectangles are small enough that what you're doing isn't a bad approximation at all!

But if you do decide that you want the real optimal paths, you should be able to get full speed if you just work out the appropriate heuristic for the rectangle/square case. The best heuristic would be the shortest distance on the unobstructed plane from a point to the rectangle, which is something you can probably work out by geometry (but I don't know off the top of my head.) And there are a number of slightly more conservative heuristics you could use (like the euclidean-distance-to-bounding-circle one) which are very easy and would probably be plenty fast. [But again, the difference in length between the true optimal path and what you're getting as-is probably isn't more than a few tiles, so I can also see why you might not bother!]