;;;; SUMMARY
;; A framework for using the famous path-finding algorithm
;;;; COPYRIGHT
;;NetLogo A* implementation Copyright (C) 2006
;;James P. Steiner, www.turtlezero.com, Used with permission." 
;;
;;
;;
globals 
[ ticks          ;; model time counter. not essential to a*
  obstacle-color ;; color of obstacles--see information about this
  space-color    ;; color of open space
  border-color   ;; color of the world border  
  path-end    
  path-found?    ;;true if has been found
  food-item      
  setup-start    ;;Nest location
  setup-target   ;;Food source location
  random-move    ;;Ants move randomly
  max-time       ;;pxcor+pycor  
  once?          ;;Initial position for nest and food 
  second?        ;;Second position for nest and food
  time           ;;Keeps track of the simulation time 
  done-one?      ;;Variable used to change nest and food position
]

breed [ bots bot ]       ;; bots use a*nodes to search the space
breed [ a*nodes a*node ] ;; each a*node occupies a place on the grid, contains the cost to get there
breed [ maza mazum ]     ;; a mazum is used to draw mazes.
breed [ indicators indicator ] ;;Nest and food source 
breed [path-finder-ants path-finder-ant] ;;Path finder ant finds path only no forage
breed [ants ant] ;;Worker ants forage 

ants-own [
  carrying-food?  ;true if ant is carrying food
  initial-location  ;Initial location is random within the world avoiding boundaries and obstacles
  time-since-reached-nest ; time passed since the ant reached nest
  time-since-reached-food ;time passed since the ant reached food
]

path-finder-ants-own
[
 path-list ;;List containing the patches from start to target or nest to food source
 moving-to-food? ;; true when ant is searching for food
 moving-to-home? ;; true when ant is carrying food and searching for home or nest
 food-pher-path-ant ;; Food pheromones dropped by path finding ant
 home-pher-path-ant ;; Home pheromones dropped by path finding ant
]

a*nodes-own
[ owner  ;; the bot that owns this node
  parent ;; the node that is the parent (that comes earlier in the path) of this node
  child  ;; the node that is the child (comes later in the path) of this node (not standard a*)
  g-score  ;; stores the cummulative cost of arriving at this point from the start
  h-score  ;; stores the estimated cost of getting from this point to the goal/target
  f-score  ;; the sum of g and h
  location ;; the patch that contains this node (duplicates "patch-here" when the node is on the path, but can be used in an -of expression, unlike patch-here)
  closed?  ;; node are open (0), or closed (1). Nodes start out open
  ;target   ;; copy of the PATCH that is the target patch
  ;start    ;; copy of the PATCH that is the start patch
  on-path? ;; is this node on the final route (or route-so-far, if needed) of the path to the target
]

bots-own
[ ;start     ;; the patch that the search starts from
  ;target    ;; the patch that is the goal / target of the search
  owner     ;; the owner of the search---always the bot itself... exists so it can be inherited by the a*nodes
  child     ;; the child of this bot is the first a*node of the path.. the a*node on the start
  g-score   ;; the bots own g-score is 0, unless the bot moves along its own path... then it might change...
  ;path-end  ;; the a*node at the end of the path... is nobody until the goal/target is reached. the path-end node is the only node that can construct the entire path back to the start
  done?     ;; boolean that indicates the search is over--may mean that no path can be found
  current   ;; the current a*node being examined or expanding the search
  o-current ;; the node that was previously current
  d-mode    ;; directions mode, either 4 or 8 
]


maza-own
[ maze-wall-color        ;; color of maze walls--also color of unexplorred (not carved) paths
  maze-breadcrumb-color ;; color of bread-crumb trail, used to backtrack
  maze-path-color        ;; final color of carved-out paths in the maze
]  

patches-own
[
 elevation
 food? ; true if patch is food source
 nest? ; true if patch is nest
 home-scent ; home pheromone 
 food-scent ; food pheromone 
]

to make-movie

  ;; prompt user for movie location
  user-message "First, save your new movie file (choose a name ending with .mov)"
  let path user-new-file
  if not is-string? path [ stop ]  ;; stop if user canceled

  ;; run the model
  
  setup
  movie-start path
  movie-grab-view
  while [ food-item < 50 ]
    [ go
      movie-grab-view ]

  ;; export the movie
  movie-close
  user-message (word "Exported movie to " path)
end



to startup
   setup
end
  
