NetLogo A* implementation on nodes and links

NetLogo_A-star_Implementation.nls

; ########################################
; ####     NetLogo A* Algorithm     ######
; #### Author : Robin Cura          ######
; #### Contact : robin.cura@gmail.com ####
; #### Date : 09/07/2013            ######
; #### Licence : GPL v2             ######
; ########################################



; ##### ENVIRONMENT #####

breed [nodes node]

globals [
  cursor ; When reading backward the path, this is used to define the shortest-path
  switch-off ; For A* computation, this is used to stop the agents spread loop
  switch-off2 ; Another switch, to stop the shortest path retrieving
]

nodes-own [
g-cost ; Weight since starting node
h-cost ; Weight to ending node
f-cost ; Total weight (g-cost + h-cost)
owner ; Who's before me ?
owner? ; Is there some node after me ?
open? ; Am I in the open list ?
path? ; Am I on the shortest-path ?
]


; ##### SETUP #####

to init-nodes
  set switch-off false
  set switch-off2 false
  ask nodes [
    set g-cost false
    set h-cost false
    set f-cost false
    set owner false
    set owner? false
    set open? true
    set path? false
  ]
end

to init-astar [#start-node #end-node]
  ask #start-node
  [
    set owner self
    set owner? true
    set open? false
    set h-cost calculate-h #end-node
    set g-cost 0
    set f-cost h-cost + g-cost
    ask link-neighbors 
    [
      set open? false
      set owner myself
      set owner? true
      set h-cost calculate-h #end-node
      set g-cost calculate-g
      set f-cost h-cost + g-cost 
    ]
  ]
end

; ##### MAIN FUNCTION #####

to-report network-distance [#start-node #end-node]
  ; 1) Init of pointers/variables for all nodes
  init-nodes
  ; 2) Init of pointers/variables for start-node and its neighbors
  init-astar #start-node #end-node
  ; 3) A* computation
  browse-network #start-node #end-node
  report [g-cost] of #start-node
end

; ##### REPORTERS #####

to-report calculate-h [#end-node]
  ; Weight toward ending, according to the heuristic
  ; To change the heuristic, change result and h-scale
  let result 0 
  set result distance #end-node
  let h-scale (1 + (16 / 8 / world-width + world-height))
  set result result * h-scale 
  report result
end

to-report calculate-g
  ; Cumulated weight from start
  let linklength distance myself
  let g-scale (1 + (16 / 8 / world-width + world-height))
  set g-scale 1
  let result ( linklength * g-scale ) + [g-cost] of myself
  report result
end

to browse-network [#start-node #end-node]
  while [switch-off = false]
    [
      ifelse (count nodes with [open? = true] >= 1 )
        [
          ask min-one-of (nodes with [(open? = false) AND (any? link-neighbors with [open? = true])]) [f-cost] 
          [
            if (self = #start-node) [stop]
            spread #start-node #end-node
          ]
        ]
        [print "there is no way..." stop]
    ]
end

to spread [#start-node #end-node]
  ask link-neighbors
    [
      ifelse (open? = true)
      ;; OPEN
      [ 
        set owner myself
        set owner? false
        set open? false
        set h-cost calculate-h #end-node
        set g-cost calculate-g
        set f-cost  h-cost + g-cost
      ]
      ;; CLOSED
      [ 
        let h-temp-cost calculate-h #end-node
        let g-temp-cost calculate-g
        let f-temp-cost  h-temp-cost + g-temp-cost  
        if ( (f-temp-cost < f-cost) AND ([owner] of myself != self) )
        [
          set h-cost h-temp-cost
          set g-cost g-temp-cost
          set f-cost f-temp-cost
          set owner myself
          set owner? false 
        ]
      ]
      if (self = #end-node) 
      [
        show-path #start-node #end-node
      ]  
    ] 
end


to show-path [#start-node #end-node]
  set cursor #end-node
  while [switch-off2 = false] 
  [
    if (cursor = #start-node) 
    [
      set switch-off2 true
    ]
    ask cursor [set path? true]
    set cursor [owner] of cursor
  ]
  set switch-off true                                     
end