Surface Walking 2D

2 collaborators

Uri Wilensky (Author)

WHAT IS IT?

This model is a 2D version of a surface-walking algorithm used in "Surface Walking 3D". Turtles approximate a user-defined surface using a simple algorithm that considers the turtle's current position relative to neighboring surface patches.

HOW IT WORKS

Turtles exist in a world that consists of two different kinds of patches: surface and non-surface. Turtles follow two basic rules in order to walk along the patch-defined surface:

Look for opposite neighboring patches. If the turtle is currently on a surface patch, it will look for a non-surface one, and vice versa.
Of those neighboring patches of opposite type, identify the one that requires the smallest change in turtle heading for the turtle to face.
Turn halfway to that patch that requires the smallest change in heading to face and take a step.

Why does this algorithm work? Consider any perturbation along a flat surface (in the case of 2D, a curve or angle along an otherwise straight line). In order to traverse the perturbation and remain on the surface, a turtle needs to find and remain on the 'edge' of the surface, and maintain its direction while travelling along this edge. Since turtles in NetLogo always report being on only one patch (the one that the center of their body is over), we maintain the turtle's position along the edge by having it search for a patch that is of opposite type to the patch it is positioned over (Rule 1).

Rule 2 enables the turtles to travel along that edge while maintaining their current direction. Consider a surface in 2d: turtles are able to travel along that surface in one of two opposite directions (for example, they can walk along a circle in either a clockwise or counterclockwise direction). If a surface is flat, a turtle needs not change its heading at all to continue to travel in the same direction along that surface. But, if the surface is curved or has an angle, then in order to continue to stay along the edge of the surface the turtle must change its heading. If it changes its heading exactly 180 degrees, it will reverse its direction of travel. But whether the angle is concave or convex, it will be of some measure between 0 and 360 degrees (non-inclusive). Then the heading change required to continue along the surface without reversing the direction of travel will be less than that required to reverse direction.

Finally, Rule 3 reduces the 'weaving' effects produced by turtles moving toward surface and non-surface patches in order to remain close to the edge by having turtles actually point only halfway to the patch of interest.

HOW TO USE IT

NUMBER-OF-TURTLES: Allows the user to adjust the number of turtles that will appear along the shape surface when SETUP is pressed.
STEP-SIZE: Allows the user to adjust how far each turtle moves forward during each step.
SURFACE-SHAPE: Allows the user to select the surface shape to appear when SETUP is pressed.
COLORED-SURFACE?: Allows user to toggle whether the surface on which turtles will walk is colored red, or is invisible.
DRAW-SURFACE: Allows the user to add mouse-drawn components to an existing surface by pressing the button and then clicking and dragging anywhere in the view. The area surrounding patches identified by the mouse will be set to behave as a surface, and if the COLORED-SURFACE? switch is on, the area will also turn red.
TRACE: Asks one of the turtles to draw a trail as it moves.
SETUP: Sets up the environment by creating a surface and placing turtles along the surface.
GO: Runs the model by asking turtles to walk along the surface.

THINGS TO NOTICE

Try adjusting STEP-SIZE while the model is running. What happens to the motion of the turtles? What happens to their speed?

Do turtles behave differently on different types of surfaces? Try using the SURFACE-SHAPE chooser to test different shapes. Then, try drawing your own by clicking on DRAW-SURFACE and clicking and dragging your mouse in the view.

THINGS TO TRY

What might happen if the STEP-SIZE is set to 1 or larger? Currently, turtles turn half of the way to the edge-patch they identify. What happens if they turn the whole way?

Select "Mickey Mouse" from the SURFACE-SHAPE chooser. SETUP and tell the model to GO. What happens to turtles when they pass over the acute angles where Mickey's ears meet his head? Try adjusting the STEP-SIZE slider while the model is running to investigate.

When does the surface-walking algorithm fail? Why? Use the DRAW-SURFACE button to test different shapes and angles. Does changing the resolution of the world's grid of patches affect turtle motion?

EXTENDING THE MODEL

Currently, turtles seek the surface edge by seeking patches that are classified in certain ways. Find and implement another way that patches can be identified or that turtles can identify edge patches.

Try using stamp to trace the trajectory of a turtle over different kinds of surfaces. How might one describe surface-walking accuracy?

The surface-walking algorithm used in this model fails for surfaces (or gaps in surfaces) that are only one patch wide. Why? How might this be fixed?

NETLOGO FEATURES

Note the use of towards to compute headings and min-one-of to make a choice between competing patches.

RELATED MODELS

See Surface Walking 3D (NetLogo 3D) and Virus on a Surface 3D (NetLogo 3D).

Wall Following Example is a simpler version of this example. It is entirely grid-based; the turtles move from patch center to center. The code for this is much less complicated and the turtles are always able to follow the wall perfectly correctly.

CREDITS AND REFERENCES

Thanks to Michelle Wilkerson for her work on this model.

HOW TO CITE

If you mention this model in a publication, we ask that you include these citations for the model itself and for the NetLogo software:

Wilkerson, M. and Wilensky, U. (2007). NetLogo Surface Walking 2D model. http://ccl.northwestern.edu/netlogo/models/SurfaceWalking2D. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.
Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.

COPYRIGHT AND LICENSE

CC BY-NC-SA 3.0

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu.

Comments and Questions

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

Click to Run Model

;; =========================== Main Procedures ===============================

to setup
  clear-all
  if surface-shape = "circle" [ draw-big-circle ]
  if surface-shape = "square" [ draw-square     ]
  if surface-shape = "mouse"  [ draw-mouse      ]
  ask n-of number-of-turtles patches with [any? different-colored-neighbors]
    [ sprout 1
       [ set size 5
         set pen-size 2
         set color one-of remove violet base-colors ] ]
  reset-ticks
end 

to go
  ask turtles [ sfd step-size ]
  tick
end 

;; =========================== Surface Walking ===============================

to sfd [how-far]  ;; turtle procedure
  face-chosen-neighbor
  fd how-far
end 

to face-chosen-neighbor  ;; turtle procedure
  ;; turtle faces the patch that requires the least change in
  ;; heading to face
  let closest-border-patch min-one-of different-colored-neighbors [abs turn-amount]
  rt [turn-amount / 2] of closest-border-patch
end 

;; computes the turn the calling turtle would have to make to face this patch

to-report turn-amount  ;; patch procedure
  let this-patch self
  report [subtract-headings (towards this-patch) heading] of myself
end 

;; ======================= Other Surface Procedures ==========================

to draw-surface
  while [mouse-down?] [
    create-turtles 1 [
      setxy mouse-xcor mouse-ycor
      ask patches in-radius 3 [ set pcolor violet ]
      die
    ]
    display
  ]
end 

to-report different-colored-neighbors  ;; patch procedure
  ;; report neighbors that are a different color than me
  report neighbors with [pcolor != [pcolor] of myself]
end 

;; =========================== Surface Drawing ===============================

to draw-big-circle
  draw-circle 0 0 (world-width * 0.45)
end 

to draw-square
  ask patches with [pxcor > world-width * -0.45 and
                    pxcor < world-width *  0.45 and
                    pycor > world-width * -0.45 and
                    pycor < world-width *  0.45]
    [ set pcolor violet ]
end 

to draw-mouse
  draw-circle 0                    (world-width * -0.1 ) (world-width * 0.35)
  draw-circle (world-width *  0.3) (world-width *  0.25) (world-width * 0.17)
  draw-circle (world-width * -0.3) (world-width *  0.25) (world-width * 0.17)
end 

to draw-circle [x y radius]
  ask patches with [distancexy x y < radius]
    [ set pcolor violet ]
end 


; Copyright 2007 Uri Wilensky.
; See Info tab for full copyright and license.

There are 10 versions of this model.

Uploaded by	When	Description	Download
Uri Wilensky	over 11 years ago	Updated to NetLogo 5.0.4	Download this version
Uri Wilensky	about 12 years ago	Updated version tag	Download this version
Uri Wilensky	about 12 years ago	Updated to version from NetLogo 5.0.3 distribution	Download this version
Uri Wilensky	almost 13 years ago	Updated to NetLogo 5.0	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Model from NetLogo distribution	Download this version
Uri Wilensky	over 14 years ago	Surface Walking 2D	Download this version

Attached files

File	Type	Description	Last updated
Surface Walking 2D.png	preview	Preview for 'Surface Walking 2D'	over 11 years ago, by Uri Wilensky	Download

This model does not have any ancestors.

This model does not have any descendants.

NetLogo