CODEWITHSUNDEEP
javaalgorithmsearch
user2787386
user2787386

Reputation: 303

Identifying cheapest path with A* algorithm

So I am writing a Java program that uses the A* search algorithm. The program runs on a 2 dimensional array. It has a start location, a goal and obstacles to move around. Every object on the grid is a node.

SRRRRRRR
RXXRRXXX
RRRXXXRX
RXRRXRRR
XXXRRXRR
RRRRRRRR
XXRXRRXR
XXXXRRRG

S = Start, G = Goal, R = Valid movement tile, X = Illegal movement tile

I have two arraylists: - openList - closedList

openList is a list of possible movements sorted from cheapest to most expensive. closedList is a list of nodes that have been visited and will not be visited again. The algorithm will always move into the first node in the openList. This node will then be removed from openList and added to the end of closedList.

My algorithm can successfully navigate from start to goal. The problem that I am having is that I am not sure how to filter out the true path from my list of closed nodes. A* will always look for the cheapest option which means that it may not go directly to the goal. The openList ranks nodes according to the cost of movement so even if the algorithm is sitting one Node away from the goal, if there is a node that is cheaper to move into somewhere earlier on the path then it will take that cheaper node. This means that I am guaranteed to find the cheapest path, but also that at the end my closed list will be full of nodes that are not on the best path to the goal.

At the end my closedList gives me the exact path my algorithm took, not the cheapest path.

My question is: Of all the nodes that my algorithm will explore, how do I differentiate between nodes that are on the cheapest path and nodes that are not?

Upvotes: 1

Views: 513

Answers (2)

user180247
user180247

Reputation:

It sounds like your cost function may be broken.

In A*, the cost function is always the sum of the actual cost of the path traversed so far plus a lower bound on the distance remaining. There are rules for admissability of the heuristic - the same as for a metric space IIRC.

Obvious heuristics to use for the lower-bound remaining distance in this case are...

  1. Euclidean distance remaining - sqrt (xdist^2 + ydist^2).
  2. Manhattan distance remaining - xdist + ydist

If the total cost estimate after taking a step along the indirect path isn't greater than after stepping directly to the goal, the only way that can be valid is if the total cost estimate is the same either way. A* won't avoid taking extra steps unless you add a tie-breaker to your cost-comparing tests. But it won't choose a higher-cost route when a direct route is available - unless your cost function is deceiving it (or your code has bugs).

In any case, that same-cost-either-way should never happen in a square grid if a possible move is directly to the goal.

There's a chance you may have implemented Dijkstra rather than A*. The cost function for Dijstra is simply the total distance travelled so far. There's no attempt to estimate distance remaining and therefore nothing to guide the search towards the goal - it explores in all directions equally.

One way to accidentally end up with Dijkstra is to use the obvious "uninformed" (but admissable) lower bound on the remaining distance - zero.

At the end it's still, of course, likely that you will have searched nodes that are off the optimum path - usually fewer than if you've got a good A* heuristic but even that can be wrong for awkward maps. See moveaway00s answer - "you need to in some way store the node you came from when you visit a node". For each node you explore, there's only one possible shortest-possible-distance to get there - if the node is on the shortest path, that backward step is a reverse step along the shortest path.

For Dijkstra, the first time you explore a location is always for the shortest way to get there. For A* that's not necessarily true IIRC (it's true for the goal node, not necessarily for other nodes explored), so you may need to store the shortest distance to the node along with the backward step.

Upvotes: 0

moveaway00
moveaway00

Reputation: 917

I would highly, HIGHLY recommend Amit Patel's A* pages, which will go into very good detail about everything you may want to know about Pathfinding.

To solve your specific problem, you need to in some way store the node you came from when you visit a node, so when you reach the goal, you just walk your way backwards along the path. This can be done with a Map<Node, Node>, or, you can make use of references to the parent node by storing something other than a Node: Something that contains the node, and a reference to the node from which you came to visit that node when you add to your lists.

Upvotes: 1

Related Questions