Netlogo - найти ближайшего агента на основе расстояния Манхэттена

Question

Я моделирую большие складские операции (см. Фото ниже).

Я реализовал вершину в каждом патче (зеленые точки) и связал их так, чтобы я мог вычислить кратчайший путь (используя алгоритм dijkstra) от каждой вершины ко всем остальным вершинам, хранящимся в таблице (словаре) каждой вершины. Этот процесс выполняется на этапе настройки и занимает довольно много времени. Затем желтые инвентарные ячейки (прямоугольник) выдадут запрос на выполнение задачи.

Автопогрузчик (некоторые на пути) предполагает оставаться на одной из вершин (узлов), когда он не занят. Когда получен запрос по требованию, он попросит текущую стоящую вершину (узел) получить начальный_узел и конечный_узел ячейки инвентаря, к которой он собирается. Затем вилочный погрузчик просит start_node получить кратчайший путь из своей таблицы, чтобы получить кратчайший путь (комбинацию узлов), и направиться к конечному узлу (желтая ячейка).

В настоящее время желтые ячейки просто случайным образом выбирают бесплатный погрузчик на складе. В качестве дальнейшего развития я хочу добавить функцию, которая позволяет желтой ячейке идентифицировать свободный грузовик, который находится ближе всего к нему, на основе фактического расстояния (а не евклидова расстояния, построенного в Netlogo). Поскольку существует много грузовых автомобилей, нецелесообразно использовать «foreach» для циклического прохождения всех доступных грузовиков и вычисления фактического расстояния с использованием вышеуказанного метода. Вы можете использовать примитивное «дистанцироваться», чтобы быстро найти грузовик, но это не совсем точно. Есть ли хороший способ определить ближайший грузовик более быстрым вычислительным методом?

Answer 1

Я не знаю, будет ли это работать с вашей текущей настройкой, но вы также можете найти расширение nw полезным. Например, попробуйте эту настройку (я прошу прощения за длину, просто приближая ваш мир):

extensions [ nw ]

breed [ nodes node ]
breed [ trucks truck ]
breed [ cells cell ]

to setup
  ca

  resize-world -29 29 -14 14

  ask patches with [ ( pxcor mod 5 = 0 or pycor = 0 ) ] [
    set pcolor grey 
    sprout-nodes 1 [
      set size 0.5
      set shape "circle"
      set color green
    ]
  ]

  ask nodes [
    create-links-with turtles-on neighbors4 [
      set color green  
    ]
  ]

  ask n-of 5 nodes [
    hatch 1 [
      set size 1
      set color red
      set breed trucks 
      set shape "car"
    ]
  ]

  ask n-of 2 trucks [
    set color blue
  ]

  ask one-of nodes [
    ask one-of neighbors with [ pcolor = black ] [
      sprout-cells 1 [
        set size 1.5
        set shape "box"
        set color yellow
      ]
    ]
  ]
  reset-ticks
end

Дает простой мир, подобный этому:

Вы можете использовать расширение nw для вычисления расстояний на лету, а не сохранять их в таблице на ячейку, и чтобы вилочные погрузчики (грузовики здесь) следовали по кратчайшему пути. Подробнее в комментариях:

to summon-nearest-truck 
  ; Treat blue trucks as 'empty' and ready to go to a cell
  let ready-trucks trucks with [ color = blue ]

  ; Get the nodes associated with those ready trucks
  let truck-proxies turtle-set map [ i -> [nodes-on patch-here] of i ] sort ready-trucks

  ; Randomly ask one of the cells to
  ask one-of cells [

    ; Choose one of the neighboring road nodes as a proxy for distance calculation
    let node-proxy one-of nodes-on neighbors4 

    ; Get the node proxy to:
    ask node-proxy [
      ; Find the nearest (by network distance) trucks, and select the node
      ; located on the same patch as that truck
      let my-truck-proxy min-one-of truck-proxies [length ( nw:turtles-on-path-to myself) ]

      ; Get that truck-proxy node to generate the path to the original asking node
      ; and have the appropriate truck follow that path
      ask my-truck-proxy [
        ; Generate the path to follow
        let path-to-follow nw:turtles-on-path-to myself

        ; Highlight that path for visualization
        ask turtle-set path-to-follow [
          set color orange
        ]

        ; Get the truck ready to move
        let ready-truck one-of trucks-here with [ color = blue ]
        ask ready-truck[
          set color yellow
        ]

        ; Move that truck along the path-to-follow
        ask ready-truck [
          foreach path-to-follow [
            n ->
            face n
            move-to n
            ; For visualization only
            wait 0.1
          ]
        ]
      ]
    ]
  ]
end

Желтое поле вызывает ближайший грузовик в зависимости от длины nw:turtles-on-path-to, которая возвращается. Этот грузовик следует по пути к узлу вызова: