Map Search

breed [searchers searcher]

globals [
  start-node
  finish-node
  number-edges
  notVisited
  a-total
]

turtles-own [
  dist
]

searchers-own [
  memory
  cost
  total-expected-cost
  localization
  active?
]

links-own [
  value
]

;--------------- SETUP ---------------

to setup
  clear-all
  setup-nodes
  setup-edges
  random-select
  ask links [ set color white ]
end 

to setup-nodes
  set-default-shape turtles "circle"
  create-turtles number-of-nodes [
    setxy (random-xcor * 0.95) (random-ycor * 0.95)
    set color blue
    set size .75
  ]
end 

to setup-edges
  set number-edges 0

  let num-links (average-node-degree * number-of-nodes) / 2
  while [count links < num-links ] [
    ask one-of turtles [
      let choice (min-one-of (other turtles with [not link-neighbor? myself])
                   [distance myself])
      if choice != nobody [
        let node-weight [distance myself] of choice
        create-link-with choice [set value round node-weight]
        set number-edges (number-edges + 1)
      ]
    ]
  ]

  repeat number-of-nodes [
    layout-spring turtles links 0.3 (world-width / (sqrt number-of-nodes) ) 10
  ]

  ask links [
    ifelse show-weights? [
      set label precision value 4
    ] [
      set label ""
    ]
  ]
end 

to random-select
  ask one-of turtles [
    set color green
    set start-node self
    set size 1.25
  ]
  ask one-of turtles [
    set color red
    set finish-node self
    set size 1.25
  ]
end 

;----------------- GO -----------------

to go-dijkstra
  dijkstra-search
end 

to dijkstra-search
  set notVisited turtles
  ask turtles [set dist 99999]
  ask start-node [ set dist 0 ]

  while [count notVisited > 0] [
    let current min-one-of notVisited [dist]
    set notVisited notVisited with [self != current]
    ask current [
      ask link-neighbors [
        let link-value ([value] of link-with current)
        let newDist ([dist] of current + link-value)
        if newDist < dist
        [set dist newDist]
      ]
    ]
  ]
end 

to go-astar
  set a-total 0
  let path (A* start-node finish-node)
  if path != false [highlight-path path]
end 

to-report A* [#Start #Goal]
  ask #Start [
    hatch-searchers 1 [
      set shape "circle"
      set color red
      set localization myself
      set memory (list localization)
      set cost 0
      set total-expected-cost cost + heuristic #Goal
      set active? true
    ]
  ]

  while [not any? searchers with [localization = #Goal] and any? searchers with [active?]] [
    ask min-one-of (searchers with [active?]) [total-expected-cost] [
      set active? false
      let this-searcher self
      let Lorig localization
      ask ([link-neighbors] of Lorig) [
        let connection link-with Lorig
        let c ([cost] of this-searcher) + [link-length] of connection
        if not any? searchers-in-loc with [cost < c] [
          hatch-searchers 1 [
            set shape "circle"
            set color red
            set localization myself
            set memory lput localization ([memory] of this-searcher)
            set cost c
            set total-expected-cost cost + heuristic #Goal
            set active? true
            ask other searchers-in-loc [die]
          ]
        ]
      ]
    ]
  ]

  let res false

  if any? searchers with [localization = #Goal] [
    let lucky-searcher one-of searchers with [localization = #Goal]
    set res [memory] of lucky-searcher
  ]
  ask searchers [die]
  report res
end 

to-report heuristic [#Goal]
  report [distance [localization] of myself] of #Goal
end 

to-report searchers-in-loc
  report searchers with [localization = myself]
end 

to-report highlight [x y]
  ask x [
    ask link-with y [set color yellow set thickness .4]
    set a-total a-total + [value] of link-with y
  ]
  report y
end 

to highlight-path [path]
  let a reduce highlight path
end