sectorFlow

index.html

<canvas id="canvas" width="400" height="400"></canvas>
<ul>
  <li>move the mouse around the field to generate flow fields leading to that point</li>
  <li>the system is optimized by breaking the map into many smaller sectors to generate the flow fields then stitching them together</li>
</ul>

script.coffeescript

rng = new Chance 19870910

options = {
  width: 5
  height: 5
  sector:
    width: 4
    height: 4
  tile:
    width: 20
    height: 20
}
options.grid = {
  width: options.sector.width * options.tile.width
  height: options.sector.height * options.tile.height
}

class FlowField
  neighborDirections: [
    [ 0, -1]
    [ 1,  0]
    [ 0,  1]
    [-1,  0]
    #[ 1, -1]
    #[ 1,  1]
    #[-1,  1]
    #[-1, -1]
  ]

  constructor: (@x, @y, @gridData) ->

  callback: (node) =>
    return unless node.data.open
    node.visited = true
    node.iteration = 1
    @openNodes.push node

  directionFlow: (vX, vY, costCallback, flowCallback) ->
    @reset()
    @openNodes = []
    {width, height} = options.sector
    lX = if vX is -1 then 0 else width - 1
    lY = if vY is -1 then 0 else height - 1
    offsetX = options.sector.width * @x
    offsetY = options.sector.height * @y
    if vX is - 1 or vX is 1
      for y in [0...height]
        node = @gridData.getNode lX + offsetX, y + offsetY
        @callback node
    if vY is -1 or vY is 1
      for x in [0...width]
        node = @gridData.getNode x + offsetX, lY + offsetY
        @callback node
    @costMap 1, costCallback
    @flowMap flowCallback
    if vX is -1 or vX is 1
      for y in [0...height]
        node = @gridData.getNode lX + offsetX, y + offsetY
        continue unless node.data.open
        vector = @neighborVector node, vX, 0
        flowCallback lX, y, vector
    if vY is -1 or vY is 1
      for x in [0...width]
        node = @gridData.getNode x + offsetX, lY + offsetY
        continue unless node.data.open
        vector = @neighborVector node, 0, vY
        flowCallback x, lY, vector

  neighborVector: (node, vX, vY) -> # bug here, sometimes vectors point towards eachother
    neighborNode = @gridData.getNode node.x + vX, node.y + vY
    if neighborNode.data.open
      vector = {x: vX, y: vY}
    else
      offsetX = options.sector.width * @x
      offsetY = options.sector.height * @y
      {width, height} = options.sector
      neighborNodes = @collectNeighbors node, (n) ->
        rX = n.x - offsetX
        rY = n.y - offsetY
        return false unless rX < width and rY < height
        return false unless rX >= 0 and rY >= 0
        n.iteration >= 0
      for n in neighborNodes
        if n.data.open
          vector = {
            x: n.x - node.x
            y: n.y - node.y
          }
          break
    vector

  process: (x, y, costCallback, flowCallback) ->
    @reset()
    offsetX = options.sector.width * @x
    offsetY = options.sector.height * @y
    @openNodes = [@gridData.getNode x + offsetX, y + offsetY]
    @costMap 0, costCallback
    @flowMap flowCallback

  flowMap: (flowCallback) ->
    {width, height} = options.sector
    offsetX = options.sector.width * @x
    offsetY = options.sector.height * @y
    for y in [0...height]
      for x in [0...width]
        node = @gridData.getNode x + offsetX, y + offsetY
        continue unless node.data.open
        continue unless node.visited
        neighbors = @collectNeighbors node, (n) ->
          rX = n.x - offsetX
          rY = n.y - offsetY
          return false unless rX < width and rY < height
          return false unless rX >= 0 and rY >= 0
          n.iteration >= 0
        lowestNode = neighbors.pop()
        neighbors.map (n) ->
          return unless n.data.open
          return unless n.iteration?
          lowestNode = n if lowestNode.iteration > n.iteration
        continue unless lowestNode
        vector = {
          x: lowestNode.x - node.x
          y: lowestNode.y - node.y
        }
        vector = {x: 0, y: 0} if node.iteration is 0
        flowCallback x, y, vector

  reset: ->
    offsetX = options.sector.width * @x
    offsetY = options.sector.height * @y
    {width, height} = options.sector
    for y in [0...height]
      for x in [0...width]
        node = @gridData.getNode x + offsetX, y + offsetY
        node.visited = false

  floodCallback: (node) -> # doesn't feel right to have this here
    return false unless node.data.open
    return false if node.visited
    node.visited = true
    true

  costMap: (iteration, costCallback) ->
    newNodes = []
    while node = @openNodes.pop()
      node.visited = true
      node.iteration = iteration
      {x, y} = node
      costCallback x, y
      nodes = @collectNeighbors node, @floodCallback
      newNodes = newNodes.concat nodes
    @openNodes = @openNodes.concat newNodes
    if @openNodes.length
      @costMap iteration + 1, costCallback

  collectNeighbors: ({x, y}, checkCallback) ->
    {width, height} = options.sector
    nodes = []
    for [dX, dY] in @neighborDirections
      tX = x + dX
      tY = y + dY
      node = @gridData.getNode tX, tY
      continue unless node
      continue unless checkCallback node
      nodes.push node
    nodes

