Having an issue implementing A* pathfinding
Hi, I am trying to add pathfinding into a game that I am creating and have tried to use the A* pathfinding algorithm. It kind of works as it does eventually find a route however it can take a very long time when nodes are far apart and when I look at it when it searches it looks like it goes over the same nodes over and over again and I'm not too sure why? My guess is that I am exploring nodes that are already in my closed list.
I have added the code as an attachment to this post.
14 Replies
@Coolbeans You are doing a pretty heavy operation here:
Sort (using LINQ) and then turning it into a list. If you used a priority queue, you wouldn't have to sort in the first place
You also seem to use lists where sets could perfectly be fine (and could be the cause of why you see duplicate processing)
That might mean some reworking as your
ExploreNeighbors seems to reconstruct the environment each callThank you!! Yeah I had some suspicions about the ExploreNeighbors.
You could also post your reworked code to #code-review , we can help you iteratively improve it if you still have perf problems after that
That would be great thank you!!
Haven't touched this code for a year or so and its been some trouble trying to understand what I was doing at the time XD
Hi I have started trying to use a priority queue and hash-set instead of lists for my open and closed sets and I was wondering how I should go about comparing newly explored nodes with nodes in the open list to see if they already exist? As I don't know of a way of iterating and looking through a priority queue?
@Coolbeans can you attach the new code? I’ll take a peek after work and see, I don’t think you should iterate the queue at all
Hi, sorry for the late response I have been busy with work. I will send the code now.
I definitely think I jumped into the deep end a little bit with this one and think I should probably do some simpler search algorithms first.
It looks like it always wants to go down and left?
Hey, I didn't wanna leave you hanging @Coolbeans . I'll try to check your code. For reference, I tried my hand at A* with the help of the wiki: https://gist.github.com/LPeter1997/27cd9504c1c86be39086e3bc44cde022
Won't claim this is world-class code, but it factors out the essentials of A*.
You can still improve it by replacing that set with a priority queue!
Hi, thank you for all the help you have given I really appreciate it. I will check it out and try and put it into my code!! 🙂