Using A* path finding is giving me inaccurate results

Question

So I am using A* pathfinding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of the must-pass nodes, to make sure they always go to each of these. My method for deciding which order nodes come in for their individual run through the algorithm is to use a distance between the person on the graph and the remaining nodes, the smallest distance will be put through the algorithm first.

Here is a diagram of what this looks like:

The person must visit the blue node last, which is why the distance hasn't been included for that node.

As you can see, the bottom right pink node is the first node to go through the algorithm since they have the smallest distance.

Here is where I come across a problem:

If the algorithm tries to find a path to this node on the bottom right, the person will actually travel across the edge with weight 1, since the distance between the node on the other side of the edge with the weight of 1, to the end node, is 6.25 (using a ruler by hand and making sure the diagram stays the same size on my screen at all times for all distances measured).

Would this not mean the person ends up traveling through all of the other must pass nodes on the graph before they even reach the first must pass node?

Are my criteria for picking the next node for the algorithm wrong?

What am I doing here that is wrong? Or is this a fault with A*?

Note: The weights on each edge are measured fairly accurately by hand with a ruler, so I doubt that is the issue.

EDIT:

The one question I need to be answered is this. What is the best way to decide which node to path find for first? I'm starting to doubt if Euclidean distance is the best choice here.

Answer 1

Let's start this off with a quick review of A*. A* is a pathfinding algorithm that builds on some of the benefits that greedy searches and dijkstra searches have. Make sure that your implementation correctly combines both basic heuristics A* uses:

1. g(N) = the cost to get from the starting node to the next node N
2. h(N) = the estimated cost to get to the goal from N

By expanding the nodes with the lowest g(N) + h(N) first, A* quickly converges on the most efficient path when some costs are unknown. It's great for any graph search and I've used it to implement backtrackers for constraint solving.

---

Now, our review's over. Let's get to your problem!

You're trying to have a character visit certain subgoal nodes on the graph and finish on the goal node. This is actually a variant of the famous "Travelling Salesperson Problem". It is an example of an NP-complete problem, which means that even A* isn't going to help you solve it quickly; you'll be doing a lot of backtracking or trial-by-error no matter what algorithm you use.

In order to adapt A* to this problem, you will need to rewrite the logic for exiting the search. Instead of checking if N_i == Blue_1, you need to check if {Blue_1, Pink_1, Pink_2, Pink_3} is a subset of the path.

Right now your calculation for h(N) is based on Euclidean distance from Blue. Not a bad start, but it's not as efficient as simply setting h(N) = 0 on this problem; dijkstra search is better than a too-greedy A*. Because you aren't actually aiming for the blue node, you have an 'inadmissable' h(N) so you'll miss the optimal path sometimes:

"If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal."

You can get an admissible heuristic by setting h(N) = the distance to the nearest sub-goal. Once all sub-goals are reached, set h(N) = the distance from the blue goal. This means that each node in the pathfinder needs additional metadata. Add a field to pathfinding nodes that tracks which goals have already been hit.