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.

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.

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