weltFlow

index.html

<canvas id="canvas" width="500" height="500"></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

seed = 19870910
rng = new Chance seed

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

config = {}
config.generators =
  world:
    options:
      spritesheetOffset: 0
      maxHeight: 7
      # world size
      worldChunkWidth: options.width
      worldChunkHeight: options.height
      # zoom level
      chunkTileWidth: options.sector.width
      chunkTileHeight: options.sector.height
config.worldTileWidth = config.generators.world.options.worldChunkWidth * config.generators.world.options.chunkTileWidth
config.worldTileHeight = config.generators.world.options.worldChunkHeight * config.generators.world.options.chunkTileHeight
config.generators.world.options.worldTileWidth = config.worldTileWidth
config.generators.world.options.worldTileHeight = config.worldTileHeight

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] > 1 }
        @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: ->
    return if @node.data.open
    @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
    @sectorTiles[y][x].arrowEl.visible = false
    @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, @worldData) ->
    @el = new createjs.Container
    @addSectors()
    @addEventListeners()

  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

class WorldGenerator
  constructor: (@randomFn, @seed, @options, cacheTiles = true) ->
    @tileCache = []
    @chunkCache = []
    @tileTypes = []
    @cacheAllTiles() if cacheTiles

  getStartPosition: (seed) ->
    grassTiles = @tileTypes[2]
    index = Math.floor @randomFn(seed) * grassTiles.length
    grassTiles[index]

  getFinishPosition: (seed) ->
    grassTiles = @tileTypes[2]
    index = Math.floor @randomFn(seed) * grassTiles.length
    grassTiles[index]

  getPathfindingArea: (centerX, centerY) ->
    offsetX = (0 - ~~(@options.worldTileHeight / 2)) + centerX
    offsetY = (0 - ~~(@options.worldTileHeight / 2)) + centerY
    outputArray = []
    for y in [[email protected]]
      outputArray[y] = []
      for x in [[email protected]]
        worldX = x + offsetX
        worldY = y + offsetY
        cellIndex = @getCell worldX, worldY
        outputArray[y][x] = cellIndex
    outputArray

  getAllCells: ->
    @tileCache

  cacheAllTiles: ->
    for y in [[email protected]]
      for x in [[email protected]]
        chunk = @getChunk x, y
        for cy in [0...chunk.length]
          for cx in [0...chunk[cy].length]
            vx = x * @options.chunkTileWidth + cx
            vy = y * @options.chunkTileHeight + cy
            cellValue = @getCell vx, vy
            index = Math.floor cellValue / 2
            @tileTypes[index] = [] if @tileTypes[index] is undefined
            @tileTypes[index].push {x:vx, y:vy}

  getCell: (worldX, worldY) ->
    worldX = @clamp worldX, @options.worldTileWidth
    worldY = @clamp worldY, @options.worldTileHeight
    if @tileCache[worldY] and @tileCache[worldY][worldX]?
      return @tileCache[worldY][worldX]
    worldChunkX = Math.floor worldX / @options.chunkTileWidth
    worldChunkY = Math.floor worldY / @options.chunkTileHeight
    chunkX = worldX % @options.chunkTileWidth
    chunkY = worldY % @options.chunkTileHeight
    chunk = @getChunk worldChunkX, worldChunkY
    cell = Math.floor chunk[chunkY][chunkX] * @options.maxHeight
    @tileCache[worldY] = [] unless @tileCache[worldY]?
    @tileCache[worldY][worldX] = cell
    cell

  getChunk: (worldChunkX, worldChunkY) ->
    row0 = [
        @chunkEdgeIndex worldChunkX - 1, worldChunkY - 1
        @chunkEdgeIndex worldChunkX, worldChunkY - 1
        @chunkEdgeIndex worldChunkX + 1, worldChunkY - 1
        @chunkEdgeIndex worldChunkX + 2, worldChunkY - 1
      ]
    row1 = [
        @chunkEdgeIndex worldChunkX - 1, worldChunkY
        @chunkEdgeIndex worldChunkX, worldChunkY
        @chunkEdgeIndex worldChunkX + 1, worldChunkY
        @chunkEdgeIndex worldChunkX + 2, worldChunkY
      ]
    row2 = [
        @chunkEdgeIndex worldChunkX - 1, worldChunkY + 1
        @chunkEdgeIndex worldChunkX, worldChunkY + 1
        @chunkEdgeIndex worldChunkX + 1, worldChunkY + 1
        @chunkEdgeIndex worldChunkX + 2, worldChunkY + 1
      ]
    row3 = [
        @chunkEdgeIndex worldChunkX - 1, worldChunkY + 2
        @chunkEdgeIndex worldChunkX, worldChunkY + 2
        @chunkEdgeIndex worldChunkX + 1, worldChunkY + 2
        @chunkEdgeIndex worldChunkX + 2, worldChunkY + 2
      ]
    chunkTileWidth = @options.chunkTileWidth
    chunkTileHeight = @options.chunkTileHeight
    @bilinearInterpolate chunkTileWidth, chunkTileHeight, row0, row1, row2, row3

  chunkEdgeIndex: (x, y) ->
    width = @options.worldChunkWidth
    height = @options.worldChunkHeight
    seed = @seed
    x = @clamp x, width
    y = @clamp y, height
    @randomFn(y * width + x + seed)

  bilinearInterpolate: (width, height, row0, row1, row2, row3) ->
    cells = []
    for y in [0...height]
      cells[y] = []
      yFactor = y / height
      for x in [0...width]
        xFactor = x / width
        i0 = @terp xFactor, row0[0], row0[1], row0[2], row0[3]
        i1 = @terp xFactor, row1[0], row1[1], row1[2], row1[3]
        i2 = @terp xFactor, row2[0], row2[1], row2[2], row2[3]
        i3 = @terp xFactor, row3[0], row3[1], row3[2], row3[3]
        cells[y][x] = @terp yFactor, i0, i1, i2, i3
    cells

  terp: (t, a, b, c, d) ->
    val = 0.5 * (c - a + (2.0*a - 5.0*b + 4.0*c - d + (3.0*(b - c) + d - a)*t)*t)*t + b
    val = Math.max 0, val
    val = Math.min 1, val
    val

  clamp: (index, size) ->
    (index + size) % size

randomFn = (seed) ->
  (new Chance seed).floating {min: 0, max: 1}

createGrid = ->
  generator = new WorldGenerator randomFn, seed, config.generators.world.options
  worldData = new WorldData generator.tileCache
  gridView = new GridView options.width, options.height, worldData
  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>

style.css

canvas {
  background-color: #dedede;
}

weltflow.markdown

weltFlow

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

A Pen by not important on CodePen.

License.