Shortest path in a maze with health loss

Question

Suppose you have a dungeon, represented by a 2D matrix. You have a start point S (x1,y1) and an end point E (x2, y2). Along the way, some cells have a number in them, which subtract from your health score. Other cells are obstacles that you can't go through. You start with 5 health points, and you need to find the shortest path from S to E where you don't die on the way.

I know that Dijikstra is used to find shortest paths. But in this case the shortest path might be one in which you die along the way. How do you find the shortest path where you don't die? Note that there is no advantage to completing the race with more health points so long as you're alive at the end.

Answer 1

Just use A*, moreover decrease health every move accordingly, but consider every move that would cause health to reach 0, as if that case were an obstacle case.

Edit: for OP convenience, I will enclose a link to articles about A*: this and this and this

Explainatory Note: It might be tricky to see, A* tries greedy first, but then backtraces and will eventually find the shortest possible route. Here I am not suggesting that a case is forever labelled as an obstacle, but merely locally considered equivalent to obstacle for the current selection if it causes a death. After finding the first path, this extended A* should not stop, but use the length of this path as upper bound and backtrace, in a decisional tree, checking all open paths. It will work.

Answer 2

The standard approach to problems like this is sometimes called 'graph layering'. You make 5 copies of the original graph (numbered 0 through 4 in this case), where getting to a vertext v in graph n means getting to the corresponding vertex in the original graph after suffering n deaths.

If an edge in the original graph costs you a life, then it connects a vertex in each graph i to a vertex in graph i+1, and otherwise it connects vertices in the same version of the graph just like the original.

After constructing this graph, use Dijkstra's algorithm to find the shortest path to the terminal vertex in any layer.