python - How to find the shortest path in 2D maze array, where direction is changed only when obstacle is hit

Question

I am struggling to implement an algorithm that resolves a 2D maze array by only changing a direction once a wall or another obstacle is hit.

What it needs to do is, given the following array (where x is the start, 1 is an obstacle, g is the goal) find the shortest path by only hitting obstacles first (no changing direction of movement unless obstacle/wall is reached).

[[1, 1, 1, 1, 1]
 [1, x, 0, 0, 1]
 [1, 0, 0, 0, g]
 [1, 1, 1, 1, 1]]

The solution should be:

[(1,1), (1,2), (1,3), (2,3), (2,4)]

or

[(1,1), (2,1), (2,2), (2,3), (2,4)]

In the example above, it moves only next to the maze walls, but that's only because the example is very small. All in all, it should only move in the 4 directions and not change it's course once it starts a direction until an obstacle is met. Here is a more visual example:

question from:https://stackoverflow.com/questions/65873972/how-to-find-the-shortest-path-in-2d-maze-array-where-direction-is-changed-only

Answer 1

Using A* it should be relative simple

• use Manhattan distance for heuristic
• when taking next edge just walk in the current direction until an obstacle is encountered and return that as the next node.
• use the heuristic as tie-breaker in the priority queue.
• save the generated nodes in a dictionary so you can check if they already have been visited.