to setup
   ca   
   ;; Initialize the color variables
   set random-move [0 45 90 135 -180 -135 -90 -45]   ;;When ant wants to move random this list helps to find a random heading
   set obstacle-color blue ;;Color of obstacles
   set border-color pink ;;Color of Border
   set space-color black ;;Free space color     
   
   ;set setup-start patch (min-pxcor + 2) ( min-pycor + 2 )
   ;set setup-target patch (max-pxcor - 2) ( max-pycor - 2 )
   
   ;setup-start-target patch 16 16 patch -16 -16
   ;set max-time max-pxcor + max-pycor  ;;This value can be changed. I am yet to find an optimum value for this  
    set max-time 100
   ;;
   ;; Setup the search space, based on the selected senario
   ;;
   
   ;;
   ;; A Random scattering of obstaces
   ;;
   
   if senario = "random" ;; random scattering of patches
   [ do-terrain
     ask patches [ if random 100 < density [ set pcolor obstacle-color ] ]
     border
     clear-around patch (max-pxcor - 1) (max-pycor - 1)
     clear-around patch (-(max-pxcor - 1)) (-(max-pycor - 1))
     clear-around patch (max-pxcor - 1) (-(max-pycor - 1))
     clear-around patch (-( max-pxcor - 1))  (max-pycor - 1)
     border
   ]
   
   ;;
   ;; A single path maze
   ;;
   
   ;if senario = "maze" 
   ;[ ask patches [ set pcolor obstacle-color ]
   ;  border
   ;  maze setup-start obstacle-color red space-color
   ;]
   ;;
   ;; A maze with loops
   ;;
   
   ;if senario = "looped maze" 
   ;[ ask patches [ set pcolor obstacle-color ]
   ;  border
   ;  maze setup-start obstacle-color red space-color
   ;  ask n-of (2 * density) (patches with [  pxcor mod 2 != pycor mod 2 and pcolor = obstacle-color ]) [ set pcolor space-color ]  
   ;]
   
   ;;
   ;; A random collection of overlapping circular regions
   ;;
   
   if senario = "blobs" 
   [ ask patches [ set pcolor space-color ]
     do-terrain
     ask patch-at (min-pxcor + world-width * .5) (min-pycor + world-height * .55)
     [ ask n-of (density * .8) (patches in-radius (world-width * .5))
       [ ask patches in-radius-no-wrap ((world-width * .05) + random (world-width * .05))
         [ set pcolor obstacle-color ]
       ]
     ]
     ;ifelse terrain? 
     ;[ border-3 ]
     ;[ border-2 ]
     clear-around patch (max-pxcor - 1) (max-pycor - 1)
     clear-around patch (-(max-pxcor - 1)) (-(max-pycor - 1))
     clear-around patch (max-pxcor - 1) (-(max-pycor - 1))
     clear-around patch (-( max-pxcor - 1))  (max-pycor - 1)
     border
     ;clear-around setup-start
     ;clear-around setup-target
   ]
   
   ;;
   ;; A completely blank field
   ;;
   
   if senario = "blank" 
   [ ask patches [ set pcolor space-color ]
     do-terrain
     border
   ]
   
   ;;
   ;; A pair of bars, crossing the center
   ;;
   
   if senario = "bars"
   [ ask patches [ set pcolor space-color ]
     do-terrain
     ask patches with [ pxcor = 0 or pycor = 0 and abs pxcor + 5 < max-pxcor and abs pycor + 5 < max-pycor ]
     [ set pcolor obstacle-color ]
     ask patches with [ (    pxcor = int ( min-pxcor + world-width * .25 )
                          or pxcor = int ( max-pxcor - world-width * .25 )
                        )   
                         and 
                       ( pycor > max-pycor - (world-height * .33) 
                         or pycor < min-pycor + (world-height * .33)
                       )
                      ]
     [ set pcolor obstacle-color ]
     border 
   ]
   
   ;;
   ;; Create the search bot with the start and target previously selected
   ;;
   
   setup-ants ;;sets up the worker ants
   
   set path-found? false 
   
   set food-item 0   
   
   
    
  
  set once? true  ;;To go into the loop which sets the initial position of nest and food
   
  set second? false  ;;To go into the loop which sets the second position of nest and food
  
  ;set done-one? false 
  
end

to setup-start-target [start1 target1] ;;Sets up the nest and food source
  
  set setup-start start1 ;;nest
  set setup-target target1 ;;food source
  set-default-shape indicators "indicator"
   ask setup-start
   [ sprout-indicators 1
     [ set color orange 
       set size 1 
       set heading 180
       set plabel "Nest"
     ]
   ]
   ask setup-target
   [ sprout-indicators 1
     [ set color orange 
       set size 1 
       set heading 0
       set plabel "Food"
     ]
   ]
   create-bot setup-start setup-target 
  
end

to setup-path-finder-ant
   cct-path-finder-ants path-finding-ant-number [ 
     set shape "default" set size 1
     setxy pxcor-of setup-start pycor-of setup-start ;;set the initial poistion to the nest
     set moving-to-food? true ;;Initially the ant needs to find food source
     set moving-to-home? false ;;Initially the ant is at the food source
     set color brown 
   ]
end 

to setup-ants
  ;set-default-shape turtles "arrow"
  create-ants Ant-number 
  ask ants [
    ;set hidden? true
    set shape "bug"
    set size 1
    set color red ;;Initially all ants are red
    set carrying-food? false ; initially no ant carries food
    set heading 0 ; this could be set to random??
    ;setxy random-pxcor random-pycor ;placing the ant at the nest experimental purposes....
    set initial-location get-random-patch ;;Assigns a random patch to the ant initially
    setxy pxcor-of initial-location pycor-of initial-location 
    set time-since-reached-nest 0
    set time-since-reached-food 0
    ;setxy pxcor-of start pycor-of start
    ;setxy -2 -2
    ;set age 0
  ]  
end  

to-report get-random-patch ;;report a random position for the ants to start with
  let random-patch patch random-pxcor random-pycor
  loop [
    ifelse pcolor-of random-patch = space-color [report random-patch] ;; if the random patch selected is not a free space
    [set random-patch patch round random-pxcor round random-pycor ]   ;; Then find another random patch
  ]   ;; loop till a random patch which is a free space is found
     
end

to go  
  ;if done-one? [       
  ;    setup      
  ; ]   
  ;if time = 5000 [show food-item set done-one? true ]
  change-start-target ;;Change food and nest positions at target-change-rate     
  set time time + 1 ;;Increment simulation time
    
  diffuse-scent ;; diffuse home and nest pheromones
  
  ;ask patches [if plabel = "Nest" [set home-scent 1000] ] ;;This acts as homing signal for ants to return to nest
 
  ask patches [ if pcolor = space-color [evaporate ] ] ;; slowly evaporate the chemical
  
  ;if time mod 3 = 0 [ask ants [ go-ants ] ];; Slow down the ants so that path finding takes place faster
  ask ants [ go-ants ]
  ;do-plots
   ask path-finder-ants [ if not path-found? [set path-list find-path ] ;;Path finding ant calls the find-path
                                                                       ;;procedure
   if path-found? and moving-to-food? [ move-to-food ]  ;;If path has been found and located at nest then move to food source
   
   if path-found? and moving-to-home? [ move-to-home ]  ;;If path has been found and located at food source then move to nest    
  ]     
  ;display  
end

to go-ants ;; main function. this is an infinite function
  if is-ant? self[  
  ifelse carrying-food? 
    [return-to-nest ] ;; if ant is carrying food it returns to the nest
 
    [  find-food ]   ;; if ant is not carrying food it finds food
  ]  
end

to find-food
  let next-food-patch nobody
  ;set time-since-reached-nest time-since-reached-nest + 1
  
  if plabel-of patch-here = "Nest" [ ;; if turtle is located at nest    
    if ( (max-food-scent get-forward-neigh-list) != nobody )[ set heading get-heading max-food-scent get-forward-neigh-list ]      
    ]
    
  set next-food-patch select-location get-forward-neigh-list true ;;sets next patch to max forward neigh home scent
  if next-food-patch = nobody [ ;;if none forward neighbors
    set next-food-patch select-location get-loc-neigh-list false ;;set next patch to max location neigh food scent
    ]
  if next-food-patch != nobody [ ;;if there exists a patch to move to
    drop-home-pheromones    ;; drop home pheromones
    set heading get-heading next-food-patch ;; set tbe orientation of the turtle to next patch
    ]
      ;ask next-food-patch [set pcolor pink - 10 ]
  ifelse (count ants-on patch-at-heading-and-distance heading 1) < 10    
    [ move heading ];; move to the next patch
    [ 
     set heading item random length random-move random-move
     set next-food-patch patch-at-heading-and-distance heading 1
     if (next-food-patch != nobody) [
       if (pcolor-of next-food-patch = space-color) and (count ants-on next-food-patch < 10) [
         move heading 
       ]  
     ]   
    ]
    ;if time-since-reached-nest > max-time [ set conformance 0.95 ]
  
    if plabel-of patch-here = "Food" [ ;;if turtle located at food source
      ;pick food item
      set carrying-food? true ;; set carrying-food? to true 
      set color brown   
      set time-since-reached-food 0   
      ;set conformance 0
      ]     
      
             
end

to return-to-nest  
  let next-nest-patch nobody
  
  ;set time-since-reached-food time-since-reached-food + 1 ;;Ant has found food so keep incrementing time-since-reached-food
  ;if time-since-reached-food > max-time [set conformance 0.95 ]
  if plabel-of patch-here = "Food"  [   ;;If ant is located at food source
    if ((max-home-scent get-forward-neigh-list) != nobody) [set heading get-heading max-home-scent get-forward-neigh-list]
    ]
  
  set next-nest-patch max-home-scent get-forward-neigh-list ;;sets next patch to max forward neigh home scent
  if next-nest-patch = nobody [ set next-nest-patch max-home-scent get-loc-neigh-list ] ;;if no forward neighbors then take loc neighbors
    ifelse next-nest-patch != nobody [;;if there exists a neighbor patch to move to
      drop-food-pheromones 
      
      set heading get-heading next-nest-patch
      ifelse (count ants-on patch-at-heading-and-distance heading 1) < 10    
       [ move heading ];; move to the next patch
       [ 
         set heading item random length random-move random-move
         set next-nest-patch patch-at-heading-and-distance heading 1
         if (next-nest-patch != nobody) [
           if (pcolor-of next-nest-patch = space-color) and (count ants-on next-nest-patch < 10) [
             move heading 
           ]   
         ]  
       ]
    ]   
       
    [
      set heading item random length random-move random-move
      set next-nest-patch patch-at-heading-and-distance heading 1
      if (next-nest-patch != nobody) [
        if (pcolor-of next-nest-patch = space-color) and (count ants-on next-nest-patch < 10) [
          move heading 
        ]   
      ]  
    ]
  
       
  if plabel-of patch-here = "Nest" [;;Ant has reached the nest
    drop-home-pheromones 
    set carrying-food? false 
    set color pink
    set food-item food-item + 1  
    set time-since-reached-nest 0 ;;since ant has reached nest reset time-since-reached-nest
    ;set conformance 0.0
    ]
    
end

to drop-home-pheromones
  let maxh 0
  let desh 0
  let dh 0
  ifelse plabel-of patch-here = "Nest" [;;if located at nest drop max home-scent 1000
    ask self [ set home-scent 1000 ]
    ] 
    [
    if not empty? get-all-neigh-list [
    set maxh home-scent-of (max-home-scent get-all-neigh-list)
    ]    
    set desh maxh - 2
    set dh desh - home-scent-of patch-here
    if dh > 0 [
      ask patch-here [ set home-scent dh ]
      ]
    ]   ;show dh   
end

to drop-food-pheromones
  let maxh 0
  let desh 0
  let dh 0
  ifelse plabel-of patch-here = "Food" [;;if located at Food drop max food-scent 1000
    ask self [ set food-scent 1000 ]
    ] 
    [
    if not empty? get-all-neigh-list [
    set maxh food-scent-of (max-food-scent get-all-neigh-list)
    ]
    ;ask max-food-scent get-all-neigh-list [set pcolor red]
    set desh maxh - 2
    set dh desh - food-scent-of patch-here
    if dh > 0 [
      ask patch-here [ set food-scent dh ]
      ]
    ]   ;show dh
   
end

to-report select-location [loc-set forward?]
   ifelse empty? loc-set [ report nobody ] ;;if the loc-set is empty then return nobody 
  [ ;;the following is not what the paper suggests. The paper actually suggests to choose
    ;;next patch based on a probablity formula which needs to be substituted here
    
    let randval random-float 1
    ;show randval
    
    ifelse forward? 
     [
      ifelse randval <= conformance
      [
        report max-food-scent get-forward-neigh-list 
      ]
      [
        report item random length get-forward-neigh-list get-forward-neigh-list
       ]
    
     ]
     [
         ifelse randval <= conformance
         [
          report max-food-scent get-loc-neigh-list
         ]
         [
            report item random length get-loc-neigh-list get-loc-neigh-list
         ]
     ] 
  ] 
end

to-report max-food-scent [neigh-list]
  let max-food-pher 0
  let max-food-patch nobody
  
  ifelse empty? neigh-list [ report nobody ]
  [
    set neigh-list shuffle neigh-list
    set max-food-pher food-scent-of first neigh-list
    foreach neigh-list [
      ask ? [
        if food-scent-of ? > max-food-pher [
          set max-food-pher food-scent-of ?
        ];;end of if
      ];;end of ask
    ];;end of for
  ];;end of outer if
  
  foreach neigh-list [
    ask ? [
      if food-scent-of ? = max-food-pher [
        set max-food-patch ?
        ;set pcolor pink - 10
        ;show "inside max-loc-food-scent"        
        ;set plabel "Next patch"        
        ]
     ] 
    ]   
        ;ask next-patch [ set pcolor pink - 10 ]
    report max-food-patch
end

to-report max-home-scent [neigh-list]
  let max-home-pher 0
  let max-home-patch nobody
  
  ifelse empty? neigh-list  [ report nobody ]
  [
    set neigh-list shuffle neigh-list
    set max-home-pher home-scent-of first neigh-list
    foreach neigh-list [
      ask ? [
        if home-scent-of ? > max-home-pher [
        set max-home-pher home-scent-of ?
        ]                
      ];;end of ask
    ];;end of foreach
  ];;end of if  

        
  foreach neigh-list [
    ask ? [
      if home-scent-of ? = max-home-pher [        
        set max-home-patch ?        
        ;set plabel "Next patch"  
        ;set pcolor pink - 10         
        ]
     ] 
    ]   
    ;ask next-patch [ set pcolor pink - 10 ]
    report max-home-patch      
end


to move [angle]
  set angle abs angle
  ;if angle = 0 [ fd 1 ]
  ifelse angle mod 10 = 0 [ fd 1 ]
  [fd 1.414]
  ;display
end

to-report get-forward-neigh-list
  let list1 []
  let temp-patch1 nobody
  let x -45
  
  repeat 3 
  [;show "hi"
   
  set temp-patch1 patch-at-heading-and-distance (heading + x) 1
  if (temp-patch1 != nobody) and pcolor-of temp-patch1 = space-color and (count ants-at pxcor-of temp-patch1 pxcor-of temp-patch1 < 10) [
    set list1 lput temp-patch1 list1   
    ]
    set x x + 45
  ]    
  report list1
end

to-report get-all-neigh-list
  let listall []
  let temp-patch-all nobody
  let x -180
  
  repeat 8
  [ 
  set temp-patch-all patch-at-heading-and-distance (heading + x) 1
  if (temp-patch-all != nobody) and pcolor-of temp-patch-all = space-color and (count ants-at pxcor-of temp-patch-all pycor-of temp-patch-all < 10) [
    set listall lput temp-patch-all listall  
  ]
  set x x + 45 
  ]  
  report listall
end

to-report  get-loc-neigh-list
  let list2 []
  let temp-patch2 nobody
  set temp-patch2 patch-at-heading-and-distance (heading + 90) 1
  if (temp-patch2 != nobody) and pcolor-of temp-patch2 = space-color and (count ants-at pxcor-of temp-patch2 pycor-of temp-patch2 < 10) [ set list2 lput temp-patch2 list2 ]
  set temp-patch2 patch-at-heading-and-distance (heading - 90) 1 
  if (temp-patch2 != nobody) and pcolor-of temp-patch2 = space-color and (count ants-at pxcor-of temp-patch2 pycor-of temp-patch2) < 10 [ set list2 lput temp-patch2 list2 ]
  set temp-patch2 patch-at-heading-and-distance (heading + 135) 1 
  if (temp-patch2 != nobody) and pcolor-of temp-patch2 = space-color and (count ants-at pxcor-of temp-patch2 pycor-of temp-patch2) < 10 [ set list2 lput temp-patch2 list2 ]
  set temp-patch2 patch-at-heading-and-distance (heading - 135) 1 
  if (temp-patch2 != nobody) and pcolor-of temp-patch2 = space-color and (count ants-at pxcor-of temp-patch2 pycor-of temp-patch2) < 10 [ set list2 lput temp-patch2 list2 ]
  set temp-patch2 patch-at-heading-and-distance (heading + 180 ) 1 
  if (temp-patch2 != nobody) and pcolor-of temp-patch2 = space-color and (count ants-at pxcor-of temp-patch2 pycor-of temp-patch2) < 10 [ set list2 lput temp-patch2 list2 ]

  report list2
end

to-report get-heading [patch1]
  let x -180
  let y 0
  loop [    
    if patch1 = patch-at-heading-and-distance x 1 [ report x ]
    set x x + 45
    set y y + 1
    if y > 8 [ report random 360 ]
    ]  
end

to do-plots
  set-current-plot "Food At Nest"
  plot food-item 
end



to diffuse-scent
 ask patches [if pcolor != space-color [ set home-scent 0 set food-scent 0 ] ]
 diffuse home-scent (diffusion-rate / 100) ;;not very clear as to what diffusion principle has been used in the 
 diffuse food-scent (diffusion-rate / 100) ;;previous paper....but I think this formula can be used 
 ask patches [if pcolor != space-color [ set home-scent 0 set food-scent 0 ] ]
end

to evaporate
  set home-scent (home-scent * (100 - evaporation-rate) / 100)  ;;slowly evaporate chemical
  set food-scent (food-scent * (100 - evaporation-rate) / 100)  ;;slowly evaporate chemical  
end

to move-to-food
  ;show "moving to food"
  ;let next-patch item 1 path-list
  if patch-here = setup-start[ set home-pher-path-ant 1000 set home-scent home-pher-path-ant]
  ;set plabel-color white
  ;set plabel home-scent
  
  let temp-list path-list 
  set temp-list but-first temp-list    
  
  foreach temp-list [ ;show next-patch show patch-at-heading-and-distance 45 1
      ;display
      if ? = patch-at-heading-and-distance 45 1 [ set heading 45 fd 1.414 ]  
      if ? = patch-at-heading-and-distance 0 1 [ set heading 0 fd 1 ]  
      if ? = patch-at-heading-and-distance -45 1 [ set heading -45 fd 1.414 ]  
      if ? = patch-at-heading-and-distance -90 1 [ set heading -90 fd 1 ] 
      if ? = patch-at-heading-and-distance -135 1 [ set heading -135 fd 1.414 ]   
      if ? = patch-at-heading-and-distance -180 1 [ set heading -180 fd 1 ] 
      if ? = patch-at-heading-and-distance 135 1 [ set heading 135 fd 1.414 ] 
      if ? = patch-at-heading-and-distance 90 1 [ set heading 90 fd 1 ] 
      ifelse (length temp-list = 1) [
        if round (distancexy pxcor-of setup-target pycor-of setup-target) = 0 [ 
         set moving-to-food? false
         set moving-to-home? true
         ;show "reached target"        
         stop         
     ]
      ]
      [ set temp-list but-first temp-list 
        set home-pher-path-ant home-pher-path-ant - 5
        set home-scent home-pher-path-ant
        ;set plabel home-scent
      ]      
    ] 
  
end

to move-to-home
  ;show "moving to home"
  if patch-here = setup-target [ set food-pher-path-ant 1000 set food-scent food-pher-path-ant]
  let temp-list path-list
  set temp-list reverse path-list
  set temp-list but-first temp-list
  foreach temp-list [ ;show next-patch show patch-at-heading-and-distance 45 1
      if ? = patch-at-heading-and-distance 45 1 [ set heading 45 fd 1.414 ]  
      if ? = patch-at-heading-and-distance 0 1 [ set heading 0 fd 1 ]  
      if ? = patch-at-heading-and-distance -45 1 [ set heading -45 fd 1.414 ]  
      if ? = patch-at-heading-and-distance -90 1 [ set heading -90 fd 1 ] 
      if ? = patch-at-heading-and-distance -135 1 [ set heading -135 fd 1.414 ]   
      if ? = patch-at-heading-and-distance -180 1 [ set heading -180 fd 1 ] 
      if ? = patch-at-heading-and-distance 135 1 [ set heading 135 fd 1.414 ] 
      if ? = patch-at-heading-and-distance 90 1 [ set heading 90 fd 1 ] 
      ifelse (length temp-list = 1) [
        if round (distancexy pxcor-of setup-start pycor-of setup-start) = 0 [
         set moving-to-home? false
         set moving-to-food? true
         ;show "reached home"
         stop         
        ]   
      ]
      [ 
       set temp-list but-first temp-list 
       set food-pher-path-ant food-pher-path-ant - 5
       set food-scent food-pher-path-ant
      ]
      ;display
    ] 
  
end

to colorpath
 foreach path-list [ask ? [set pcolor yellow ] ]
end

to-report find-path
set path-found? false
  ask bots
   [ go-bot 
     if is-turtle? path-end 
     [ 
     ;show-path-nodes get-path yellow
     
     set path-found? true
     
     ]
   ]  
   
   if not any? bots with [ done? = false ]
   [ ask bots
     [ ifelse is-turtle? path-end
       [ ask center-patch [ set plabel  "Path Solved." ] ]
       [ ask center-patch [  set plabel  "No Path." ] ]
     ]    
   ]
   
  ifelse path-found? [ report get-path ]
  [report nobody]
   
end  

to change-start-target ;;Changes the start and target patches at target change rate
  if once? and ( time mod target-change-rate = 0) [ 
    ask path-finder-ants [ die ]
    ask bots [ die ]
    ask a*nodes [ die ] 
    ask indicators [ die ]
    setup-start-target patch  (-(max-pxcor - 1)) (-(max-pycor - 1)) patch ((max-pxcor - 1)) ((max-pycor - 1))
    ;set conformance 0.0
    ;ask patch -19 -19  [set home-scent 1000]
    set path-found? false
   
    ask patch  ((max-pxcor - 1)) (-(max-pycor - 1)) [ set plabel ""]    
    ask patch  (-(max-pxcor - 1)) ((max-pycor - 1)) [ set plabel ""]
    
    ask center-patch [ 
      ifelse time = 0 [ set plabel "Initial Postion" ] 
        [ set plabel  "Target changed." ]
    ]    
    setup-path-finder-ant 
    set once? false
    set second? true
    ask patches [set home-scent 0 set food-scent 0]
    
    ;show "once"
    set time time + 1
    ]
  if second? and (time mod target-change-rate = 0 ) and (time != 0) [
     ask path-finder-ants [ die ]
     ask bots [ die ]
     ask a*nodes [ die ] 
     ask indicators [ die ]     
     setup-start-target patch  ((max-pxcor - 1)) (-(max-pycor - 1)) patch (-(max-pxcor - 1)) ((max-pycor - 1))
     ;ask patch 19 -19  [set home-scent 1000]
     set path-found? false
     
     ask patch  (-(max-pxcor - 1)) (-(max-pycor - 1)) [ set plabel ""]    
     ask patch  ((max-pxcor - 1)) ((max-pycor - 1)) [ set plabel ""]
     ask center-patch [ set plabel  "Target changed." ]
     setup-path-finder-ant 
     set second? false  
     set once? true   
     ask patches [set home-scent 0 set food-scent 0]
     ;set time time + 1
     ;show "second"
     ;set conformance 0.0
     ]

end


to go-bot
   ;;
   ;; when path-end is not nobody, that means the target has been reached.
   ;; and path-end contains the a*node that lies on the target.
   ;; path-end can then be used to trace the path back to the start
   ;;
   ;; when done? is true, that means that no more locations
   ;; need to be searched.
   ;; 
   ;; if path-end is nobody when done? is true, that means there is
   ;; NO path from the start to the target.
   ;;
   if path-end = nobody
     [ ;;
     ;; collect the nodes that are this bots nodes
       ;; (if netlogo had mutable lists, or mutable agentsets, this could be made faster!)
       ;;
       let my-nodes  a*nodes with [ owner = myself ]
       
       ;; 
       ;; are any of the nodes open?
       ;;
       ifelse any? my-nodes with [ closed? = 0 ]
       [ ;; 
         ;; yes. do the path search
         ;;
         set current a*build-path
         ;;
         ;; having done that, was the target found?
         ;;
         if location-of current = setup-target
         [ set path-end current 
           set done? true
         ]
       ]
       [ ;;
         ;; no more open nodes means no where left to search, so we are done.
         ;;
         set done? true
       ]
     ]
end

to border   
   ;;
   ;; colors the edge of the world to prevent searches and maze-making from leaking
   ;;
   ask patches with [ pxcor = min-pxcor or pxcor = max-pxcor or pycor = min-pycor or pycor = max-pycor ]
   [ set pcolor border-color ]
end   

to border-2
   ;;
   ;; creates open space along the border
   ;;
   ask patches with [     ( pxcor = ( min-pxcor + 1 ) or pxcor = ( max-pxcor - 1 ) )
                      or ( pycor = ( min-pycor + 1 ) or pycor = ( max-pycor - 1 ) )]
   [ set pcolor space-color
   ]
end   

to border-3
   ;;
   ;; creates a border of randomly "elevated" terrain just inside the border
   ;; 
   ask patches with [     ( pxcor = ( min-pxcor + 1 ) or pxcor = ( max-pxcor - 1 ) )
                      or ( pycor = ( min-pycor + 1 ) or pycor = ( max-pycor - 1 ) )]
   [ set pcolor 5 + random-float 5
   ]
end 

to do-terrain
 ;; 
 ;; puts elevation data in the world
 ;; black = minimum elevation
 ;; white = max-mum elevation
 ;;
 ;; when terrain? is on, path seeks best balance of shortness of path and lowness of elevation
 ;;
 if terrain?
         [ ask patches [ set pcolor 140 - ((distancexy-nowrap 0 0 ) / (.75 * world-width) * 140) ]
           repeat 3 [ diffuse pcolor .5 ]
           ask patches [ set pcolor scale-color gray pcolor 0 140 ]
           
         ]
end  

      
to clear-around [ agent ]
   ;;;
   ;;; clears obstacles from under and around the given agent
   ;;;
   ask agent [ ask neighbors [ set pcolor space-color ] set pcolor space-color ]
end

to maze [ start-location m-w-c m-bc-c m-p-c ]
   ;;
   ;; use a mazum turtle to create a single path maze in the field
   ;;
   ask start-location
   [ sprout-maza 1
     [ set maze-wall-color m-w-c
       set maze-breadcrumb-color m-bc-c
       set maze-path-color m-p-c
       let timeout timer + 1
       set pcolor maze-breadcrumb-color
       ;; timeout prevents possibility that an infinite loop may occur
       while [ maze-drawing and timer < timeout ]
       [  ]
       die
     ]
   ]
end

to-report maze-drawing
   ;; 
   ;; draw a maze by first drawing a path with a marker color, then backtracking with the space color
   ;; allows drawing of mazes iterively, rather than recursively, and without using a stack!
   ;;
   ;; assume no path from here
   let path nobody
   ;; candidates are previously unexplored paths (ie, still colored as obstacles
   let candidates (patches at-points [ [ -2 0][0 -2 ] [ 2 0 ][ 0 2] ]) with [ pcolor = maze-wall-color-of myself ]
   ifelse any? candidates 
   [ ;;if there are any unexplored paths, select one of them
     let straight-patch patch-ahead 2 ; -at (dx * 2) (dy * 2)
     ifelse member? straight-patch  candidates and (random 100 < density or count candidates = 1)
     [ set path straight-patch] 
     [ set path one-of candidates with [ self != straight-patch ] ]
     ;; point to it
     set heading towards-nowrap path
     ;; jump to it, in two steps, two draw a path from here to that patch
     ;; (note that jump first,then color, leaving starting patch color that it was!
     repeat 2 [ jump 1 set pcolor maze-breadcrumb-color ]
     
     ;; report that the maze-drawing still has some exploring to do!
     report true
   ]
   [ ;; if we are here, then there are no unexplored paths in the vicinity.
     ;; so, candidates are previously explored paths, that we have likely backed up to
     ;; or have just finished tracing (i.e. colored with the bread-crumb color
   
     set candidates (patches at-points [ [ -1 0][0 -1 ] [ 1 0 ][ 0 1] ]) with [ pcolor = maze-breadcrumb-color-of myself ]
     ifelse any? candidates
     [ set path one-of candidates
       set heading towards-nowrap path
       repeat 2 [ set pcolor maze-path-color jump 1 ]
       
       report true
     ]
     [ set pcolor space-color
       report false]
   ]
   setxy pxcor pycor
end
 
to-report same-patch [ a b ]
   ;;
   ;; reports true if both agent a and b, whether turtles or patches, are on the same patch
   ;;
   report (pxcor-of a = pxcor-of b and pycor-of a = pycor-of b )
end   

to highlight-path [ path-color ]
   ;;
   ;; recursive routine that colors the nodes, tracing back up through the node parents
   ;; until the start node is reached
   ;;
   set on-path? true
   set color path-color
   ;if color = yellow [ ifelse heading mod 90 = 0 [set shape "path" ] [ set shape "path-long" ] ]
   if is-turtle? parent
   [ set heading towards-nowrap parent
     ask parent
     [ 
     ;highlight-path path-color
     ]
   ]
   
end

to-report get-path
   ask a*nodes [set hidden? true ]
   let n path-end
   if not is-turtle? n
   [ set n current ]
   if not is-turtle? n
   [ stop ]
   
   let p (list location-of n )
   ;let p (list n )
   while [ location-of n != setup-start ]
   [ set n parent-of n
     set p fput location-of n p
     ;set p fput n p
   ]
   report p
end      

to show-path-nodes [ p hue ]
   ask __turtles-from-list p
   [ set color hue 
     if color = yellow [ ifelse heading mod 90 = 0 [set shape "path" ] [ set shape "path-long" ] ]
   ]  
    ;ask a*nodes with [ member? self p ] [ 
    ;set color hue 
    ;]
   ;display
   ;   foreach p
   ;   [ 
   ;     set color hue 
   ;     if color = yellow [ ifelse heading mod 90 = 0 [set shape "path" ] [ set shape "path-long" ] ]
   ;   ]
end
   
   
to color-path-patches [ p ]
   ;;
   ;; non-recursive routine that,
   ;; given the path-end, increments the pcolor of the patches covered by the path,
   ;; tracing back to the start
   ;;
   foreach p 
   [ if pcolor = 0 [ set pcolor 2 ]
     if pcolor < 9.5 [ set pcolor pcolor + .5 ]
   ]
end   
   

to create-bot [ starting-patch target-patch ]
   ;;
   ;; creates a search bot
   ;; and the first a*node for that bot.
   ;; so: a bot always has at least one a*node, and that first node is
   ;; the child of the bot
   ;; the first node, however, does not have any "parent"...
   ;; that is, its parent is always "nobody"
   ;; this is how a trace-back routine can know that it has reached
   ;; the begining of a path: when there is no more parents to trace-back to...
   ;;  
   cct-bots 1
   [ 
     set hidden? true ;;newly added
     set color gray
     ;set start starting-patch
     ;set target target-patch
     set owner self
     set path-end nobody
     set g-score 0
     setxy pxcor-of setup-start pycor-of setup-start
     set shape "bot"
     set done? false
     set current nobody
     set o-current self  
     set child nobody
     expand-into self setup-start
     ask child [ set closed? 0 
     ;set shape "node" 
     set parent nobody set on-path? true ]
   ]
end  

to expand-into [ parent-agent location-agent ]
   ;;
   ;; causes the given parent agent to 
   ;; expand into the given location (patch)
   ;; 
   ;; this means that nodes are created in the given patch, and the parent
   ;; of these nodes is the given parent agent.
   ;;
   ask parent-agent
   [ hatch-a*nodes 1
     [ set location location-agent
       setxy pxcor-of location pycor-of location
       ;; first thing--is this a dead end? if so, don't
       ;; bother to add it to any list... just die.
       let my-owner owner
       set hidden? true
       ifelse location = setup-target or any? neighbors with [ shade-of? pcolor space-color and not any? a*nodes-here with [ owner = my-owner ] ]
       [ set breed a*nodes
         set shape "node"
         set size 1.01
         set hidden? true ;; delete
         ;;set color green ;;?@
         ;set color space-color ;; delete
         set parent parent-agent
         set owner owner-of parent-agent
         set child-of parent-agent self
         set child nobody
          
       
       
         face parent
       
         ;; target is inherited
         set g-score calculate-g parent-agent 
         set h-score calculate-h
         set f-score calculate-f
         set closed? -1 ;; new... neither open or closed
         set on-path? false
       ]
       [ die ]
     ]
   ]
end   
    
to-report calculate-f 
  ;;
  ;; calculates the f score for this s*node
  ;;
  
  ifelse location = setup-target
  [ report -999999 ]
  [ report g-score + h-score  ]
end

to-report calculate-g [ candidate ] 
  ;;
  ;; calculates the g score relative to the candidate for this s*node
  ;;

   let g g-score-of candidate + distance-nowrap candidate
   if terrain? [ set g g + pcolor * 10]
   report g
end

to-report calculate-h
   let result 0 
   if heuristic = 0  ;; euclidian distance to target
   [ set result distance-nowrap setup-target ]
   
   if heuristic = 1 ;; manhattan distance
   [ let xdiff abs(pxcor - pxcor-of setup-target)
     let ydiff abs(pycor - pycor-of setup-target)
     set result ( xdiff + ydiff )
   ]

  if heuristic = 2 ;; diagonal distance
   [ 
   
     let D  1
     let D2 1.414214
     let xdiff abs(pxcor - pxcor-of setup-target)
     let ydiff abs(pycor - pycor-of setup-target)
     let h_diagonal min (list xdiff ydiff)
     let h_straight xdiff + ydiff
     set result D2 * h_diagonal + D * ( h_straight - 2 * h_diagonal )
   ]
   
   if heuristic = 3 ;; diagonal distance + tie-breaker
   [ 
   
     let D  1
     let D2 1.414214
     let xdiff abs(pxcor - pxcor-of setup-target)
     let ydiff abs(pycor - pycor-of setup-target)
     let h_diagonal min (list xdiff ydiff)
     let h_straight xdiff + ydiff
     set result D2 * h_diagonal + D * ( h_straight - 2 * h_diagonal )
     ;; tie-breaker: nudge H up by a small amount
     let h-scale (1 + (16 / directions / world-width * world-height))
     set result result * h-scale
   ]
   if heuristic = 4  ;; euclidian distance to target with tie-breaker
   [ set result distance-nowrap setup-target 
     let h-scale (1 + (16 / directions / world-width + world-height))
     set result result * h-scale
   ]
   report result
end

to-report a*build-path
   let o-c o-current
   set current min-one-of a*nodes with [ owner = myself and closed? = 0 ] [ f-score ] ; + distance-nowrap o-c ]
   set o-current current
   let cc current
   if is-turtle? cc
   [ ask cc
     [ set closed? 1
        ;set color magenta
        set hidden? true ;; delete
        set color space-color ;; delete
       if not same-patch location setup-target
       [ let me owner
         let paths nobody
         ifelse directions = 8
         [ set paths neighbors with [ shade-of? pcolor space-color ] ]
         [ set paths neighbors4 with [ shade-of? pcolor space-color ] ]
         
         let new-paths (paths with [ not any? a*nodes-here with [ owner = me ] ] )
         if any? new-paths [ ask  new-paths [ expand-into cc self ] ]
         
         set new-paths  (a*nodes-on paths ) with [ owner = me and closed? < 1 ]
         ; if any? new-paths [ set new-paths min-one-of new-paths [ f-score ] ]
         ask  new-paths
         [ ifelse closed? = 0 ;; already open
           [ ;; see if g from current is better than prior g
             let new-g calculate-g cc
             set f-score calculate-f
             if new-g < g-score
             [ ;; if it is, then change path to go from this point
               ;; set parent of this node to current
               set parent cc 
               set shape "node"
               face parent
               set child-of parent self
               set g-score new-g 
               set f-score calculate-f
             ]
           ]
           [ ;; must be new (not yet open, not previously closed.
             set closed? 0 ;; open it
               set parent cc 
           ]
         ]
       ]
     ]
   ]
   report current
end
       
       
to reset-bots
   ask a*nodes [ die ]
   ask bots [ die ]
   set setup-start patch (min-pxcor + 2) ( min-pycor + 2 )
   set setup-target patch (max-pxcor - 2) ( max-pycor - 2 )
   create-bot setup-start setup-target
end

to-report center-patch
   report patch (int (min-pxcor + world-width * .5)) (int (min-pycor + world-height * .5))    
end        
   ;;  1) Add the starting square (or node) to the open list.
   ;;  2) Repeat the following:
   ;;     a) Look for the lowest F cost square on the open list. We refer to this as the current square.
   ;;     b) Switch it to the closed list.
   ;;     c) For each of the 8 squares adjacent to this current square …
   ;;  
   ;;        * If it is not walkable or if it is on the closed list, ignore it. 
   ;;          Otherwise do the following.           
   ;;      * If it is on the open list already...
   ;;          Check to see if this path to that square is better,
   ;;          using G cost as the measure.
   ;;          A lower G cost means that this is a better path.
   ;;          If so, change the parent of the square to the current square,
   ;;          and recalculate the G and F scores of the square.
   ;;          If you are keeping your open list sorted by F score,
   ;;          you may need to resort the list to account for the change.
   ;;        * If it isn’t on the open list...
   ;;            Add it to the open list.
   ;;            Make the current square the parent of this square.
   ;;            Record the F, G, and H costs of the square. 
  ;;  
   ;;  d) Stop when you:
   ;;  
   ;;      * Add the target square to the closed list, in which case the path has been found (see note below), or
   ;;      * Fail to find the target square, and the open list is empty. In this case, there is no path.   
   ;;  
   ;;  3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path. 

 
   
@#$#@#$#@
GRAPHICS-WINDOW
131
10
629
529
30
30
5.0
1
20
1
1
1
0
0
0
1
-30
30
-30
30

CC-WINDOW
5
599
944
694
Command Center
0

BUTTON
9
174
64
207
NIL
setup
NIL
1
T
OBSERVER
T
NIL

BUTTON
68
174
123
207
go
go
T
1
T
OBSERVER
NIL
NIL

MONITOR
33
536
128
585
NIL
count a*nodes
3
1

SLIDER
8
60
100
93
density
density
0
100
10
1
1
NIL

BUTTON
68
211
123
244
go 1x
go
NIL
1
T
OBSERVER
T
NIL

CHOOSER
8
10
100
55
senario
senario
"blank" "bars" "blobs" "random"
2

SLIDER
9
98
101
131
heuristic
heuristic
0
4
3
1
1
NIL

SLIDER
8
134
100
167
directions
directions
4
8
4
4
1
NIL

SWITCH
14
445
117
478
terrain?
terrain?
1
1
-1000

MONITOR
847
451
935
500
nodes in path
count a*nodes with [ color = yellow ]
3
1

MONITOR
850
507
928
556
path-length
ifelse-value (any? bots) [value-from one-of bots [ g-score-of current ]] [""]
3
1

