2
\$\begingroup\$

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
  • ...

enter image description here

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) ?

\$\endgroup\$
  • 5
    \$\begingroup\$ en.wikipedia.org/wiki/Dijkstra%27s_algorithm \$\endgroup\$ – Alexandre Vaillancourt Jun 14 '15 at 21:30
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Ali1S232 Jun 15 '15 at 15:47
  • \$\begingroup\$ 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. \$\endgroup\$ – amitp Jun 15 '15 at 22:56
1
\$\begingroup\$

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)

\$\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.