flow.js

//fields have directions associated with their elements
//2d arrays of vectors
function makeBlankField(x, y) {
  var map = []
  for (var i = 0; i < y; i++) {
    var row = []
    for (var j = 0; j < x; j++) {
      row.push({
        x: 0,
        y: 0
      })
    }
    map.push(row)
  }
  return map
}

//maps are 2d arrays of scalars, which have no direction associated with
//them
function makeBlankMap(x, y) {
  var map = []
  for (var i = 0; i < y; i++) {
    var row = []
    for (var j = 0; j < x; j++) {
      row.push(0)
    }
    map.push(row)
  }
  return map
}

//takes a map and returns the bfs distance between all points on a map
//and a source
function generateDistanceMap(map, source) {
  var dist = makeBlankMap(map.length, map[0].length)
  var seen = makeBlankMap(map.length, map[0].length)
  var nodes = [source]
  seen[source[0]][source[1]] = true
  var node
  while (nodes.length !== 0) {
    node = nodes.shift()
    var nextnodes = [
      [node[0] + 1, node[1]],
      [node[0] - 1, node[1]],
      [node[0], node[1] + 1],
      [node[0], node[1] - 1],
    ]
    for (var i = 0; i < nextnodes.length; i++) {
      var nextnode = nextnodes[i]
      if(nextnode[0] < map.length && nextnode[0] >= 0 &&
         nextnode[1] < map[0].length && nextnode[1] >= 0 &&
         seen[nextnode[0]][nextnode[1]] === 0) {
        seen[nextnode[0]][nextnode[1]] = true
        nodes.push(nextnode)
        dist[nextnode[0]][nextnode[1]] = 1 + dist[node[0]][node[1]]
      }
    }
  }
  return dist
}

function addMaps(map1, map2) {
  if (map1.length !== map2.length || map1[0].length !== map2[0].length) {
    console.log('maps need to be the same size')
  }
  var res = makeBlankMap(map1.length, map1[0].length)
  for (var i = 0; i < map1.length; i++){
    for (var j = 0; j < map1[0].length; j++) {
      res[i][j] = map1[i][j] + map2[i][j]
    }
  }
  return res
}

//takes a map and returns a field where each element tells you where to
//go next in the map.  each element in the field points to the smallest
//neighbor in the corresponding map
function generateGradientField(map) {
  var field = makeBlankField(map.length, map[0].length)
  for(var i = 0; i < map.length; i++) {
    for(var j = 0; j < map[0].length; j++) {
      var minNeighbor = getMinimumCell(map, [i, j])
      field[i][j].x = minNeighbor[0] - i
      field[i][j].y = minNeighbor[1] - j
      var magnitude = Math.sqrt(field[i][j].x * field[i][j].x + field[i][j].y * field[i][j].y)
      if (magnitude !== 0) {
        field[i][j].x /= magnitude
        field[i][j].y /= magnitude
      }
    }
  }
  return field
}

//check all adjacent cells in the map for the smallest weight, return
//the coordinates
function getMinimumCell(map, coordinate) {
  var neighbors = []
  for (var i = -1; i < 2; i++) {
    var x = coordinate[0] + i
    for (var j = -1; j < 2; j++) {
      var y = coordinate[1] + j
      if (x === 0 && y === 0) continue
      if (x >= 0 && x < map.length && y >= 0 && y < map[0].length) neighbors.push([x,y])
    }
  }

  var minIndex = 0;
  var min = map[neighbors[0][0]][neighbors[0][1]]
  for (var i = 0; i < neighbors.length; i++) {
    var weight = map[neighbors[i][0]][neighbors[i][1]]
    if (weight < min) {
      minIndex = i;
      min = weight
    }
  }
  return neighbors[minIndex]
}

function printMap(map) {
  for (var i = 0; i < map.length; i++) {
    var str = ''
    for (var j = 0; j < map[0].length; j++) {
      str += (JSON.stringify(map[i][j]) + ' ')
    }
    console.log(str)
  }
}

var m = generateDistanceMap(makeBlankMap(500,500), [0,2])
printMap(generateGradientField(m))
printMap(m)