koobas.hobune.stream
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...
post the code which does the path finding logic.
usually this could be fixed by giving more weight to horizontal and vertical nodes ins$$anonymous$$d of diagonal ones!
also check if the heuristic is calculated correctly!
It's about 125 lines of code and doesn't even say much without the node class, query class etc I think. Does anyone take the time to read study it? Anyway, I'll edit my question. It may be a problem with the closed list. What happens, when a new path is found with lower costs to reach a node. It's dropped, because the costs aren't checked in the closed list, I think..
In the node class you are deciding the neighbours i suppose, changing the order of it will change end results
Hmm the top node is already connected first (I also thought it could help)..
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.
So it is necessary, that the algorithm searches all those ways up before moving over a two tiles high block, even though the block is near the end?
Well I think I understood now. This is my a* at the moment: http://en.wikipedia.org/wiki/File:Weighted_A_star_with_eps_5.gif and thats the right one without doubled estimated costs: http://commons.wikimedia.org/wiki/File:Astar_progress_animation.gif
I thought, I could make the pathfinding faster, but it seems like it is supposed the way it worked.
Thank you! :)
Yes, i know that A* can be really heavy in some situations. I implemented a 3d-A* for a computercraft turtle (a $$anonymous$$ecraft mod) and due to the 3 degrees of freedom even on short pathes the openlist kind of explodes (5k-10k nodes :D). The most important thing is to use fast datastructures since A* does nothing but pushing / popping / looking up nodes all the time.
I don't see how you could speed up the search any further. The only thing which is unnecessary at the moment is storing path.TotalCost in the closed list. Is TotalCost a property or a field? if it's a field, it doesn't really matter. If it's a property which traverses the whole path it should be removed since it isn't used at all.
I'm not sure if you already calculate the path in a thread, but that might be the next thing you might consider. In most cases it doesn't metter if it takes 3-5 frames until the path is ready. The user probably won't notice that. Of course using threading brings a lot of additional problems.
I might be missing something, but couldn't the nodes store some kind of penalty based on line of sight in the x axis? You know, a node costs more if it can't see far to the right of itself...
