path finding - Tile Based A* Pathfinding, but with a bomb

I've written a simple A* path finding algorithm to quickly find a way through a tile based dungeon in which the tiles contain the information of walls.

An example of a dungeon (only 1 path for simplicity):

However now I'd like to add a variable amount of "Bombs" to the algorithm which would allow the path-finding to ignore 1 wall. However now it doesn't find the best paths anymore,

for example with use of only 1 bomb it generates paths like these:

While the correct shortest path would be this one:

The problem is that "Closed Nodes" now interfere with possible paths. Any ideas of how to tackle this problem would be greatly appreciated!

Answer

The typical approach here would be to treat your remaining bomb count as an additional dimension in the pathfinding space.

So given this situation

2      ↑
   ──────┐
1   ←  o │ →
         │
0      ↓ 

    0  1   2

Our tile at the o (1, 1, 4 bombs) has the following reachable neighbours in the cardinal directions:

     x   y   bombs   cost
---------------------
←    0   1     4    1 step
↓    1   0     4    1 step
→    2   1     3    1 step + 1 bomb
↑    1   2     3    1 step + 1 bomb

This solves the problem of "closed nodes" interfering with possible paths, because the node you reach by blasting through the wall to the right (2, 1, 3 bombs) is different from the node you reach by walking down past the end of the wall, then right, then up (2, 1, 4 bombs). So marking one as closed doesn't prevent exploration of the other.

To make sure you can still terminate the algorithm, you count every node on the exit tile as a goal node, regardless of the number of bombs left - so a path can be considered complete whether it used no bombs or all 4. A*'s cost minimization will choose the best one according to the parameters you give it.

You can adjust your cost function to decide whether the algorithm should always find the shortest number of steps even if it has to use all the bombs (bomb cost = 0), or give it some trade-off like "use a bomb if it saves more than 3 steps" (bomb cost = 2 x step cost, since a bomb use always comes with one step too)

When your maps or number of dimensions are large, you'd probably want to construct these tiles only as-needed, rather than reserving an array for every conceivable configuration (of which many will never be used). For the case you describe though, an exhaustive collection wouldn't be a problem.