Map Search

Map Search preview image

1 collaborator

Default-person Sebastian Dixon (Author)

Tags

(This model has yet to be categorized with any tags)
Visible to everyone | Changeable by everyone
Model was written in NetLogo 6.3.0 • Viewed 78 times • Downloaded 6 times • Run 0 times
Download the 'Map Search' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


Info tab cannot be displayed because of an encoding error

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

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 

There are 2 versions of this model.

Uploaded by When Description Download
Sebastian Dixon about 1 year ago Info Download this version
Sebastian Dixon about 1 year ago Initial upload Download this version

Attached files

File Type Description Last updated
Map Search.png preview Preview for 'Map Search' about 1 year ago, by Sebastian Dixon Download

This model does not have any ancestors.

This model does not have any descendants.