class FlowNode
  constructor: (@x, @y, @iteration, @data = {}) ->

class WorldData
  constructor: (mapData) ->
    @buildData mapData

  buildData: (mapData) ->
    @width = mapData[0].length
    @height = mapData.length
    @nodes = []
    for y in [0...@height]
      @nodes.push []
      for x in [0...@width]
        node = new FlowNode x, y, -Infinity, { open: !!mapData[y][x] }
        @nodes[y][x] = node

  getNode: (x, y) ->
    unless @nodes[y]? and @nodes[y][x]?
      return node = new FlowNode x, y, -Infinity, { open: false }
    @nodes[y][x]

class SectorTile
  directionLookup: {
    '1_0': 0
    '2_1': 90
    '1_2': 180
    '0_1': 270
    '2_0': 45
    '2_2': 135
    '0_2': 225
    '0_0': 315
    '1_1': 0
  }

  constructor: (x, y, @node) ->
    @el = new createjs.Container
    @el.x = x
    @el.y = y
    @render()

  render: ->
    @drawBackground()
    @drawArrow()

  drawBackground: ->
    return if @node.data.open
    g = new createjs.Graphics
    backgroundEl = new createjs.Shape g
    g.f('#880000').dr 0, 0, options.tile.width, options.tile.height
    @el.addChild backgroundEl

  drawArrow: ->
    g = new createjs.Graphics
    @arrowEl = new createjs.Shape g
    width = options.tile.width * 0.25
    height = options.tile.height * 0.75
    x = (options.tile.width - width) / 2
    y = (options.tile.height - height) / 2
    g.lf(['#333333', '#dedede'], [0, 1], 0, 0, 0, height).dr x, y, width, height
    @arrowEl.regX = options.tile.width / 2
    @arrowEl.regY = options.tile.height / 2
    @arrowEl.x = options.tile.width / 2
    @arrowEl.y = options.tile.height / 2
    #@arrowEl.visible = false
    @el.addChild @arrowEl

  setVector: ({x, y}) ->
    return unless @node.data.open
    return if x is 0 and y is 0
    @arrowEl.visible = true
    @arrowEl.rotation = @directionLookup["#{x + 1}_#{y + 1}"]

  clearVector: ->
    @arrowEl.visible = false

