Path finding Algorithm for changeable environments

Question

I am having trouble adapting the A* algorithm to handle changing environments. As a minimum example, consider this rogue-like map:

######
#!   #
###  #
#S   #
##+###
##F###
######

The goal is to get from S to F, but in order to do so the player must step on ! to open the door. The problem I'm having is that in A* once a grid point is visited it becomes "closed" and cannot be reentered. How can I modify the algorithm to solve this puzzle?

Answer 1

You can run A* twice:

1. First find shortest path to the switch (!) where the door is like a wall
2. Then find shortest path to the end from the switch, where the door is blank tile.

The shortest path will be the combination of these two paths.

Answer 2

In your problem, it is not true that in A* when you visit a point (x,y cord) you won't visit again the same point.

The reason is that in your problem, state is position in the grid and for each door its state (open or close). So at the beginning, in your example, the initial state is (3,1,{false}). (false means the door is closed).

When you reach the '!' position, the new state will be (1,1,{true}) so now when you reach the door you will pass the door.