Sign in to follow this  
CadetUmfer

Search My Graph! (Pathfinding with No Destination)

Recommended Posts

CadetUmfer    234
I have a potential field that updates periodically. It generates a short path to follow between (expensive) field/path updates. To generate the path, I'm just using a greedy best-first search that gives up when it hits the max path length (tick rate / path update rate) or a local maxima. Is there a smarter algorithm I should try? (eg one that keeps in mind the total potential of the path, instead of just the best neighbor?) My graph theory education ends at Dijkstra. EDIT: I should explain this better. The potential field is queried at certain points (places Entity can move to this tick). It searches all those places, adds the best one onto the path, searches again from there, etc. It doesn't know where it's pathing TO, it's just looking for the best available within x steps. I'm hoping to avoid most pathfinding issues by changing the potential field, rather than making the pathfinding more complicated. If you're stuck in a local maxima, for example, the field will change to get you out of it. I may not need a more advanced pathfinding solution, I'm just inquiring. [Edited by - CadetUmfer on April 28, 2010 9:54:27 AM]

Share this post


Link to post
Share on other sites
alexjc    457
The main benefit of potential fields is that you can just follow them reactively and not have to generate the whole path. For situations like horse shoes that you mentioned, you can get around that by grouping your obstacles into convex obstacles (circle is probably best) and applying a force around those. Are you sure what you're doing is necessary?

If you'd like to search over that map, and treat it as an influence map instead, then A* is still the most optimal way you can find a solution -- but because there are variable costs at each 2D point, it's going to be slow.

Did I miss anything?

Share this post


Link to post
Share on other sites
Sneftel    1788
Take a look at this paper. LPA* is a lot more efficient than planning from scratch every time your edge costs change, and a lot more effective than getting into local minima and then trying to climb out of them.

Share this post


Link to post
Share on other sites
CadetUmfer    234
Quote:
Original post by alexjc
The main benefit of potential fields is that you can just follow them reactively and not have to generate the whole path.


I'm just trying to plan ahead a little bit, so that I can find the performance sweet spot. By adding a little bit of planning, I'm hoping to be able to slow down my potential fields.

For example, right now my potential fields update every 0.5 seconds, my physics every 0.05. So the PF generates a path of up to 10 steps describing how to move. This seems much quicker than trying to keep the PF up to date and just reacting (moving to best neighbor).

LPA* looks interesting. Not sure if I can use it in this case, since I have no idea which edge costs changed until I check them (the PF is lazy).

Share this post


Link to post
Share on other sites
alexjc    457
OK, I see.

I'd just use brute force local A* on a regular basis with a maximum search iteration set at a value that you pick based on performance. [EDIT] Your A* wouldn't have the usual heuristic since you don't have a goal, but the rest would be the same.

Share this post


Link to post
Share on other sites
Sneftel    1788
Quote:
Original post by CadetUmfer
LPA* looks interesting. Not sure if I can use it in this case, since I have no idea which edge costs changed until I check them (the PF is lazy).

In that case you'll be interested in D* Lite, a variant of LPA* that does not require full prior knowledge of the state space or of changes to the edge costs.

Share this post


Link to post
Share on other sites
alexjc    457
Quote:
Original post by Sneftel
In that case you'll be interested in D* Lite, a variant of LPA* that does not require full prior knowledge of the state space or of changes to the edge costs.


The thing about either of these algorithms is that they're not as trivial to implement, and much harder to justify. Do you think it's worth it in this case?

Share this post


Link to post
Share on other sites
Sneftel    1788
That depends on his level of ability, and how pressing his computational needs are. These algorithms are simple to implement. full pseudocode is given, and no exotic data structures are used. I'm not sure what's involved in "justifying" an algorithm.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this