Grid Path

model.coffee

# AgentBase is Free Software, available under GPL v3 or any later version.
# Original AgentScript code @ 2013, 2014 Owen Densmore and RedfishGroup LLC.
# AgentBase (c) 2014, Wybo Wiersma.

# Grid Path shows one of Knuth's great puzzles on the probability
# of all Manhattan traversals diagonally traversing a grid.

u = ABM.util

class ABM.GridPathModel extends ABM.Model
  setup: ->
    @refreshAgents = false # for static agents
    
    # globals
    @prob = 1
    
    # defaults
    @patches.setDefault "labelColor", u.color.white
    offset = Math.floor @world.size * .45
    @patches.setDefault "labelOffset", {x: offset, y: offset}
    u.contextTextParams @contexts.patches, "10px sans-serif",
        "right", "bottom"
    @agents.setDefault "shape", "circle"
    @agents.setDefault "color", u.color.from [210, 0, 0]
    @agents.setDefault "size", .4
    @agents.setDefault "hidden", 2.5
    @agents.setDefault "heading",  0 # override promotion to random angle

    @animator.setRate 10

    for patch in @patches.create()
      patch.color = u.color.random type: "gray", min: 160, max: 190
      patch.occupied = false

    @drawGrid u.color.black
    @walker = @agents.create(1)[0]
    patch0 = @patches[0]
    @walker.moveTo patch0.position
    @walker.penDown = true
    @walker.stamp()
    @walker.patch.occupied = true

  step: ->
    @floodFill()

    patches = new ABM.Set
    for neighbor in @walker.patch.neighbors(diamond: 1)
      if neighbor.ok
        patches.push neighbor

    @drawNum patches.length
    @walker.moveTo patches.sample().position
    @walker.stamp()
    @walker.patch.occupied = true
    if @done()
      @stop()
      console.log "prob: #{@prob}"
  
  drawNum: (number) ->
    @walker.patch.label = "" + number
    @prob /= number

  done: ->
    @patches.last().occupied
  
  drawGrid: (color) ->
    agent = @agents.create(1)[0]
    agent.color = color
    agent.penSize *= .4
    agent.heading = Math.PI / 2

    for x in [0..@patches.max.x]
      agent.moveTo x: x, y: 0
      agent.penDown = true
      agent.forward @patches.max.y
      agent.penDown = false
    agent.heading = 0

    for y in [0..@patches.max.y]
      agent.moveTo x: 0, y: y
      agent.penDown = true
      agent.forward @patches.max.x
      agent.penDown = false
    agent.die()
  
  floodFill: ->
    for patch in @patches
      patch.ok = false

    patches = new ABM.Set @patches.last()

    while patches.length > 0
      for patch in patches
        patch.ok = true

      neighbors = new ABM.Set

      for patch in patches
        neighbors.push patch.neighbors(diamond: 1)

      nextPatches = neighbors.flatten()
      nextPatches = nextPatches.flatten()
      nextPatches.sort("id").uniq()

      patches = new ABM.Set
      
      for nextPatch in nextPatches
        if not nextPatch.ok and not nextPatch.occupied
          patches.push nextPatch
    null

window.model = new ABM.GridPathModel({
  div: "world",
  patchSize: 30,
  min: {x: 0, y: 0},
  max: {x: 10, y: 10}
})
window.model.start()

# Uses the AgentBase library (03-02-2017 release)
# https://github.com/wybo/agentbase/commit/3501302567c018da82601cd858be2ea6d0b9c74d