# Dxter

Member

5

106 Neutral

• Rank
Newbie
1. ## Finding the shortest path between points in a grid

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.
2. ## Finding the shortest path between points in a grid

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*.
3. ## Finding the shortest path between points in a grid

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.
4. ## Finding the shortest path between points in a grid

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) And now calculate the shortest path?
5. ## Finding the shortest path between points in a grid

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. 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.   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.