Introduction
While solving google foobar I stumbled upon this problem. I approached the problem with A* along with a few modifications. As this algorithm correctly outlines the core concepts, I would like to go further ahead and add some detailing to this.
Algorithm:
Each node will have the following parameters:
1. parent: The immediate parent of the node.
2. position: This is the (x,y) position of the node.
3. f,g,h: These are the heuristics needed for A* to work.
4. wall_broken: This is a boolean flag that would account for a broken wall in the path to the node. By default is set to False.
After we set up our pre-requisites, we move into the algorithm.
1. Create the start and end node.
2. Initialize the open and closed lists. The open list must contain the start node.
3. Iterate until we have visited each node.
1. Take the node with least f from the open list. 835
This is our current node. Remember putting it inside the visited list.
2. Check whether the current node is the end node. When comparing equality, we will compare the positions of the nodes only. If yes, then hurray! Return the path that has been traced. If no, perform the next step.
3. Generation of children from the current node.
+ Check for validity of the position.
+ Check if the position has a wall. If it does, then we need to check whether the current node has any broken walls in its path (this is where we will need the wall_broken property of the node). We destroy the wall if we have no prior destruction. We make sure to assign the wall_broken property of the child which broke into a wall to True.
+ We do not generate children if they already have been visited.
4. Iteration on the children to decide which goes into the open list and which don't.
* Assign heuristics to each child.
* Look for a better child in open to replace. Else add it into the open list.
Conclusion
This algorithm is a modification of the A*. It conveys the core concept. If you want a detailed walkthrough of the concept with code, I have a gist written in python. 242