title: Optimized wayfinder
body: <p><em>I have a quite difficult problem to solve and I'll try my best to describe it. I'm not a native English speaker so if there is any doubt about what I meant, ask me</em></p>
  
  <p><strong>Description</strong></p>
  
  <p>I'm struggling with some sort of pathfinder. I have a grid with a list of N points of coordinates [x,y]. You need to go from a point A to a point B, both belonging to the previous list. You can only move between two existent points. I need a function which takes as parameters the list of points, the start point A, the end point B and a maximum distance D.</p>
  
  <p>The goal is to find whether you can go from A to B using intermediate points without having to ever travel more than a distance D between two consecutive points of your path. In case you can't, we need to find the minimal distance D' which follow the rule above.</p>
  
  <hr>
  
  <p><strong>An example:</strong> <img src="https://i.stack.imgur.com/FgcRO.png" alt="Example graph"></p>
  
  <p>To go from point 7 to point 5 on this graph, the path that minimize the maximum distance ever traveled between two points is 7 > 1 > 17 > 15 > 8 > 10 > 3 > 16 > 5</p>
  
  <hr>
  
  <p><strong>Solution</strong></p>
  
  <p>I've come up with a solution to this problem using Python. However, when there are more than a hundred points, my script is suffering. I've really tried to optimize this to the maximum by reducing useless memory affectation and trying to avoid useless tests, however, it's still not sufficient. Do you have any ideas on how to improve it's effectiveness? I've thought to try recursive methods but I don't think this will change anything since this is just an iterative way to write recursion. Any tips is welcome :)</p>
  
  <p>My solution to the problem using python:</p>
  
  <pre><code>def OptimizedPath( a, b, points, Dmax ):
  # Dmax is the maximal distance you can travel between two points
  # D is a function which calculate the distance between two points
  maxi = D( points[a], points[b])
  if maxi &lt; Dmax: # if the direct travel is already ok
      return Dmax
  else:
      ways = [[a]]    # itervative methode to explore all paths
      while ways != []:
          nways = []  # new matrix that will contain all paths of n+1 points
          for w in ways:
              # PAcc returns the list of points you can access in less than a distance maxi
              for i in PAcc( w, maxi, points):
                  nways.append( w + [i] )
  
          ways = []
          for w in nways:
              if w[-1] == b:  # if a path has arrived to it's destination
                  if Dmaxw( w, points ) &lt; Dmax:   # if it has done it without traveling more than Dmax between two points
                      return Dmax
                  elif Dmaxw( w, points ) &lt; maxi: # if it has done it better than the best path found
                      maxi = Dmaxw( w, points )
              elif Dmaxw( w, points ) &lt; maxi: # if it's not over and the maximum distance between two points is smaller than maxi
                  ways.append( w )
      return maxi
  </code></pre>