Jump to content
  • Advertisement
Sign in to follow this  
Dxter

Finding the shortest path between points in a grid

This topic is 524 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

I'm trying to build a game where a person needs to start from a point 1 and clear his path to point 2. I researched this and found that the A* algorithm will do fine here. The problem with it comes is that I need to have multiple targets and find the smallest number of nodes to be cleared in order to connect all of the targets. Below is a simple grid to represent what I mean with 'o' being the uncleared fields, 'x' the unclearable fields, '1-4' are the points I need to connect and '.' are the cleared fields. Considering you can go back and use already cleared fields, the total count of fields to be cleared is 13.

816316ba748f4b2faf72dd37394f8ae22.png

I checked out the topic on A* algorithm with multiple goals, but I'm not sure that it can work for me, especially in the case that some of the fields can be cleared before the algorithm starts, which will change the final result. If someone has done something similar or can just point me in the right direction.

 dfd28c4c04f9599446dbdd8aa28c653f3.png

Here the fields needed to be cleared changes to 11 and also the path between 1-2. The whole thing is a project for my university studies and the part with the multiple points is not mandatory, but I want to solve it.

Share this post


Link to post
Share on other sites
Advertisement

Find the A* distance between each pair of points (there are 6 possible edges), then it just becomes an ordinary graph problem where you're looking for the singly connected graph with the lowest edge sum.

A singly connected graph will use exactly 3 of the 6 edges (20 combinations), and must include all 4 nodes (excludes 4 combinations) so there are 16 possible candidates for forming a singly-connected graph from four nodes.

Note that there are a couple opportunities for optimization here, but I'll leave that to you.

Share this post


Link to post
Share on other sites

Ok,
So you want me to calculate A* distance between all the points and include them into a graph and calculate the shortest path. The graph will look something like that (haven't included the weights)

53a9c0279e3fb03af8b148d769446ddb2.png

And now calculate the shortest path? 

Share this post


Link to post
Share on other sites

A path calculation with multiple goals is normally for having to pick one of the goals afaik, while you don't want a selection, you want all goals. Maybe A* is not what you need for solving the more complicated puzzle????

That is, in your search, did you look for "smallest path between 2 points" or for "smallest path between N points with re-use of path"? That can make a large difference.

Share this post


Link to post
Share on other sites
I agree with above: All pairs -> A* -> path graph -> find minimum spanning tree of path graph -> solution.

Share this post


Link to post
Share on other sites

A* finds the shortest path between two points, which is not what you described in the OP. If that's what you're looking for, then yes, just use A* again. If you're looking for "the smallest number of nodes to be cleared in order to connect all of the targets" then you'll need to think about how to efficiently find the singly connected graph with the lowest edge sum. Nypyren gave you a big hint by telling you the proper name of such a graph.

Share this post


Link to post
Share on other sites

I agree with above: All pairs -> A* -> path graph -> find minimum spanning tree of path graph -> solution.

Not exactly the MST. For an optimal solution it will not always suffice considering that 2 nodes must have a degree of 1 and the other 2 must have a degree of 2. For this subset of spanning trees, we want to find the minimal one.

(Sorry for nitpicking :P)

Share this post


Link to post
Share on other sites

I agree with above: All pairs -> A* -> path graph -> find minimum spanning tree of path graph -> solution.

Not exactly the MST. For an optimal solution it will not always suffice considering that 2 nodes must have a degree of 1 and the other 2 must have a degree of 2. For this subset of spanning trees, we want to find the minimal one.

(Sorry for nitpicking :P)


Another thing... After re-reading the initial post I need to revise my thinking. The goal is to minimize the *total path nodes used*, not the total path *length*. I don't think using A* as a first pass is going to be able to know how to share path nodes. Basically, we want a MST, with the modification that it only needs to go far enough to connect points 1 through 4.

This feels like a problem that might need Ant Colony Optimization.

(Side note: This is exactly what I do when I connect all of the pump jacks in an oil field in Factorio) Edited by Nypyren

Share this post


Link to post
Share on other sites

My interpretation was that he was talking about the nodes in a regular 2D grid like he showed in the images, so the A* path between the target nodes would be effective as edge weights for the second problem.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!