Hello, I've got a question on pre-action while my path finder locates the valid path. For the underlying systems, I've got Navigation mesh and my pathfinder does A* search on it. But since my map is rather large and there are a lot of nodes in navimesh, I need some sort of a pre-action while my pathfinder finishes it's task. By pre-action I mean something for my PC(playable character) to do or follow until the completed path is returned by the pathfinder. (I prefer something to follow cuz thats how most games work, right?) For now, I get some sort of a partial path by searching the first 50(var) nodes and if the complete path is not ready, simply follow that partial path(A* speaking, form path from the popped node after 50 node search). And of course, I restart my pathfinder from the end of that partial path to the original destination point while PC follows the above partial path. but this as u may know already, has problems. Simply put.. it doesn't provide a smart looking path due to the partial path being very uncertain. (It may cause my path to backtrack a long way.) Any suggestion on the pre-action part?? I'm not even sure if u'd understand what I mean by pre-action but that's the best I can put it. (If u don't get my question plz let me know.) Any help or suggestion would be great! thanks in advance. [Edited by - myClaim on April 24, 2008 5:33:23 AM]

Let me make sure I am understanding you properly:
You have the A* algorithm running, but it takes a good deal of time because of the quantity of path nodes, and you want to figure out something to appear on screen during processing, or optimize the algorithm. Right?

If so, the main way to speed up a search algorithm is to decrease the amount of data.

One thing you could do is make a larger "quick grid"
Basically, each larger grid contains several (say...10x10) normal grid tiles and it knows whether or not there is an entrance/exit out of each of the sides.

Run the A* algorithm on these big tiles first, storing ALL paths, not just the best.

Then when you run it for the player on the small tiles, make sure all tiles that were not included in the large-scale data are ignored.

This should eliminate the completely erroneous paths.

I thought he was saying that having to repath from a position along the initial estimated path sometimes looks bad. The original post wasn't all that clear though.

Ideally, if you have a hierarchical pathfinder you'd be able to both reduce your search times and prevent having to wait, or at least get an accurate direction to head towards.

The process of playing a locomotion animation while waiting is tricky, and rarely used in games for the reasons you describe. Idle or looking around is probably the best you can do.


Now you understand why developers put in a lot of effort to optimize their pathfinders to avoid such problems!

Hehe first of all Thanks for replying back!

I was worried that my question may be a little misleading but it seems that you all gave me some ideas on what I should do.

Yet again, my apologies for lack of clarity.

to FortisVenaliter:

you got my point clearly and your suggestion sounds great. I better start on that asap!!

to Kylotan :

Right. I do have this repath btw my quick path destination and original destination.

1) search 50 nodes.
2) if(fullpath not ready)
3) use the popped node after 1) and produce a quick path to follow.
(By linking parents)
4) move my PC along quick path.
5) while PC is moving, locate path from quick path dest to original dest.
6) when PC is thru w/ quick path follow path made from 5).

This is what I meant lol.

But the repathing was a result of my pre-action scheme so it won't be a problem if I drop it.

// to alexjc

Hierarchical, yeah that seems to be my word. I thought I was done w/ path finding but I was wrong.

I've never done some serious optimizing task so this is really a new challenge for me.

//

Thank you all again for your replies!!

Oh, one extra thing to ask.

I've read something like giving extra weight or cost to clicking on regions where fog of war is still on.
(Having to path find to that unrevealed region)

Is this normal? I mean is it common in games? I'm not sure cuz I failed to get back to whichever source I read it from.

I remember reading something like pathfinder will be too smart if they know the whole map prior to exploring it.

Any reference or idea will help a million!

[Edited by - myClaim on April 25, 2008 1:59:04 AM]

In real life rarely do people pick the perfect path immediately -- especially when the solution isnt immediately visible. If the path is complex few people will come up with an optimal solution instantly.

You could have the NPC move at half speed and with a 'searching' animation -- to minimize any backtracking (and backtracking is a perfectly proper behavior for real world objects...)

If you are in a maze, expect alot of 'thinking time' and hesitation and reverals as the real path is 'felt out' and discovered.


Pre-digest map with hierarchical levels of mapping to lower the time to find the 'correct' path and then do the local fine pathfinding between the coarse level waypoints.

If the object took a path to get somewhere, it can be saved to reverse and go back to the original location (being a proven path).

to wodinoneeye:

Thank you for your opinion.

I was use to playing well made games that I figured it would all have some clear cut solutions.

I will consider things that you've pointed out and hopefully get a better result.