A usual solution to the problem is to time-splice the pathfinding.

In developing my a* pathfinder for a 3d rts game, we time-spliced the loop. So essentially, if you consider the main loop, (i.e. the one where you check all adjacent nodes to the current node), and at the end of the section, before you loop back check to see if the function has exceeded the pre-allocated time allowance, if so, then save the path so-far, and drop out.

The algorithm should never lock-up on any individual path request.

Additionally, you may want to consider accounting for these kinds of issues in the level editing process. I would suggest maybe using ''regions'' as a higher level pathfinding domain. i.e. if the goal and start are in two separate regions then don''t bother trying to find a path. What I''m talking about here, is maybe where you have two islands, separated by water (which is impassible), then each island is a region. consequently each tile on the map is assigned to only one region. In the case where entities can pass between regions, you need some handling in the higher level pathfinder, e.g. path to the waters edge in the first region, board a boat, path to the shoreline on the second island, exit the boat, then path to the destination. Or if you had an enclosed room, with a locked door, that room would be a separate region, and would be unreachable by the low level pathfinder, but the high level pathfinder should say:
-path to the door (in current region, so this is ok),
-unlock the door, and open it.
-make all tiles within region2, into region1 (as there is now a legitimate entry point between the two regions, so they should become a single region.
-path to the destination.

hope this makes sense, and by the way, if your map is 100x100 tiles, the pathfinder shouldn''t hold the pc up for longer than say 5 or 10 seconds, it sounds like you may not have set up the exit conditions on the pathfinding algorithm correctly, or the algorithm is *extremely* slow. I had my algorithm path across a 255x255 map with obstacles in about 8mS. And that was with minimal optimisation.

cheers

Matt

Just as a footnote, it might be useful to do some preprocessing of the map to determine if there are any permanently unreachable areas so they can be instantly discounted. But I agree with the previous poster that a 100x100 map shouldn''t take that long to exhaustively search. My gut feeling is that your open and closed list checking is slow because they run in linear time, searching through lists. To change this to constant time, consider a simple data-structure like this:

bool isInClosed[MAP_X * MAP_Y]; 

To add a node/tile to the closed list, you just do:

isInClosed[y * MAP_X + x] = true; 

and the next function changes like so:

bool AStar::IsInCLOSED(NODE n){    return isInClosed[n.y * MAP_X + n.x];} 

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

Yes I've been toying with some other A* applications, and they go very quickly with way more complex maps. It is obviously something in my implementation. I looked at some that show you what nodes they checked, and usually they check far less nodes than I do..



As you can see my routine is checking a huge area. This is not normal, correct? From other pictures I've seen it is behaving more like Dijkstrata's(sp) path finding. I'm calculating node cost by adding the parent node's cost to what the manhatten formula returns. Is this not correct?

To "solve" the inaccessible area problem I am doing something like what iron suggested. I have a counter and if the number of loops gets above X it comes out of the routine. After I conquer the speed problem I will work on a better solution.


edit: Hm.. Instead of adding all four directions to the open list if they're valid tiles should I just be adding the direction with the lowest cost?

[edited by - ddh on January 13, 2004 3:43:40 AM]

well it looks like your heuristic is way overestimating the cost to the goal. Try playing with the heuristic calculation to reduce its value.

quote:

---

I looked at some that show you what nodes they checked, and usually they check far less nodes than I do

---

ya, if you read up on how to optimize A* there are only really 2 main ways, better heuristic and less nodes. Reducing the number of nodes will help a lot.

Then again, with a 100x100 map it shouldnt take too long unless you click on a point you cant get to.

Looking at ddhs code again it seems that his GetBestNode looks at node.f which seems to be the remaining cost estimate rather than the estimate+the current traveled length.

The strange thing about this is that it should lead to a more directed (but suboptimal since he is in a sense way overestimating the remaining distance) path while his picture indicates that the search is to unfocused.

My code is slightly altered from the version I posted. Now f contains the parents f + estimated remaining distance.

edit:

But you are correct. If I remove the part where it adds in the given cost, then I get extremely refined paths, but they aren't smart and they also only branch when looking inside of things.

Sxxxx.....................x.+-----+.............x.|xxxoo|.............x.|xoxoo|...F.........x.|xoxoo|...x.........x.+x.x--+...x.........xxxx.xxxxxxxx...........................S = Start, F = Finishx = path, o = searched tile. = unsearched tile 

[edited by - ddh on January 13, 2004 8:15:33 AM]

quote:

---

Original post by ddh
edit: Hm.. Instead of adding all four directions to the open list if they''re valid tiles should I just be adding the direction with the lowest cost?

---

Random guess: you need to add more than the current best, in case the current best ends up being a dead end. However I don''t think you need to add the tile you just came from, since it should already be in the open list, just the other 3.

Yes, sorry. The tile I came from is not added as it is in a list already. At the bottom of the GenerateSucc function there is a check to make sure it isn''t in a list yet.

You need to add all possible successors, not just the best one.

I am not sure what your code looks like now as you said it is modified. But yes, using the correct calculation for f will help. Usually it should be the parent''s g (not f!), plus the estimated remainder, plus the code of reaching this node (an extra 1 point in your case).

Personally I don''t like using the f/g/h terms as they''re not very clear. Each node''s estimated cost (f, I believe) should be equal to the known cost to get there (g) plus the estimated cost to reach the end (h). Your current algorithm incurs no cost for moving from tile to tile, as you just carry forward a score from the parent, yet adds in the estimate multiple times for each step, as the score you''re carrying forward is the estimate instead of the cost.

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

"Usually it should be the parent''s g (not f!), plus the estimated remainder, plus the code of reaching this node (an extra 1 point in your case)."

Okay that could be the problem then. I''m adding the parents f value. I will rewrite my code to store G values, and give it a wirl then. Is the +1 really necessary if all moves cost the same? I didn''t think it would be since it was a constant value.

I would like to thank everyone for being so helpful. I really didn''t expect that.