1
$\begingroup$

Let's suppose we have a square grid board like the one shown in the picture below: Square grid

I'm wondering how I can find the path with minimum number of "bending" points (like the ones shown in red) between two given squares ("Start" and "Finish"). The board has some impediments or broken squares on it (Black squares).

I tried to run a BFS algorithm and find all of the minimum cost paths and then pick up the one with minimum bending points, but this won't give us the optimal answer.

Is there a way to efficiently solve this problem?

Motivation: I was trying to solve a computer game using A* algorithm, and I figured out I can use the solution to this problem as a heuristic function to solve the game.

$\endgroup$
0
1
$\begingroup$

Create an undirected weighted graph $G$ with two vertices $h_c$, $v_c$ for each (non-obstacle) cell $c$ of the grid. Intuitively $h_c$ encodes entering $c$ from the left or right and $v_c$ encodes entering $c$ from the top or bottom.

For each pair of horizontally adjacent cells $c, c'$ add the edge $(h_c, h_{c'})$ with weight $0$. For each pair of vertically adjacent cells $c, c'$ add the edge $(v_c, v_{c'})$ with weight $0$. For each cell $c$, add the edge $(v_c, h_c)$ of cost $1$ (this encodes changing direction).

If the starting cell is $s$, add a new vertex $s^*$ along with the edges $(s^*, h_s)$ and $(s^*, v_s)$ of cost $0$. Similarly, if the target cell is $t$, add a new vertex $t^*$ along with the edges $(h_t, t^*)$ and $(v_t, t^*)$ of cost $0$.

The path with the minimum number of bends in the grid is the one corresponding to the shortest path between $s^*$ and $t^*$ in $G$. Such a shortest path can be found in time $O(n)$ where $n$ is the number of cells (since weights are non-negative and bounded by a constant, there are $2n+2$ vertices, and each vertex has degree at most $4$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.