voidbot.js

/**
 @license
 Copyright 2014 David Aurelio <dev@david-aurelio.com>
 Full source at https://gist.github.com/davidaurelio/4bdafd219ebf610e8fc4
 */
(function() {
  'use strict';

  var GIVE_UP = 0;
  var NORTH = 1, EAST = 2, SOUTH = 3, WEST = 4;
  var HORIZONTAL_SHIFT = 0, VERTICAL_SHIFT = 8;
  var HORIZONTAL_MOVE = 1 << HORIZONTAL_SHIFT,
      VERTICAL_MOVE = 1 << VERTICAL_SHIFT;
  var HORIZONTAL_MASK = 0xff << HORIZONTAL_SHIFT,
      VERTICAL_MASK = 0xff << VERTICAL_SHIFT;

  var BLOCKED = -1, FREE = 0, OWNED = 1;

  var currentPosition = 99 << VERTICAL_SHIFT | 99 << HORIZONTAL_SHIFT;
  var verticalMax = currentPosition & VERTICAL_MASK,
      verticalMin = verticalMax,
      horizontalMax = currentPosition & HORIZONTAL_MASK,
      horizontalMin = horizontalMax;
  var world = new Int8Array(0x10000);
  world[currentPosition] = OWNED;
  var currentHeading, currentStrategy, triedHeading;

  function random(n) {
    return Date.now() % n;
  }

  function moveNorth(position) { return position + VERTICAL_MOVE; }
  function moveEast(position) { return position + HORIZONTAL_MOVE; }
  function moveSouth(position) { return position - VERTICAL_MOVE; }
  function moveWest(position) { return position - HORIZONTAL_MOVE; }

  function move(position, heading) {
    return heading === NORTH ? moveNorth(position) :
           heading === EAST ? moveEast(position) :
           heading === SOUTH ? moveSouth(position) :
           heading === WEST ? moveWest(position) :
           position;
  }

  function updateExtrema(position) {
    var x = position & HORIZONTAL_MASK, y = position & VERTICAL_MASK;
    if (x > horizontalMax) {
      horizontalMax = x;
    } else if (x < horizontalMin) {
      horizontalMin = x;
    }

    if (y > verticalMax) {
      verticalMax = y;
    } else if (y < verticalMin) {
      verticalMin = y;
    }
  }

  function goNorthAsLongAsPossible(wasLastMoveSuccessful) {
    return wasLastMoveSuccessful === false ? null : NORTH;
  }
  function goSouthAsLongAsPossible(wasLastMoveSuccessful) {
    return wasLastMoveSuccessful === false ? null : SOUTH;
  }
  function goNorthToEquator(_, queue) {
    var currentVerticalPosition = currentPosition & VERTICAL_MASK;
    var equator = verticalMax + verticalMin >> 1 & VERTICAL_MASK;
    var steps = equator - currentVerticalPosition >> VERTICAL_SHIFT;
    while ((steps--)) {
      queue.push(NORTH);
    }
    return null;
  }
  function goWestAsLongAsPossible(wasLastMoveSuccessful) {
    return wasLastMoveSuccessful === false ? null : WEST;
  }
  function goEastAsLongAsPossible(wasLastMoveSuccessful) {
    return wasLastMoveSuccessful === false ? null : EAST;
  }
  function fill() {
    if (!currentHeading) {
      currentHeading = NORTH;
    }

    // if we could move ahead, try to move further ahead
    var coordinatesAhead = move(currentPosition, currentHeading);
    var fieldAhead = world[coordinatesAhead];
    if (fieldAhead === FREE) {
      return currentHeading;
    }

    // check for other free fields around us
    var left = currentHeading === NORTH ? WEST : currentHeading - 1;
    var right = currentHeading === WEST ? NORTH : currentHeading + 1;
    var coordinatesLeft = move(currentPosition, left);
    var coordinatesRight = move(currentPosition, right);
    var sides = [
      [left, world[coordinatesLeft]],
      [right, world[coordinatesRight]]
    ];

    var firstIndex = random(2), secondIndex = 1 >> firstIndex;
    if (sides[firstIndex][1] === FREE) {
      return sides[firstIndex][0];
    }
    if (sides[secondIndex][1] === FREE) {
      return sides[secondIndex][0];
    }


    // go backwards, if not taken
    var backwards = currentHeading + (currentHeading < 3 ?  2 : -2);
    var coordinatesBehind = move(currentPosition, backwards);
    var fieldBehind = world[coordinatesBehind];
    if (fieldBehind === FREE) {
      return backwards;
    }

    // if there are no free fields around us, go forward if possible
    if (fieldAhead === OWNED) {
      return currentHeading;
    }

    // try to the side, if possible
    if (sides[firstIndex][1] === OWNED) {
      return sides[firstIndex][0];
    }
    if (sides[secondIndex][1] === OWNED) {
      return sides[secondIndex][0];
    }

    // go backwards, if possible
    if (fieldBehind === OWNED) {
      return backwards;
    }

    // nothing is possible, give up
    return GIVE_UP;
  }

  var strategies = [
    goNorthAsLongAsPossible,
    goSouthAsLongAsPossible,
    goNorthToEquator,
    goWestAsLongAsPossible,
    goEastAsLongAsPossible,
    fill
  ];
  var moveQueue = [];
  function determineHeading(wasLastMoveSuccessful) {
    if (wasLastMoveSuccessful !== undefined) {
      var triedPosition = move(currentPosition, triedHeading);
      world[triedPosition] = wasLastMoveSuccessful ? OWNED : BLOCKED;
      if (wasLastMoveSuccessful === true) {
        currentPosition = triedPosition;
        currentHeading = triedHeading;
        updateExtrema(triedPosition);
      }
    }

    if (moveQueue.length > 0) {
      return moveQueue.shift();
    } else {
      if (!currentStrategy) {
        currentStrategy = strategies.shift();
        wasLastMoveSuccessful = undefined;
        if (!currentStrategy) {
          return GIVE_UP;
        }
      }
      var heading = currentStrategy(wasLastMoveSuccessful, moveQueue);
      if (!heading) {
        currentStrategy = null;
        heading = determineHeading(undefined);
      }
      return heading;
    }
  }

  function tryMove(wasLastMoveSuccessful) {
    return (triedHeading = determineHeading(wasLastMoveSuccessful));
  }

  onmessage = function(event) {
    var eventData = event.data;
    var heading = tryMove(eventData.done);
    if (heading) {
      postMessage({
        id: eventData.id,
        direction:
          heading === NORTH ? 'up' :
          heading === EAST ? 'right' :
          heading === SOUTH ? 'down' :
          heading === WEST ? 'left' : 'none'
      });
    }
  };
})();