title: How to speed up A* algorithm at large spatial scales?
body: <p>From <a href="http://ccl.northwestern.edu/netlogo/models/community/Astardemo1" rel="noreferrer">http://ccl.northwestern.edu/netlogo/models/community/Astardemo</a>, I coded an A* algorithm by using nodes in a network to define least-cost paths. The code seems to work but it is much too slow when I use it at large spatial scales.My landscape has an extent of 1000 patches x 1000 patches with 1 patch = 1 pixel. Even if I reduce it at 400 patches x 400 patches with 1 patch = 1 pixel, it is yet too slow (I can't modify my landscape below 400 patches x 400 patches). Here is the code:</p>
  
  <pre><code>to find-path [ source-node destination-node] 
  
  let search-done? false
  let search-path []
  let current-node 0
  set list-open []
  set list-closed []  
  let list-links-with-nodes-in-list-closed []
  let list-links []
  
  set list-open lput source-node list-open
  while [ search-done? != true]
  [    
  ifelse length list-open != 0
  [
    set list-open sort-by [[f] of ?1 &lt; [f] of ?2] list-open 
    set current-node item 0 list-open 
    set list-open remove-item 0 list-open 
    set list-closed lput current-node list-closed
    ask current-node
    [  
      if parent-node != 0[
      set list-links-with-nodes-in-list-closed lput link-with parent-node list-links-with-nodes-in-list-closed 
      ]
      ifelse any? (nodes-on neighbors4) with [ (xcor = [ xcor ] of destination-node) and (ycor = [ycor] of destination-node)]
      [
        set search-done? true 
      ]
      [        
        ask (nodes-on neighbors4) with [ (not member? self list-closed) and (self != parent-node) ]  
        [  
          if not member? self list-open and self != source-node and self != destination-node
          [
            set list-open lput self list-open
            set parent-node current-node
            set list-links sentence (list-links-with-nodes-in-list-closed) (link-with parent-node)
            set g sum (map [ [link-cost] of ? ] list-links)
            set h distance destination-node 
            set f (g + h)
          ]
        ]
      ]
    ]
  ]
  
  [
    user-message( "A path from the source to the destination does not exist." )
    report []
   ]
  ]
  set search-path lput current-node search-path
  let temp first search-path
  while [ temp != source-node ]
  [
   ask temp
  [
    set color red
  ]
  set search-path lput [parent-node] of temp search-path 
  set temp [parent-node] of temp 
  ]
  set search-path fput destination-node search-path
  set search-path reverse search-path  
  print search-path
  end
  </code></pre>
  
  <p>Unfortunately, I don't know how to speed up this code. Is there a solution to calculate rapidly least-cost paths at large spatial scales ?</p>
  
  <p>Thanks very much for your help.</p>