Optimized Path

extensions [nw table]

breed [waypoints waypoint]
breed [nodes node]

globals [
  list-distance
  list-path-waypoint
  list-distance-path
  list-dist-path
  list-links
  list-all-path
  list-total-distance
  waypoint-count
  number-waypoint
  list-waypoints
  strating-point
  path
  previous-waypoint
  total-distance
  final-distance
  fp
]

waypoints-own [
  distances-to-other-waypoint
]

links-own [
  street-length
]

;*********SETUP*************

to setup
  clear-all
  set-default-shape nodes "dot"
  set-default-shape waypoints "dot"
  
  ask patches with [abs pxcor < (grid-size / 2) and abs pycor < (grid-size / 2)][ 
    sprout-nodes 1 [ set color blue]
  ]

  ask nodes [
    if Show_Names_Nodes? = True [
      ifelse label = "" 
        [set label (word who " ")]
        [set label ""]
    ]
    let neighbor-nodes turtle-set [turtles-here] of neighbors4
    create-links-with neighbor-nodes [
      set street-length link-length
      set color grey
      set thickness 0.1
    ]
  ]
  
  ask nodes [
    setxy (xcor * (max-pxcor - 1) / (grid-size / 2 - 0.5))
          (ycor * (max-pycor - 1) / (grid-size / 2 - 0.5))
  ]
  
  create-waypoints nb-waypoints
  ask waypoints [
    setxy random-xcor random-ycor
    set color red
    if Show_Names_Waypoints? = True [
      ifelse label = "" 
        [set label (word who " ")]
        [set label ""]
    ]
    let closest-node min-one-of nodes [distance myself]
    create-link-with closest-node [
      set street-length 0
      set thickness 0.1
      set color white]
  ]
end 


;*********GO*************

to-report optimized-path
  
  let select-optimized-path []
  set list-distance []
  set list-path-waypoint []
  set list-distance-path [] 
  set list-dist-path [] 
  set list-links []
  set list-all-path [] 
  set list-total-distance [] 
  set waypoint-count count waypoints 
  set number-waypoint count waypoints
  set list-waypoints sort-on [who] waypoints
  
  let r 0
  let h 0
  let i 0
  
  while [r < number-waypoint][
    let first-waypoint item r list-waypoints
    set strating-point item r list-waypoints
    set list-waypoints remove first-waypoint list-waypoints
    
    while [h < number-waypoint - 1][
      
      while [i < waypoint-count - 1][
        
        ask first-waypoint [
          let waypoint-next item i list-waypoints
          set path nw:weighted-path-to waypoint-next "street-length"
          set distances-to-other-waypoint nw:weighted-distance-to waypoint-next "street-length"
          set list-distance lput distances-to-other-waypoint list-distance
          set list-path-waypoint lput waypoint-next list-path-waypoint
          ]
        
        set i i + 1 
        ]
      
      let dw (map [(list ?1 ?2)] list-distance list-path-waypoint)
      set list-distance-path sort-by [first ?1 < first ?2] dw
      let closest-waypoint last (item 0 list-distance-path)
      
      ask first-waypoint [
        set path nw:weighted-path-to closest-waypoint "street-length"      
        set distances-to-other-waypoint nw:weighted-distance-to closest-waypoint "street-length"
        set list-links lput path list-links
        set list-dist-path lput distances-to-other-waypoint list-dist-path
        set previous-waypoint first-waypoint
        ask closest-waypoint [set first-waypoint closest-waypoint]
        ]    
      
      set i 0
      set h h + 1   
      set list-distance []
      set list-path-waypoint []
      set list-distance-path []
      set list-waypoints remove previous-waypoint list-waypoints
      set list-waypoints remove first-waypoint list-waypoints
      set waypoint-count waypoint-count - 1
      ]
    
    set total-distance sum list-dist-path
    set list-all-path lput list-links list-all-path 
    set list-total-distance lput total-distance list-total-distance
    
    set h 0
    set r r + 1
    set list-waypoints sort-on [who] waypoints
    set waypoint-count count waypoints 
    set list-dist-path []
    set list-links []
    ]
  
  let temp (map [(list ?1 ?2)] list-total-distance list-all-path)
  let fpt sort-by [first ?1 < first ?2] temp 
  set select-optimized-path item 0 fpt
  
  report select-optimized-path
end 

to compute-optimized-path
  
  ask links [set color grey]
  let temp optimized-path
  set final-distance item 0 temp
  set fp item 1 temp
  
  let s 0
  let total count waypoints
  while [s < total - 1][
    let dummy item s fp
    let t 0
    while [t < length(dummy)][
      ask item t dummy [
        set color yellow
        set thickness 0.3
      ]
      set t t + 1
    ]
    set s s + 1
  ]
  
 print (word "The shortest path between all waypoint is " fp)   
 print (word "and has a length of " final-distance " meters ")
end