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?

Does the player know that pressing that ! opens the door +? Because if there are multiple switches without an indication which door they open, the A* assumption of full information fails and the algorithm cannot solve the problem. (Also, vanilla A* is pretty bad at handling mazes.) — Fred Foo
– Fred Foo, Commented Jul 14, 2012 at 19:45

amit · Accepted Answer · 2012-07-14 19:24:11Z

3

You can run A* twice:

First find shortest path to the switch (!) where the door is like a wall
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.

answered Jul 14, 2012 at 19:24

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

barak1412 · Accepted Answer · 2012-07-14 19:41:17Z

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.

answered Jul 14, 2012 at 19:41

barak1412

1,1709 silver badges21 bronze badges

Collectives™ on Stack Overflow

Path finding Algorithm for changeable environments

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related