How to speed up least-cost path model at large spa

Question

Following on from How can I increase speed up simulation of my least-cost path model, I try to find a way to speed up my least-cost path model that runs at a large spatial scale. My landscape has an extent of 100km² (1000 patches x 1000 patches with 1 patch = 1 pixel).

For the moment, my code seems to work but it runs very slow: my code takes several hours to draw one least-cost path. The problem is that my model evolves according to discrete time steps of two minutes during 100 days and I have 1000 wolves in my landscape. For each wolf and at each time step, my model has to build the least-cost path between a polygon (composed of several patches) where there is a wolf and all polygons that are situated in a radius of 3km around the wolf.

I used the new version of NW-extension and I tried to optimize my model by saving all costs that have already been calculated to avoid to re-draw the least-cost paths. Unfortunately, my code is yet too slow and I don't know how to speed up it. Here is my code to calculate the cost of one least-cost path (If need be, I can provide more code to someone)

to-report path-cost-between-polygons [ID-polygon-1 ID-polygon-2] 
let path-cost -1

;; Define polygon edges
ask patches with [ID-polygon != ID-polygon-1] [
ask neighbors with [ID-polygon = ID-polygon-1] [
ask nodes-here [
set color red ] ] ]

ask patches with [ID-polygon != ID-polygon-2] [
ask neighbors with [ID-polygon = ID-polygon-2] [
ask nodes-here [
set color red ] ] ]

;; Calculate path cost
foreach sort ( (nodes-on patches with [ID-polygon = ID-polygon-1]) with [color = red] ) [ 
let node-on-polygon-1 ?  
foreach sort ( (nodes-on patches with [ID-polygon = ID-polygon-2]) with [color = red] ) [ 
let node-on-polygon-2 ?  

ask node-on-polygon-1 [ 
  let cost nw:weighted-distance-to node-on-polygon-2 "link-cost"  
  if path-cost = -1 or cost < path-cost [ 
    set path-cost cost ] ] ] ] 

;; Save path cost between polygons
set list-ID-polygons lput (list ID-polygon-1 ID-polygon-2) list-ID-polygons
set list-path-costs-between-polygons lput path-cost list-path-costs-between-polygons 

ask nodes with [color = red] [ set color white]

report path-cost
end

Thanks very much for your help.

Answer 1

I'm currently working on a new version of the NW-extension that will be much faster. Unfortunately, for weighted paths, it won't be available till NetLogo 5.0.6 comes out.

Until then, you could code your own least-cost path code. A* would be perfect for your situation. Implementing would definitely be somewhat tricky, but doable. If I have the time, I'll give it shot and post it here.