Skip to content

Instantly share code, notes, and snippets.

@davidaurelio davidaurelio/voidbot.js
Last active Aug 29, 2015

Embed
What would you like to do?
/**
@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'
});
}
};
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.