MintyLyton

Learning Pathfinding

Recommended Posts

Hey so I'm new to learning AI pathfinding, specifically learning to implement A*. I wanted to make my own system instead of using arongranberg's version of A* (It's a lot to take in when I don't know how the implementation works). I'm using Unity right now and I was wondering if its better to use multi-threading to create my path-finding instead and how I would go about doing this?

Share this post


Link to post
Share on other sites

Since you're using Unity, have you considered using the one that is built in to the engine?  Sometimes there are reasons to re-implement functionality that is already present in the engine, but what you described probably isn't one.

As for multi-threading, no, it is unlikely to help because of the nature of the search. There is no known implementation allowing it to scale well in parallel.  If you need a parallel search, you'll probably want a Parallel Ripple Search or Parallel Fringe Search. 

If you are just looking for how A* works, there are plenty of tutorials, animations, and youtube videos describing it. If you've got specific implementation questions those could be asked in any of several sections of the site: here in AI, in For Beginners, or in General Programming. 

(The most straightforward implementation is a priority queue for the open list where the priority is the length of the path plus the estimated remaining distance to target. Take the first open list item, (the priority queue should automatically pull the lowest combined number), look at the neighbors, either find them in the closed list or add/update them on the open list priority queue, move the current node to the closed list, then repeat. When you hit your target, you're done.)

Share this post


Link to post
Share on other sites
18 hours ago, frob said:

As for multi-threading, no, it is unlikely to help because of the nature of the search. There is no known implementation allowing it to scale well in parallel.  If you need a parallel search, you'll probably want a Parallel Ripple Search or Parallel Fringe Search. 

Ill look into this pattern in my spare time. I was just curious to see if people implement it and under what conditions would need the search pattern. 

 

18 hours ago, frob said:

(The most straightforward implementation is a priority queue for the open list where the priority is the length of the path plus the estimated remaining distance to target. Take the first open list item, (the priority queue should automatically pull the lowest combined number), look at the neighbors, either find them in the closed list or add/update them on the open list priority queue, move the current node to the closed list, then repeat. When you hit your target, you're done.)

Yup Im watching Sebastian Lague 's youtube tutorials and he does a implementation on priority queues which is nice. I'm just trying to figure out if I want to implement triggers for jump behaviour's or add in a "jump cost" to the heuristics when the grid is calculating a path. 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now