Calculate the number of steps to reach another square from a square in a grid and use it for the h cost in A* algorithm

Question

My goal is to select a square in a grid then displays the number of steps needed to reach each square in the grid assuming there are obstacles in the grid. I'm thinking of recursion but I'm not sure if it's possible. Any other ideas?

Something just like this (p.s. just disregard the blue spot):

Edit: Are the values good for the h cost in the A* algorithm?

Answer 1

Essentially you need to emulate graph and use appropriate graph algorithm suitable for your case.

Emulation of graph is rather simple - vertex A,B exists if squares are adjucent and neither of them is obstacle. Enumerating vertexes connected to point (x, y) is simple - check bounds for (x-1, y), (x+1, y), (x, y-1), (x, y+1) and check if they are not obstacles.

So, if you have no weights, you can use mentioned Breadth-first search https://en.wikipedia.org/wiki/Breadth-first_search

Also you can use Dijkstra's algorithm, even though it's a bit slower: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm or A* algorithm: https://en.wikipedia.org/wiki/A*_search_algorithm

At last, you can use Bellman-Ford algorithm: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm