a-star_2009


Information

Created with NetLogo version NetLogo 4.0.4
Running with NetLogoLite.jar version 404.



Procedures

NetLogo Version: NetLogo 4.0.4

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
]

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 ]

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, may not be the current patch
  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 
  heuristic ;; heuristic-mode used by this bot
]


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
  maze-border-color      ;; color of maze-border
  maze-curviness         ;; probability that maza will choose a non-straight ahead path
  maze-timeout
]  

to startup
   setup
end
   
to setup
   ca
   
   ;;
   ;; Initialize the color variables
   ;;
   
   set obstacle-color blue
   set border-color pink
   set space-color black
   let bread-crumb-color red
   
   
   ;;
   ;; define the start and target patches
   ;; (for this demo, they are fixed, but you they could be dynamic
   ;;
   
   let setup-start patch (min-pxcor + 2) ( min-pycor + 2 )
   let setup-target patch (max-pxcor - 2) ( max-pycor - 2 )
   
   ;;
   ;; Setup the search space, based on the selected senario
   ;;

   ;;
   ;; A completely blank field
   ;;
   
   if senario = "blank" 
   [ fill-patches space-color
     do-terrain
     border
   ]
  
   ;;
   ;; 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
     ;; make sure that there is at least a clearing around
     ;; the start and target patches--prevents needlessly creating
     ;; a large number of unpassable configurations
     clear-around setup-start
     clear-around setup-target
   ]
   
   ;;
   ;; A single path maze
   ;;
   
   if senario = "maze" 
   [ senario-maze maze-new setup-start obstacle-color bread-crumb-color space-color border-color straightness 1
   ]
   
   ;;
   ;; A maze with loops
   ;;
   
   if senario = "looped maze" 
   [ senario-maze-looped density maze-new setup-start obstacle-color bread-crumb-color space-color border-color straightness 1
   ]
   
   ;;
   ;; A random collection of circular regions that may overlap
   ;;
   
   if senario = "blobs" 
   [ fill-patches space-color
     do-terrain
     ask patch (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-nowrap ((world-width * .05) + random (world-width * .05))
         [ set pcolor obstacle-color ]
       ]
     ]
     ;ifelse terrain? 
     ;[ border-3 ]
     ;[ border-2 ]
     border
     clear-around setup-start
     clear-around setup-target
   ]
   
   ;;
   ;; A pair of bars, crossing the center
   ;;
   
   if senario = "bars"
   [ fill-patches space-color
     do-terrain
     ;; draw horizontal and vertical bars, to within 5 units of edges
     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
   ;;
   
   
   create-bot setup-start setup-target extract-heuristic
   
   set-default-shape indicators "indicator"
   ask setup-start
   [ sprout-indicators 1
     [ set color orange 
       set size 4 
       set heading 180
     ]
   ]
   ask setup-target
   [ sprout-indicators 1
     [ set color orange 
       set size 4 
       set heading 0
     ]
   ]
 
end

to go
   ask bots
   [ go-bot 
     ifelse is-turtle? path-end
     [ show-path-nodes get-path yellow
     ]
     [ ;if show-path-in-progress?
       ;[ ask a*nodes with [ owner = myself and color != magenta ]
       ;  [ set color magenta ]
       ;  show-path-nodes get-path white
       ; ]
     ]
   ]
   if show-path-in-progress? [ tick ]
   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." ] ]
     ]
     tick
     stop
   ]
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 = 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 fill-patches [ #color ]
   ask patches [ set pcolor #color ]
end  

to maze-border
   ask patches with [ pxcor = min-pxcor or pxcor = max-pxcor or pycor = min-pycor or pycor = max-pycor ]
   [ set pcolor [ maze-border-color ] of myself ]
end

to maze-field
   ask patches with [ pxcor > min-pxcor and pxcor < max-pxcor and pycor > min-pycor and pycor < max-pycor ]
   [ set pcolor [ maze-wall-color ] of myself ]
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 senario-maze [ #maze ]
     ;; takes a maze object, generates a maze using that object
     maze #maze
end

to senario-maze-looped [ #density #maze ]
     ;; capture color info from maze
     let #wall [maze-wall-color] of #maze
     let #path [maze-path-color] of #maze
     
     ;; make a standard maze using the maze object
     senario-maze #maze
     
     ;; punch holes in the maze walls at random to create loops
     ;; depends on the maze starting on an even patch,
     ;; so can assume that any patch with both coords odd
     ;; is definitely a wall (obstacle) patch
     ask n-of (2 * #density) (patches with [ pcolor = #wall and pxcor mod 2 != pycor mod 2 ])
     [ set pcolor #path ]  
end


to-report maze-new [ #start #wall #crumb #path #border #curve #timeout ]
   let me nobody
   ask #start [ sprout-maza 1
   [ set me self
     set maze-wall-color #wall
     set maze-breadcrumb-color #crumb
     set maze-path-color #path
     set maze-border-color #border
     set maze-curviness #curve
     set maze-timeout #timeout
   ] ]
   report me
end
  
to maze [ #maze ]
   ;; given a maze turtle, create a single path maze in the field,
   ;;
   ask #maze
   [ 
     maze-border
     maze-field
     let #timeout timer + maze-timeout
     set pcolor maze-breadcrumb-color
     ;; timeout prevents possibility that an infinite loop may occur
     ;; (which may not even be possible with this algorithm...
     ;; each call to maze-drawing carves out or backtracks the maze path
     ;; this is a reporter with special effects, returns TRUE when there
     ;; is no more maze to be carved.
     while [ maze-drawing and timer < #timeout ]
     [  ]
     ;; mazum die when they are through carving a maze
     die
   ]
end

to-report maze-drawing
   ;; a maze can make a 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!
   ;; essentially uses the patches themselves to remember the path and the path-so-far
   ;;
   ;; assume no path from here
   let path nobody
   ;; candidates for the next step 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 ]
   if-else any? candidates 
   [ ;;if there are any unexplored paths, select one of them
     
     ;; which path is the straight-ahead path?
     let straight-patch patch-ahead 2 ; -at (dx * 2) (dy * 2)
     
     ;; either co straight (if curve test fails or straight is only choice)
     ;; or turn left or right (if possible)
     ifelse member? straight-patch  candidates and (count candidates = 1 or random 100 < maze-curviness )
     [ set path straight-patch] 
     [ set path one-of candidates with [ self != straight-patch ] ]
     ;; point to it
     face-nowrap path
     ;; jump to it, in two steps, two draw a path from here to that patch
     ;; (note that jump is 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 carved (open) 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
     [ ;; there is a breadcrumb to retrace. trace it.
       set path one-of candidates
       face-nowrap path
       repeat 2 [ set pcolor maze-path-color jump 1 ]
       
       report true
     ]
     [ ;; we are finally back at the beginning
       ;; carve out the starting point, and we are done
       set pcolor maze-path-color
       report false
     ]
   ]
   ;; avoid coordinate creep
   ;; center maza in the patch
   ;; 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
   let n path-end
   if not is-turtle? n
   [ set n current ]
   if not is-turtle? n
   [ stop ]
   
   let p (list n )
   while [ [location] of n != start ]
   [ set n [parent] of n
     set p fput n p
   ]
   report p
end      

to show-path-nodes [ p hue ]
   ask (turtle-set 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 #heuristic ]
   ;;
   ;; 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...
   ;;  
   create-bots 1
   [ 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 start [pycor] of start
     set shape "bot"
     set done? false
     set current nobody
     set o-current self  
     set child nobody
     set heuristic #heuristic
     expand-into self 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
       ifelse location = [ target ] of owner 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 color green
         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 = [ target ] of owner
  [ 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 ] of owner = 0  ;; euclidian distance to target
   [ set result distance-nowrap [ target ] of owner ]
   
   if [ heuristic ] of owner = 1 ;; manhattan distance
   [ let xdiff abs(pxcor - [pxcor] of [ target ] of owner)
     let ydiff abs(pycor - [pycor] of [ target ] of owner)
     set result ( xdiff + ydiff )
   ]

  if [ heuristic ] of owner = 2 ;; diagonal distance
   [ 
   
     let D  1
     let D2 1.414214
     let xdiff abs(pxcor - [pxcor] of [ target ] of owner)
     let ydiff abs(pycor - [pycor] of [ target ] of owner)
     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 ] of owner = 3 ;; diagonal distance + tie-breaker
   [ 
   
     let D  1
     let D2 1.414214
     let xdiff abs(pxcor - [ [pxcor] of target ] of owner)
     let ydiff abs(pycor - [ [pycor] of target ] of owner)
     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 ] of owner = 4  ;; euclidian distance to target with tie-breaker
   [ set result distance-nowrap [ target ] of owner 
     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
       
       if not same-patch location [ target ] of owner
       [ 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-report extract-heuristic
   report first choose-heuristic
end
       
to reset-bots
   ask a*nodes [ die ]
   ask bots [ die ]
   let setup-start patch (min-pxcor + 2) ( min-pycor + 2 )
   let setup-target patch (max-pxcor - 2) ( max-pycor - 2 )
   create-bot setup-start setup-target extract-heuristic
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. 

 
   

                    


Download Link

View or download the complete model file (to download: right-click, save-link-as):
-- Download a-star_2009 --