# Short distances from reference point

I would like to compute short distance from reference point in 2d grid. To expose:

• 0, 0: not penetrable
• 0, 1: not penetrable
• ...
• 1, 1: penetrable
• ...

I search an algorithm who return:

• 1, 1: 1
• 2, 1: 1
• 3, 1: 1
• 1, 2: 1
• 2, 2: 0
• 3, 2: 1
• ...
• 1, 6: 4
• 3, 6: 4

for 2, 2 reference point, 4 as maximum distance in exemple grid. What algorithm can to this (with good perf) ?

• en.wikipedia.org/wiki/Dijkstra%27s_algorithm – Vaillancourt Jun 14 '15 at 21:30
• nah, it's just BFS... Dijkstra is used when some nodes can be passed through but have some specific cost; like passing through themare considered them, is considered two turn. – Ali1S232 Jun 15 '15 at 15:47
• I agree with Ali.S — BFS will work well here. It's simple and fast. It also works if you have multiple reference points (see demo), which is handy for figuring out which reference point is closest to where you are. – amitp Jun 15 '15 at 22:56

An possible algorithm, expsed in python language:

def get_distances_for_points(object_position, max_distance):
points_distances = {}
points_to_looks = [object_position]

for current_distance in range(max_distance):
new_points_to_looks = []
for looked_point in points_to_looks:
around_points = <here return around points of looked_point>
for around_point in around_points:
if around_point not in points_distances and <here return True if around point is penetrable and False if blocked (wall)>:
points_distances[around_point] = current_distance+1
new_points_to_looks.append(around_point)
points_to_looks = new_points_to_looks

return points_distances


And according to comment of Ali.S and amitp: https://en.wikipedia.org/wiki/Breadth-first_search (demo)