You might want to post your A* performance figures (say for distances of 1, 10, 30, 50, 100) because that does sound overly long?

I only let mine expand a maximum of say 500 nodes or return that it can't get there. You'll probably want to use something more like 1500-2000 but probably not more than that.

That should still only take milliseconds (guessing).

[edited by - Talyssan on March 30, 2003 6:28:29 PM]

If you''re using a tile based map, check out the Distance Transform Algorithm. Since it starts at the goal node it is guaranteed to identify an inaccessible goal in a finite search space.

Cheers,

Timkin

Gandalf, you should be able to search a 256x256 space in well under a second. I would suggest profiling your algorithm and optimising it a bit, as I doubt you will need to use a totally different algorithm in your situation.

Expanding on what Unwise Owl said, one idea would be to use a simple depth-first flood-fill algorithm to determine reachable squares at the start of the game. For each square, recursively flood-fill that and any adjacent squares with a unique region number if it hasn''t already got one assigned. Then before you calculate any paths, check the region numbers for the start and the destination; if they differ, you can''t get there. (This doesn''t take into account changing terrain, but you can work around that.)

Timkin, where can we find information on the distance transform algorithm? Neither Google or Citeseer seem to return much of any worth...

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

I think I have find a solution to the problem now... If the search takes to long time, I stop and search again but this time
from end to start end then reverse the path.

[edited by - Gandalf on March 31, 2003 1:54:00 PM]

Jarvis, R. A. "Collision-free trajectory planning using the distance transforms", Mechanical Engineering Transactions of the Institute of Engineers. No. 3, 1985.

You might also want to look at a 3-D version of the algorithm:

Williams, M. and Jones, D. I., "A Rapid Method for Planning Path in Three Dimensions for a Small Aerial Robot", Robotica, v19, 2001. pp125-135.

I also posted the basic algorithm last year to this forum... here it is.

Timkin

Gandalf: What are you using to implement the open and closed list? That may be your problem.

Also, are you searching the closed list before each insertion into the open list? Are you sorting the open list after each insertion?
Both could be greatly slowing down your program, and both are pretty much uneeded if you can impose certain limitations on your search (such as only doing 1 search at a time).

[edited by - Extrarius on April 1, 2003 2:19:35 AM]

I use a heap to sort the nodes in the open open list. The open and closed list are vectors. I use no lists.

defining landmasses is the best way to go in this situation, im quite sure.

landmasses is not the right term though, cos it led you to believe it would cause trouble with trees enclosing an area. a better term for this would be just areas: each part of the map only reachable by itself.
to construct these area''s, add a member to your tile struct char area, and do a floodfill witch will fill all walkable tiles with a unique index. then keep searching the map for a spot thats not yet indexed by a floodfill and start a new floodfill from there, until youve covered all of the map.
then you can just check if the target and start have the same area index, and only if they do perform an a* search.

5 min is not really healthy tho. even if your whole map were to be put on the open list, such a time still isnt justified. probably theres a bug somewhere..

quote: Original post by Timkin
Jarvis, R. A. "Collision-free trajectory planning using the distance transforms", Mechanical Engineering Transactions of the Institute of Engineers. No. 3, 1985.

You might also want to look at a 3-D version of the algorithm:

Williams, M. and Jones, D. I., "A Rapid Method for Planning Path in Three Dimensions for a Small Aerial Robot", Robotica, v19, 2001. pp125-135.

I also posted the basic algorithm last year to this forum... here it is.

Timkin

Thanks Timkin!

Do you know if anyone has actually implemented the DTA for pathfinding in a computer game?

Have you (or any one you know of) ran testbed comparisons of the DTA vs A* for the same map, same path?

Thanks,

Eric

quote: Original post by Gandalf
I use a heap to sort the nodes in the open open list. The open and closed list are vectors. I use no lists.

Well, you could get rid of the closed list by putting a boolean in each node like "already_visited" which you set to true when it would be put into the closed list. That way, instead of searching th closed list for a node you just test a boolean property. The only problem with that is that you can only run one search at a time.