SLIDER
731
175
903
208
Ant-number
Ant-number
0
1000
115
1
1
NIL

SLIDER
731
308
903
341
diffusion-rate
diffusion-rate
0
100
2
1
1
NIL

SLIDER
732
264
904
297
evaporation-rate
evaporation-rate
0
100
99
1
1
NIL

SLIDER
733
357
905
390
conformance
conformance
0
1.0
0.9
0.05
1
NIL

PLOT
721
11
921
161
Food At Nest
NIL
NIL
0.0
10.0
0.0
10.0
true
false

SLIDER
731
212
903
245
path-finding-ant-number
path-finding-ant-number
0
1
1
1
1
NIL

BUTTON
12
307
109
340
NIL
make-movie
NIL
1
T
OBSERVER
T
NIL

SLIDER
651
420
823
453
target-change-rate
target-change-rate
200
1000
400
100
1
NIL

@#$#@#$#@
WHAT IS IT

This project was done in order to support our paper titled "Optimal Path Planning 
Applied to Ant Foraging". This interesting work takes a hybridised approach by 
combining a Biologically evolved technique such as Ant Foraging with a Mathematically
evolved search technique called the A* algorithm. Please check my website to download
the full paper. www.geocities.com/anandvincent78

This is not an attempt to reproduce the exact behaviour of Ant Colonies. We are more
interesting in using the Ants Biologically evolved techniques to create more efficient
robots. 

In this experiment there are 2 kinds of breeds. One is simply the 'Ant' breed and the 
other is the 'Path-Finding-Ant' breed. The Ants go about thier foraging with the help
of double pheromones. Food pheromones and Nest pheromones to create trails of food and
nest respectively. The Path-Finding-Ant goes about its task which is to use the A* algorithm to find an optimal path between Nest and food. Once it has found the path it 
continually traverses between the food and the nest dropping the appropriate pheromones. The Ant breed also drop pheromones. But since the Path-Finding-Ant is more
efficient it finds the path more quickly and this helps the other ants to find the path
quickly thereby increasing the efficiency of foraging. 

****Note****************************************************************************** 
The path finding ant cannot be seen in the simulations because it moves much faster than the other ants and updating the display to make it visible slows down
the simulation considerably.
****Note******************************************************************************

HOW TO USE IT

Click the setup button to reset the simulation. Click on scenario to change the scenarios. Set the 'path-finding-ant-number' to 0 if you want to see the foraging process without path finding. Setting it to 1 will enable to see the foraging process with path finding. 'target-change-rate' specifies the number of simulation time steps
at which the food source and nest change positions. 

Click the GO button to start the simulation. The ants are initially colored red. Once the Ants find food their color changes to brown. If an ant is sucessful in dropping the food at the nest its color changes to pink. 

Changing the "Ant Number" increases or decreases the number of ants in the simulation. 

Use the Evaporation slider and diffusion slider to change the rate of evaporation and diffusion. The present model seems to work better at lower rates of diffusion. The conformance slider should be ideally set to 0.95 which encourages the ants to explore.

THINGS TO NOTICE

With the Number of Path finding ants turned to zero, there is no path finding taking place which allows the ants to find a path using purely home and nest pheromones. The changes in the rate of evaporation and diffusion can be noticed here. But with path finding enabled(Setting Path-Finding-Ants-Number to 1) the rated of diffusion and evaporation do not actually make much of a difference.


CREDIT AND ACKNOWLEDGEMENTS
---------------------------
NetLogo A* implementation Copyright (C) 2006
James P. Steiner, www.turtlezero.com, Used with permission." 
@#$#@#$#@
default
true
0
Polygon -7500403 true true 150 5 40 250 150 205 260 250

link
true
0
Line -7500403 true 150 0 150 300

link direction
true
0
Line -7500403 true 150 150 30 225
Line -7500403 true 150 150 270 225

bot
true
6
Circle -13840069 true true 30 30 240

bug
true
0
Circle -7500403 true true 96 182 108
Circle -7500403 true true 110 127 80
Circle -7500403 true true 110 75 80
Line -7500403 true 150 100 80 30
Line -7500403 true 150 100 220 30

indicator
true
2
Polygon -955883 false true 150 75 210 15 285 90 225 150 285 210 210 285 150 225 90 285 15 210 75 150 15 90 90 15
Polygon -955883 false true 105 150 60 105 105 60 150 105 195 60 240 105 195 150 240 195 195 240 150 195 105 240 60 195
Polygon -955883 false true 135 150 105 120 120 105 150 135 180 105 195 120 165 150 195 180 180 195 150 165 120 195 105 180

node
true
6
Circle -13840069 true true 75 75 150
Polygon -13840069 true true 75 150 150 -150 225 150

path
true
6
Rectangle -13840069 true true 75 -75 225 225
Polygon -16777216 true false 75 195 105 195 150 135 195 195 225 195 150 90
Polygon -16777216 true false 75 60 105 60 150 0 195 60 225 60 150 -45

path-long
true
6
Rectangle -16777216 true false 75 -195 225 225
Polygon -13840069 true true 75 0 75 -195 225 -195 225 -60 150 -165 75 -60 105 -60 150 -120 195 -60 225 -60 225 60 150 -45 75 60 105 60 150 0 195 60 225 60 225 195 150 90 75 195 105 195 150 135 195 195 225 195 225 225 75 225

@#$#@#$#@
NetLogo 3.1.1
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@