Optimizing A* pathfinding (not the A* project!)

Hey Folks,

I wrote a A* algorithm for my 2D jump’n’run (gravity affected).
Now I have a problem with chosing a good value for the estimated distance. If I choose the exact distance ignoring any objects blocking the path, I get the problem, that the script tries every node which is as near as possible on the y-level to the goal.
I tried to make a picture to show it. The red line is the path found (after a long time). The green path shows the direct path and the green lines going up shall show where the script searches a path (senseless).


So I’ve chosen to double the estimated distance. Now the script searches always the nearest possible node (like expected) but now I got this problem:


The script moves from closed door to the end of the red line. But you see it goes behind the ladder (it’s nearer to the goal) and then returns to the ladder, because the ladder is needed to reach the goal. But this isn’t the fastest path anymore and it also looks strange if enemies move like that.

I hope anyone can help me with this…

You don’t have to post your code. The solution is simple because you broke one of the fundamental rules for A*:

Like you can read on the A* article on wikipedia the heuristic must be admissible. That means it must not overestimate the distance.

So revert your heuristic to the previous normal distance or your A* will never find the shortest path.

What you can do is to modify (increment) the individual cost of certain nodes to offer a more attractive route.

The algorithm doesn’t search “senseless” because it doesn’t “sense” at all. It doesn’t know that the current path will be a dead end until it reaches the end. That’s how it works.