Jump to content
  • Advertisement
Sign in to follow this  
Oliverr

A Star Pathfinding

This topic is 2589 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 :

qqz48y.jpg


nwcvtt.jpg


and here is the problem :
29ei4co.jpg


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 )

Share this post


Link to post
Share on other sites
Advertisement
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!

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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 :/

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!