Hi,

i am some what finishing on my implementation of A Star, tho i have some issues with some principles i believe. It works well with regural obstacles, but once there is concave obstacle it sometimes gives error, but always fills in the the space in the concave obstacle then moves to the goal. So its of course far from best path.

Here are few pics from working pathfinding :







and here is the problem :



i am not sure how to handle this problem. What i came to undersand is that i should probably compare for each node that is in closed list ( the final path nodes ) the path to that node from start. And if the g distance is smaller i should replace the path to this node with the new path. Tho i am not sure if thats what would help. Also when i was trying something like this it made the script too expensive as of course the path is computed for each node, instead just for one goal.
I was thinking if there was some easier solution for this, maybe based on f distance.

Thanks for any kind of help or suggestions. ( btw i am using javascript and Unity )

You sure you aren't over-estimating your heuristic?

I believe not, i am using standard heuristics for diagonal grid, so it shouldnt be problem. Anyway if you know about some issue concerning heuristicsk, please let me know.

Sure you should check any neighbouring nodes from the closed list to see if your current path is shorter - that should solve that 'pooling' problem in image 3.
If your maps are all as simple as this you may find that fuzzy navigation is good enough and much cheaper!

It would be great, if i could somehow just create shortest path from the nodes in closed list, tho i am not sure how to check which path is shortest in this pooling scenario. I would realy like to avoid computing new path for each node. It will be used in quite big maps and if theres 500 nodes long path, it would mean to run check on 500 nodes, so it would be 500 times more expensive than its now :/