How to assign the shortest-distance to all agents
- Current status: My codes only finds the shortest-path for 1 person but cannot when there are more than 1 person.
- Question: How can I assign the shortest-path for each person?
Background
I manipulated the traffic grid model inside the NetLogo model library to create a shortest-path algorithm for pedestrians (somewhat close to A*). The interface below shows that an agent is standing on its origin which is coloured in pale yellow, and has the same colour as a destination. It also works fine for 3 people.
- 1 person
- 3 people
Setup
Here is a code chunck that I wrote as a setup. It doesn't seem to have any problem in this section.
globals
[
grid-x-inc ;; the amount of patches in between two roads in the x direction
grid-y-inc ;; the amount of patches in between two roads in the y direction
intersections ;; agentset containing the patches that are intersections
roads ;; agentset containing the patches that are roads
population
]
breed[people person]
patches-own
[
father
navigated?
active?
Heuristic
step
total-cost
is-intersection?
start
finish
]
people-own
[
origin
destination
h-distance ;; short for heuristic distance. Euclidean distance to goal
path
]
to setup
clear-all
setup-globals
setup-patches
setup-people
setup-destination
reset-ticks
end
to setup-globals
set grid-x-inc world-width / grid-size-x
set grid-y-inc world-height / grid-size-y
ask patches
[
set father nobody
set navigated? false
set active? false
set total-cost 0
]
end
to setup-patches
;; initialize the patch-owned variables and color the patches to a base-color
ask patches [ set pcolor brown + 3 ]
;; initialize the global variables that hold patch agentsets
set roads patches with
[(floor((pxcor + max-pxcor - floor(grid-x-inc - 1)) mod grid-x-inc) = 0) or
(floor((pycor + max-pycor) mod grid-y-inc) = 0)]
set intersections roads with
[(floor((pxcor + max-pxcor - floor(grid-x-inc - 1)) mod grid-x-inc) = 0) and
(floor((pycor + max-pycor) mod grid-y-inc) = 0)]
ask roads [ set pcolor white ]
ask intersections [ set is-intersection? true
ask neighbors [ set is-intersection? true ]]
end
to setup-people
create-people no-of-people
[
set shape "person"
set size 1
set color black
move-to one-of patches with [pcolor != brown + 3]
set origin patch-here
set destination one-of patches with [pcolor != brown + 3 and is-intersection? != true]
set h-distance distance destination
]
set population [] ;; create list of individuals
let sort-turtles sort people set population sort-turtles
end
to setup-destination
foreach population [ individual ->
ask individual [
let roads_ roads with [pcolor = white]
ask roads_ [
set navigated? false
set active? false
set Heuristic 0
set step 0
set total-cost 0
set start false
set finish false
]]
let current [origin] of individual
let target [destination] of individual
ask individual [
if target != nobody [
ask current [
set pcolor (10 + random 130)
set step 0
set start true
set finish false
set navigated? false
]
ask target [
set pcolor [pcolor] of current
set navigated? true
set start false
set finish true
]]
]]
end
Problem 1: Set all paths
set-path traces all the steps from the origin patch to everywhere inside the virtual world. The code will colour the road to yellow and add a label on the path. This procedure will repeat 50 times to find all the possible steps.
The problem occurs from this section where this code only works for one agent not for the entire agents.
to set-path
repeat 50 [
ask patches with [pcolor = white and pcolor != yellow] [
if any? neighbors4 with [ start = true ] or
any? neighbors4 with [ pcolor = yellow ]
[ set pcolor yellow
let laststep [step] of one-of neighbors4 with [pcolor = yellow or
start = true]
ifelse [plabel] of patches != nobody [
set step laststep + 1
set plabel step
set father step
set total-cost father + heuristic
set plabel-color red][set plabel ""]
]]]
let allroads [self] of patches with [pcolor != brown]
let final_location one-of patches with [finish = true]
foreach allroads [ road_patch ->
ask road_patch [set Heuristic distance final_location]
]
end
Problem 2: Set shortest path
This procedure finds the shortest path by finding the patches and adding them to a list named path. Because the previous procedure only worked for one agent this procedure will also assign the patches to one agent, which is not what I want.
to shortest-path
ask patches with [start = true] [
let maxsteps 0
ask patches with [navigated? = true]
[ let check-steps min-one-of neighbors4 with
[pcolor != brown + 3 and pcolor != white][step]
set maxsteps [step] of check-steps
]
let num (range maxsteps 0 -1)
let paths []
foreach num [ navigation ->
ask patches with [navigated? = true] [
let nav-patch min-one-of neighbors4 with
[step = navigation and pcolor != brown + 3][step]
if nav-patch != nobody [ask nav-patch [set navigated? true set paths fput self paths]]
]]
ask people [set path paths]
]
ask patches with [pcolor = yellow][set pcolor white set plabel ""]
end
Summary: What I want the model to look like
How can I assign the shortest-path for each person if there are more than 2 people inside NetLogo?
What I want the model to look like
File: https://drive.google.com/file/d/1gxhkcnlBniB5M4aSYmt65PE6LBekgVp6/view?usp=sharing