class SectorView
  constructor: (@worldData, @x, @y) ->
    @el = new createjs.Container
    @render()
    @flowField = new FlowField @x, @y, @worldData

  reset: ->
    for row, y in @sectorTiles
      for sectorTile, x in row
        sectorTile.clearVector()

  markCost: ->

  markFlow: (x, y, vector) =>
    @sectorTiles[y][x].setVector vector

  render: ->
    @drawTiles()
    @el.cache 0, 0, options.grid.width, options.grid.height

  drawTiles: ->
    @sectorTiles = []
    {width, height} = options.sector
    for y in [0...height]
      @sectorTiles[y] = []
      for x in [0...width]
        pX = x * options.tile.width
        pY = y * options.tile.height
        wX = @x * options.sector.width + x
        wY = @y * options.sector.height + y
        node = @worldData.getNode wX, wY
        sectorTile = new SectorTile pX, pY, node
        @el.addChild sectorTile.el
        @sectorTiles[y][x] = sectorTile

  process: (x, y) ->
    @vX = @vY = undefined
    return unless @sectorTiles[y][x].node.data.open
    @flowField.process x, y, @markCost, @markFlow
    @el.updateCache()

  directionFlow: (vX, vY) ->
    return if vX is @vX and vY is @vY
    @vX = vX
    @vY = vY
    @flowField.directionFlow vX, vY, @markCost, @markFlow
    @el.updateCache()

class GridView
  constructor: (@width, @height) ->
    @el = new createjs.Container
    @createWorldData()
    @addSectors()
    @addEventListeners()
  
  createWorldData: ->
    width = options.width * options.sector.width
    height = options.height * options.sector.height
    @worldData = new WorldData mapData(width, height)

  addSectors: ->
    @sectors = []
    for y in [0...options.height]
      @sectors[y] = []
      for x in [0...options.width]
        pX = x * options.grid.width
        pY = y * options.grid.height
        sectorView = @addSector pX, pY, x, y
        @el.addChild sectorView.el
        @sectors[y][x] = sectorView

  addSector: (x, y, sectorX, sectorY) ->
    sectorView = new SectorView @worldData, sectorX, sectorY
    sectorView.el.x = x
    sectorView.el.y = y
    sectorView

  addEventListeners: ->
    {width, height} = options
    @cX = @cY = undefined
    $('canvas').mousemove @onMouseMove

  onMouseMove: ({offsetX, offsetY}) =>
    sectorX = ~~(offsetX / options.grid.width)
    sectorY = ~~(offsetY / options.grid.height)
    mX = offsetX % options.grid.width
    mY = offsetY % options.grid.height
    x = ~~(mX / options.tile.width)
    y = ~~(mY / options.tile.height)
    if @cX isnt x or @cY isnt y
      @cX = x
      @cY = y
      for sY in [0...options.height]
        for sX in [0...options.width]
          sector = @sectors[sY][sX]
          sector.reset()
          if sX is sectorX and sY is sectorY
            sector.process x, y
          else
            vX = 0
            vY = 0
            if sectorX > sX
              vX = 1
            if sectorX < sX
              vX = -1
            if sectorY > sY
              vY = 1
            if sectorY < sY
              vY = -1
            sector.directionFlow vX, vY

mapData = (width, height) ->
  data = []
  for y in [0...height]
    data[y] = []
    for x in [0...width]
      data[y][x] = rng.bool {likelihood: 92}
  data

createGrid = ->
  gridView = new GridView options.width, options.height
  stageEl.addChild gridView.el
  gridView.onMouseMove {offsetX: 0, offsetY: 0}

stageEl = new createjs.Stage 'canvas'
createjs.Ticker.setFPS 60
createjs.Ticker.addEventListener 'tick', ->
  stageEl.update()

createGrid()

scripts

<script src="https://code.createjs.com/easeljs-0.8.0.min.js"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/chance/0.5.6/chance.js"></script>
<script src="//code.jquery.com/jquery-2.1.3.js"></script>

sectorflow.markdown

sectorFlow

pathfinding for large areas, using flow fields and breaking the map into smaller sectors

A Pen by not important on CodePen.

License.

style.css

canvas {
  background-color: #dedede;
}