slither.js

if (window._loop != undefined) {
  clearInterval(window._loop);
}

if (window._origRedraw != undefined) {
  redraw = window._origRedraw;
}

(function() {
  window.lastTarget = {
    x: 0,
    y: 0
  };
  setTarget = function(x, y) {
    dx = x - snake.xx
    dy = y - snake.yy
    m = Math.sqrt(dx * dx + dy * dy) + 0.01
    xm = dx / m * 100
    ym = dy / m * 100
    lastTarget.x = x;
    lastTarget.y = y;
  };

  getDist = function(A, B) {
    return Math.sqrt((A.xx-B.xx)*(A.xx-B.xx)+(A.yy-B.yy)*(A.yy-B.yy));
  };

  var BINSIZE = 100;
  coordHash = function(x, y) {
    return parseInt(x / BINSIZE) + ',' + parseInt(y / BINSIZE);
  };

  window.foodDensity = {};
  computeFoodDensity = function() {
    // Compute food density field
    foodDensity = {};
    for (var i = 0; i < foods.length; i++) {
      var food = foods[i];
      if (food == null) { continue; }
      var hash = coordHash(food.xx, food.yy);
      if (foodDensity[hash] == undefined) {
        foodDensity[hash] = 0;
      }
      foodDensity[hash] += Math.pow(food.sz, 1.4);
    }
  };

  window.threatDensity = {};
  computeThreatDensity = function() {
    threatDensity = {};
    for (var i = 0; i < snakes.length; i++) {
      var s = snakes[i];
      var _headWeight = 25;
      var _bodyWeight = 0.3;
      if (s == null) { continue; }
      if (s.xx == snake.xx && s.yy == snake.yy) {
        _headWeight = 0;
        _bodyWeight = 0.05;
      }
      var n = s.pts.length;
      // Big threat near head
      var _tS = 1 + parseInt(n / 100)
      for (var _xx = -_tS; _xx <= _tS; _xx++) {
        for (var _yy = -_tS; _yy <= _tS; _yy++) {
          var hash = coordHash(s.xx + _xx * BINSIZE, s.yy + _yy * BINSIZE);
          if (threatDensity[hash] == undefined) {
            threatDensity[hash] = 0;
          }
          threatDensity[hash] += _headWeight
        }
      }
      // Account for the threat rating at each coordinate of the snake
      for (var j = 0; j < s.pts.length; j++) {
        var threat = s.pts[j];
        if (threat.dying) {
          continue;
        }
        var hash = coordHash(threat.xx, threat.yy);
        if (threatDensity[hash] == undefined) {
          threatDensity[hash] = 0;
        }
        threatDensity[hash] += 1
        _tS = 1;
        for (var _xx = -_tS; _xx <= _tS; _xx++) {
          for (var _yy = -_tS; _yy <= _tS; _yy++) {
            var hash = coordHash(threat.xx + _xx * BINSIZE, threat.yy + _yy * BINSIZE);
            if (threatDensity[hash] == undefined) {
              threatDensity[hash] = 0;
            }
            if (_xx == 0 && _yy == 0) {
              threatDensity[hash] += _headWeight;
            } else {
              threatDensity[hash] += _bodyWeight;
            }
          }
        }
      }
    }
  };

  findBestFood = function() {
    var bestFood = null;
    var bestValue = -1000;
    var bestDot = 0;
    var _myLen = snake.pts.length;
    var wang = -Math.atan2(-(snake.yy - snake.pts[snake.pts.length-1].yy),
                           snake.xx - snake.pts[snake.pts.length-1].xx);

    // Find best food to hunt via region and motion cost
    for (var i = 0; i < foods.length; i++) {
      var food = foods[i];
      if (food == null) { continue; }
      var dx = food.xx - snake.xx;
      var dy = food.yy - snake.yy;
      var angToFood = Math.atan2(dy, dx);
      // var wang = Math.atan2(ym, xm);
      var dist = Math.sqrt(dx * dx + dy * dy);
      var dotHeading = Math.cos(angToFood) * Math.cos(wang)
                     + Math.sin(angToFood) * Math.sin(wang);
      var crossHeading = Math.cos(angToFood) * Math.sin(wang)
                       - Math.sin(angToFood) * Math.cos(wang);
      var hash = coordHash(food.xx, food.yy);
      var regionValue = foodDensity[hash];
      var correctHeading = (dotHeading + 1) / 2.0;
      // Value is proportional to food density in region
      var value = regionValue + food.sz
      // Value is reduced using an opportunity cost for distance traveled
      value /= dist * 0.01 + 1;
      // Value increases for correct heading
      value +=  correctHeading * (0.01 * _myLen + 2);
      // Value decreases if you are trying to make tight turns
      if (dotHeading < 0.0 && dist < 200) {
        value = -1000;
      }
      // Threats in that region reduce value
      var threatVal = threatDensity[hash]
      if (threatVal == undefined) {threatVal = 0;}
      // value /= (1 + threatVal);
      // Food line of sight
      var LOSThreat = lineOfSightThreat(snake, food);
      value -= LOSThreat;
      // Choose min cost food
      if (value > bestValue) {
        bestFood = food;
        bestValue = value;
        bestDot = dotHeading;
      }
    }
    return {
      food: bestFood,
      heading: bestDot
    }
  };

  lineOfSightThreat = function(A, B) {
    var _x = A.xx;
    var _y = A.yy;
    var _dx = (B.xx - A.xx);
    var _dy = (B.yy - A.yy);
    var dist = Math.sqrt(_dx * _dx + _dy * _dy);
    steps = parseInt(dist / BINSIZE);
    _dx /= steps;
    _dy /= steps;
    var acc = 0;
    while (steps > 0) {
      var hash = coordHash(_x, _y);
      var threatVal = 0;
      if (threatDensity[hash] != undefined) {
        threatVal = threatDensity[hash];
      }
      acc += threatVal;
      _x += _dx;
      _y += _dy;
      steps--;
    }
    return acc;
  };

  findNearestThreat = function() {
    nearestThreat = null
    nearestDist = 160 + Math.sqrt(snake.pts.length * 200);
    for (var i = 0; i < snakes.length; i++) {
      s = snakes[i];
      if (s == null) { continue; }
      if (s.xx == snake.xx && s.yy == snake.yy) { continue }
      for (var j = 0; j < s.pts.length; j++) {
        threat = s.pts[j];
        if (threat.dying) { continue; }
        dist = getDist(snake, threat);
        if (dist < nearestDist) {
          nearestDist = dist;
          nearestThreat = threat;
        }
      }
    }
    return nearestThreat
  };

  runStrategy = function() {
    // Food gathering
    bestFoodObj = findBestFood();
    if (bestFoodObj.food != null) {
      bestFood = bestFoodObj.food;
      setTarget(bestFood.xx, bestFood.yy);
      var hash = coordHash(bestFood.xx, bestFood.yy);
      var threatVal = 0;
      if (threatDensity[hash] != undefined) {
        threatVal = threatDensity[hash];
      }
      freeData[0] = 'Target food density: ' + parseInt(foodDensity[hash]);
      freeData[1] = 'Target heading:      ' + bestFoodObj.heading.toFixed(2);
      if (threatVal < 5) {
        if (foodDensity[hash] > 75 && bestFoodObj.heading > 0.91) {
          setAcceleration(1);
        }
      }
    }

    // Threat avoidance
    nearestThreat = findNearestThreat();
    if (nearestThreat != null) {
      setTarget(2 * snake.xx - nearestThreat.xx, 2 * snake.yy - nearestThreat.yy)
    }
  };

  update = function() {
    if (snake == null) {return;}
    setAcceleration(0);
    BINSIZE = 120 + parseInt(snake.pts.length * 0.1);
    computeFoodDensity();
    computeThreatDensity();
    runStrategy();
  };

  var _canvas = $('canvas.nsi');
  var ctx = _canvas.getContext('2d');
  window._SF = 0.9;
  window.freeData = new Array(10);
  render = function() {
    _SF = .5 + .4 / Math.max(1, (snake.sct + 16.0) / 36.0);
    for (var x = -_canvas.width / _SF; x < _canvas.width / _SF; x += BINSIZE) {
      for (var y = -_canvas.height / _SF; y < _canvas.height / _SF; y += BINSIZE) {
        ctx.setTransform(1, 0, 0, 1, 0, 0);
        var VX = (x - view_xx%BINSIZE);
        var VY = (y - view_yy%BINSIZE);
        var G = foodDensity[coordHash(VX + view_xx, VY + view_yy)];
        if (G == undefined) {
          G = 0;
        }
        ctx.globalAlpha = (1.0 - Math.exp(-G * 0.03)) * 0.5;
        ctx.fillStyle = 'rgb(0,255,0)';
        ctx.fillRect((VX) * _SF + _canvas.width / 2.0,
                     (VY) * _SF + _canvas.height / 2.0,
                     BINSIZE * _SF, BINSIZE * _SF);

        var R = threatDensity[coordHash(VX + view_xx, VY + view_yy)];
        if (R == undefined) {
          R = 0;
        }
        ctx.globalAlpha = (1.0 - Math.exp(-R * 0.03)) * 0.5;
        ctx.fillStyle = 'rgb(255,0,0)';
        ctx.fillRect((VX) * _SF + _canvas.width / 2.0,
                     (VY) * _SF + _canvas.height / 2.0,
                     BINSIZE * _SF, BINSIZE * _SF);
      }
    }
    // Draw immediate target
    ctx.globalAlpha = 0.5;
    ctx.strokeStyle = 'rgb(255,255,255)';
    var VX = (snake.xx - view_xx);
    var VY = (snake.yy - view_yy);
    ctx.lineWidth = 1;
    ctx.beginPath();
    ctx.moveTo(VX * _SF + _canvas.width / 2.0,
               VY * _SF + _canvas.height / 2.0);
    ctx.lineTo((VX + lastTarget.x - snake.xx) * _SF + _canvas.width / 2.0,
               (VY + lastTarget.y - snake.yy) * _SF + _canvas.height / 2.0);
    ctx.stroke();
    // Draw data array
    ctx.globalAlpha = 0.5;
    ctx.fillStyle = 'rgb(255,255,255)';
    ctx.font = '16px courier';
    for (var i = 0; i < freeData.length; i++) {
      if (freeData[i] == undefined) { continue; }
      ctx.fillText(freeData[i], 20, 100 + i * 20);
    }
  };

  window._origRedraw = redraw;
  redraw = function() {
    if (snake == null) {return;}
    window._origRedraw();
    render();
  };

  var _gameOver = 0;
  window._loop = setInterval(function() {
    update();
    if (snake == null) {
      _gameOver++;
    } else {
      _gameOver = 0;
    }
    // Auto-replay
    if (_gameOver > 20 && !connecting) {
      connect();
    }
  }, 100)
})()