Sign in to follow this  
Dxter

Finding the shortest path between points in a grid

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

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 actually did find the "Travelling Salesman problem", but didn't implement any solutions. I think that http://stackoverflow.com/questions/2501732/algorithm-shortest-path-between-all-points has the solution in the top answer, but considering I've only 4 nodes, I will try the A* algorithm first with the graph after that.

Edited by Dxter

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
Let's see if some ASCII art helps with what I'm thinking about:
 
Let's say for this example we can only move in cardinal directions.

6 intermediate nodes (Dxter calls these "cleared" nodes):

1.....2
   .
   3

...would be better than...

8 intermediate nodes:

1     2
.     .
...3...

...even though the number of steps found by A* is the same (10).

If we feed A* results into a MST and get: (1 -> 3 with cost 5, 3 -> 2 with cost 5),
we still don't know the best way to find the paths that share those intermediate nodes.
Edited by Nypyren

Share this post


Link to post
Share on other sites

I'm not sure what you're saying. Those graphs should have the same score of 10. The edges in your first graph are lengths 5 and 5.

 

edit:

Ah, never mind. I got it.

That's only a little bit more complex, but I'd be asking for clarification of the requirements at this point.

Edited by Khatharr

Share this post


Link to post
Share on other sites

Yes,
A* will not be the right solution for my problem having multiple nodes. I need something for finding the shortest path between N points by reusing the same path. The whole thing can be imagined as a grid of obstacles, some are removable and some are not, and when you clear a removable obstacle, moving back on it has not cost. I was misled by the initial 2 point connecting task, that can work with A*.

Edited by Dxter

Share this post


Link to post
Share on other sites

I was misled by the initial 2 point connecting task, that can work with A*.
You're searching for the set of positions to take in order to reach the destination.

 

I need something for finding the shortest path between N points by reusing the same path. The whole thing can be imagined as a grid of obstacles, some are removable and some are not, and when you clear a removable obstacle, moving back on it has not cost.
You're searching for the set of obstacles to take in order to get a free path to all points.

A* will not be the right solution for my problem having multiple nodes.
I think you can, by seeing the initial grid as starting point, and the grid with free paths to all nodes as end-point, and in-between, grids with some partial fields taken out.

The branching factor is far beyond horrible though, and the estimate becomes an interesting problem by itself (although solvable by A*), so I am really wondering if this is what is intended :p

Share this post


Link to post
Share on other sites

I think that you can still use A* for the initial step, but stop me if I'm wrong here.

The smallest connected system should be primarily composed of the MST, but you may be able to crop some parts if you have overlapping with weird geometry (I think? It seems like it but I'm having trouble imagining an example.). I think that in most cases you'll just end up with a sort of "virtual node", like Nypyren showed, since the path from that position to its connecting "real" nodes will always be the A* shortest path that led to there in the first place.

This is becoming a problem of finding a proof for this system. -.-

Share this post


Link to post
Share on other sites
I have an idea for a naive single-pass solver that I'm going to try: Do Dijkstra's/wavefront/BFS traversal simultaneously starting at all of the waypoints. I suspect the optimal nodes will involve the 'ridge' that forms when wavefronts meet. Edited by Nypyren

Share this post


Link to post
Share on other sites

It's above my level (second year university), but I guess this is why I'm here :D . I will try Nypyren idea anyway, I understand that your solution involves starting the algorithm from all 4 points and when they meet it's the optimal path.

Share this post


Link to post
Share on other sites

Wasn't this a breadth-first search on a graph? This map also looks like a graph where each node has 8 neighbors.

X chars would just delete 1 neighbor connection. Root is the starting point, building a tree from that point shouldn't be complex. Or is it?

Edited by between3and26characters

Share this post


Link to post
Share on other sites
My concept appears to guarantee an optimal solution, BUT it's quite a bit more complicated than I'd hoped.

- Do a flood fill from each waypoint, tallying up cost-per-waypoint (distance) in each cell.
- Increment cost when you step FROM a non-free cell, rather than TO a non-free cell, to handle the case where some cells start cleared before traversal (just some disgusting nuance to the rest of the algorithm).

- After all four traversals finish, foreach cell, sum up its four costs.
- Find the cell(s) that contain the minimum of these sums (there will usually be more than one of these, but they are always contiguous). This is what I was calling the 'ridge' in my previous post, but it turns out it's not really a ridge at all once you see what it actually looks like.

- For each waypoint, find the cell within the minimum-sum-region with the lowest cost to "exit" the region towards that waypoint. Call these cells 'exit points'.
- Calculate the exit-to-exit costs by applying the same parallel-flood-fill concept, but limit traversal to the minimum-sum-region.
- Treat all eight cells (four exit points, four waypoints) as a graph and make an MST out of them using Prim's algorithm using the costs previously calculated in the flood fill.

It's instantaneous on the 8x8 examples above but would probably be pretty damn slow on game-sized graphs.

The flood-fill loop can probably be terminated the moment all four costs are available and the sum of the cell you would traverse into increases (which indicates your wavefront is exiting the minimum region).

I don't know if there's any way to use A*-style heuristics during the traversal.

Edge cases:

- The minimum-sum-region can contain one or more of the waypoints themselves. If this happens, those waypoints will effectively be their own exit nodes and you can just include them once in the graph that you feed to Prim's algorithm. This usually happens if the points are arranged in a rectangle with no obstacles between them. The resulting MST for the above algorithm if ALL points are within the minimum-sum-region will be the same as if you had A*-then-MST'ed them. Edited by Nypyren

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

Sign in to follow this