AStar problem

You could do a bi-directional search. *shrug*

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

or you could cache it ( ok, 5 minutes are 5 minutes, but then you won''t do that again ), you could preprocess the navigation map with some other algorithm like floyd warshall for example to see where are possible ways. ( would take really long when one nonexisting path takes 5 min )
Last but not least, you should think about some cancel criteria for your pathfinder an/or thinking about hirachial pathfinding.

@$3.1415rin

I guess you could generate some kind of 2D byte array, where each element corresponds to a map cell. Then you''d calculate during loading time which landmass each cell was. If during play time the source and targets points of a pathsearch were of different landmasses, you wouldn''t even bother to perform the A* calculation.

Unwise owl: Yes, I think I will do something like that. But the problem remains if the destination point is on the same landmass but but surroounded by trees.

I think heirarchial pathfinding mimght be a good way to fix your problem. You first find a course path and then find the path from each large grid area to the next one on the course path. You can limit the search depth to something like twice the number of waypoints in a diagonal in the course grid. It should be a lot faster than a full search (since the course grid has only a fraction of the nodes, and then each search after that{from course node to course node} only needs to search a few nodes each).

Extrarius: Sound intresting. Where can I read more about this?

Really, I don''t have any idea. I don''t remeber any papeers, tutorials, sites, etc on it. I''ve seen it mentioned all over the place but I haven''t seen any detailed information about it and I looked around because I haven''t had a need for it yet.

How large is your map? I''d check your implementation because unless your map is huge, five minutes is a really long time, even to search the entire map.

tj963

Only 256x256 squares...

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.