Tile Based A* Pathfinding, but with a bomb

Question

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 the generated path looks like the first image here:

Edit: actually it would look like this: https://i.sstatic.net/kPoAA.png

While the correct path would be the second image

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

Answer 1

Your "game state" will no longer only be defined by your location, but also by an integer representing the number of bombs you have left. If you're following the pseudocode of A* on wikipedia, this means you cannot simply implement the closedSet as a grid of booleans. It should probably be implemented as, for example, a hash map / hash set, where every entry holds the following data:

• x coordinate
• y coordinate
• number of bombs left

By visiting a certain position in the search process, you'll no longer mark just that position as closed. You'll mark the combination of position + number of bombs left as closed. That way, if later on in the same search process you run into a position where you're at the same location, but have more bombs left, you will not ignore it as closed but will actually continue searching that possibility.

Note that, if the maximum possible number of bombs is relatively low, you could also implement the closedSet as an array of boolean grids, where you first index by number of bombs, then by x and y coordinates to find out if a specific position is closed or not.