Best path in a grid

Question

I have a best path problem to solve. Given a nxn grid populated with walkable tiles and non walkable tiles, I have to reach point B from point A, through the shortest path. The trick is some of the walkable tiles contain points. To be a valid solution when I reach the goal I must have a certain number of points. The tiles have a variable number of points on them( or none) and I need the shortest path to reach the goal but to also have gathered at least M points on the way.

What I have tried is the A* algorithm which finds the shortest path between the 2 points and tried to customize it to have the stop condition not just when it reaches the goal but to also have the necessary points. It doesn't work the way I made it because I am blocking the paths.

If you have any suggestions how to approach this problem or another algorithm that would be more suited I would appreciate the help. Thanks.

Ephemerality

Have you taken a look at Dijkstra's algorithm? – Mcmurry

Can I pick up points from the same tile more than once? In other words, if the grid has a loop that includes some tiles with points, can a valid path contain such a loop to come up with the necessary number of points before arriving at the final destination? – Negrete

@Mcmurry The "plain" Dijkstra (or Floyd-Warshall) are not going to help, because the optimization task has a second dimension to it. – Negrete

@dasblinkenlight Nope, the points are pickable only once. – Ephemerality

@Mcmurry I have looked at Dijkstra and in my opinion I will have the same problem as with A*. – Ephemerality

Does the path have to be simple? (I.e., can we revisit squares not for the points but to make the solution shorter or even existent?) – Noahnoak

Yes you can revisit squares, if you have gathered the necessary points and the shortest path is through some already visited squares than it is needed to go through them. – Ephemerality

Answer 1

In case you're still stuck on this problem, as the other answers/comments only give you a partial answer -- here's a crack at the problem space.

You can actually use A* with a few modifications to capture a (mostly) unordered M point path. The only things you need to change are the heuristic and the termination criteria.

First you need to change your heuristic to account for paths through M points. The heuristic must be admissible and consistent, so it must equal a value less than or equal the true path cost and it can only decrease as you get closer to the goal (must be monotonic increasing).

You can think of the path you're now taking as M subpaths you must complete, each of which acts as a normal path. Thus for a single point graph (with only a terminating space) you can use a standard heuristic like Euclidean distance. This is a greedy estimate that suggests a straight path is optimal and for which you can't do better under ideal circumstances (it's admissible).

For more than one path the greedy approach similarly says that an unblocked straight path between points is the fastest you can go. It's also still a consistent heuristic because you can't step further away and still have a better score. The hard part is picking which ordering of M points is the fastest without obstructions in order to maintain an admissible heuristic. You can find the optimal choice of M points in a graph where all tiles are walk-able by breadth first searching the Euclidean distance from your current tile to each of M points, to each of M-1 remaining points, ..., to the terminating square. This operation is expensive as you need to do it for each square you reach -- but you can use dynamic programming or search caching to bring the required amortized computation down to O(M) per step.

Now, once you have the M point paths which would be fastest without obstacles you can use the Euclidean distance between each point in that path and your current position as the heuristic. It's a greedy movement estimate, so it's always admissible (you can't beat the estimated cost) and it's consistent because you can't walk away from the next greedy optimal point and reduce your cost because choosing a different greedy point from the current tile would not be admissible.

Finally your terminating criteria needs to change to reaching M points, where the last point is the terminating tile. This imitates walking M graphs without needing to construct M! possible graphs to walk. The provided heuristic will let A* do it's magic without changing the underlying algorithm and should be about as effective as you can get while maintaining the required constraints on the heuristic on generic grids.

Waterproof

I have solved the problem myself but your answer is the closest to what I have done. – Ephemerality

Answer 2

You can add layers to your graph, when you are at layer of depth X -> you've collected at least X points. Add appropriate edges at your graph from upper layer, to layer +N where N is number of points at current tile.

Your graph is infinite, but you can just dynamically add number of layer to vertex handle, when traversing some edge. And as it infinite, you can't tell if finish is reachable, but you can check if path on base graph exists and if there is at least one point.

You should place finish on levels >M.

If you need some clarifications, ask =)

Edit

As @Pyrce said, you also should provide consisten heuristic, if you are planning to use A* http://en.wikipedia.org/wiki/Consistent_heuristic

Illfavored

+1 for clean answer, though his graph is not infinite just maybe really really big as you can only capture M points in permutation(M) ways. You might also want to add that the heuristic needs to change for A* as well -- i.e. distances are now no longer in 2D. – Waterproof

@Waterproof In general, graph is infinite, because M is input parameter, like start and finish. For A* case, heuristic, as always, is not that simple task =) But I think normal heuristic(Manhattan distance to finish) with weighted addition like abs(cur_level - M) would do it right – Illfavored

Yes, but M is fixed upon starting the algorithm and doesn't change. An M of 4 points would provide 24 possible permutations to be solved thus the graph size would be NxNx(M!) = 24N^2; big but much smaller than infinite. Granted there are infinite possible choices of N and M to start the problem. The heuristic you suggest is admissible but not consistent as you can fall into a hole at the solution point, before reaching all M points, where moving away makes the heuristic non-monotonic. See en.wikipedia.org/wiki/Consistent_heuristic. Just thought you should add it to your answer. – Waterproof

@Waterproof Yes, I know about heuristic, but as I said, correct one is tricky. I'll add your link to answer. As about size, I was trying to separate search space from search problem. It the task of the algorithm not to go to far =) – Illfavored