Jump to content
  • Advertisement
Sign in to follow this  
browny

A little confusion with A*

This topic is 5113 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Does A* algorithm support -ve edges ? Apparently the pseudocode seem to support -ve edges to me ( the way nodes are removed from the "closed" list and put back into the "open list" ). But i have a little confusion here. Suppose we have a situation as below
A-->B-----------
|   ^          |
|   |------|   |
-------->  C <-|

[ sorry for the poor text-art ] A has an edge towards B and C, and B has a edge towards C, while C has a edge back towards B. Now, for example, A was popped out first in the algorithm; hence, both B and C will be pushed into the "Open List." Now Let B has the minimum "G" value hence B will be popped out next. Suppose now the edge between C-B is negative or maybe the G value of B becomes smaller as u travel from C to B. If this is the case, then B will be removed from the "Closed" list and put back into "Open" list. So , sometime in the future we will again process the node B and WOULDN'T this create an infinite cycle ? [ Because this time the cost to reach C will be smaller than the previous case and C will be again pushed into the "Open List" ] Someone please clear me out

Share this post


Link to post
Share on other sites
Advertisement
What do you mean by "-ve edges"? If you mean edges with negative cost, I don't think A* supports them.

Share this post


Link to post
Share on other sites
A* supports negative-cost edges, but you'll need to pick your heuristic very carefully. Remember: you want a heuristic that NEVER overestimates the cost. If that heuristic fails to take into account the potential for a negative-cost edge, you will run into problems.

Share this post


Link to post
Share on other sites
DrEvil, a negative cost could represent some goodies that you can collect in some corridor. In the real world, some friends of mine bought a special train ticket that allowed them to travel through Europe for a month. Sometimes they took a train overnight that they didn't need to, so they could sleep in the train and not spend money in a hotel. That trip would have a negative cost.

Share this post


Link to post
Share on other sites
Ok, Sneftel, but what about the possibility of INFINITE CYCLE, apparently it seems that like there COULD be INFINITE CYCLES if heuristics are not set carefully or if there are negative edges.

However, if we dont have negative edges [ letz just assume we are careful enough with the heuristic thingy ] then why should we bother about "Closed List." We can simply follow the Dijkstras method, ie. "Once a a node is popped ( relaxed ) , it's never relaxed again." Hence we dont have to worry about taking a node from the "Closed" list and putting in back into the "Open" list. Wouldn't that cut down on space and time requirement for the algorithm?

Share this post


Link to post
Share on other sites
Quote:
Original post by browny
Ok, Sneftel, but what about the possibility of INFINITE CYCLE, apparently it seems that like there COULD be INFINITE CYCLES if heuristics are not set carefully or if there are negative edges.
Yep. In those cases, there is no finite shortest-path, so the algorithm has trouble. I don't know of any pathfinding algorithms that correctly handle this situation (and I suspect that detecting all such negative loops is NP-complete).

Share this post


Link to post
Share on other sites
Instead of using negative costs, add the absolute value of the minimum node cost to all nodes such that all costs are greater than or equal to zero. It might not have the exactly same effect, but it should act simmilarly and would make things much easier to process (no need to worry about infinite loops, and there is a finite 'best path' if there is one at all).

Share this post


Link to post
Share on other sites
If you want to take rewards into account when performing pathfinding, then one method is to define a value function over possible paths. There was a good thread earlier this year on this exact problem, wherein I explained the procedure and provided one such function for use with A*.

Here's the link

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!