42
\$\begingroup\$

The contest is over!

Intro

This is an interactive contest where the controller is fully contained in a Stack Snippet at the bottom of the question. The controller automatically reads the answers and plays through games. Anyone can run it at any time right in their browser.

The mechanics of this contest are very similar to those of Red vs. Blue - Pixel Team Battlebots. Except the game being played, while still grid based, is entirely different. Each game is 1 vs. 1 and there are no teams. Each entry is fighting for itself and only one will be the final champion.

The controller uses JavaScript, and as JavaScript is the only client-side scripting language most browsers support, all answers must be written in JavaScript too.

In this spec, italicized text is used to indicate the formal term for a game mechanic or property. These terms are used throughout to help maintain a cohesive and clear way of referring to the different parts of the game.

Gameplay

Basics

Every answer to this question represents a player. A game is a competition between two players, P1 and P2. Each player controls a flock of 8 bots, numbered 0 through 7. Games takes place in the grid, a 128×64 cell arena whose bottom 8 rows start out as walls (the 'blocks') and other rows start as air. Cells outside the grid bounds are considered air.

The grid's x coordinate ranges from 0 on the left to 127 on the right, and y ranges from 0 at the top to 63 at the bottom.

Sample starting grid:

Bots always stay aligned to the grid cells and multiple bots may occupy the same cell. Bots can only occupy air cells. P1's bots always start in a line 0-7 at the very left of the row above the walls and P2's bots always start in a line 7-0 at the very right.

The neighbors of a bot or cell are the 8 cells directly orthogonal and diagonal to it.

The field of view (FOV) of a bot is the 13×13 cell square centered on a bot. A cell or enemy bot is said to be in a player's FOV if it is in the FOV of at least one of the player's bots.

Moves & Actions

During a game, each player gets to move 1000 times. P1 moves first, then P2, then P1 and so on until 2000 total moves have been made, at which point the game ends.

During a move, each player receives information about the game state and the grid cells and enemy bots in their FOV, and uses it to decide on an action for each of their bots to take.

The default action is do nothing, where the bot does not move or interact with the grid.

The other actions are move, grab, and place:

  • A bot can move to one of its neighboring cells C if:

    • C is not out of bounds,
    • C is air (i.e. not a wall),
    • and at least one of C's neighbors is a wall.

    If successful, the bot will move to C.

  • A bot can grab one of its neighboring cells C if:

    • C is not out of bounds,
    • C is a wall,
    • and the bot is not already carrying a wall.

    If successful, C will become air and the bot will now be carrying a wall.

  • A bot can place to one of its neighboring cells C if:

    • C is not out of bounds,
    • C is air,
    • no bots of either player occupy C,
    • and the bot is carrying a wall.

    If successful, C will become a wall and the bot will no longer be carrying a wall.

Unsuccessful actions result in a do nothing.

A cell occupied by at least one wall-carrying bot has a small wall-colored square drawn over it. Bots start without walls.

Memory

During a move, a player can access and change their memory, an initially empty string that lasts throughout the game and can be used to store strategic data.

Goal

The cell in the yellow crosshair is the goal, which starts in a random position. Each player has a score that starts at 0. When a player's bot moves to the goal, that player's score increases by 1 and the goal is randomly repositioned before the next turn. The player with the highest score at the end of a game wins. It's a tie if the scores are equal.

If multiple bots move to the goal during a move, the player still only gets one point.

If the goal has been in the same place for 500 moves, it is randomly repositioned again. Any time the goal is randomly positioned, it is guaranteed to not be placed on a cell occupied by a bot.

What to Program

Write a body for this function:

function myMove(p1, id, eid, move, goal, grid, bots, ebots, getMem, setMem) {
    //body goes here
}

It will be called once every time your player moves and needs to return the actions you want each of your bots to take during that move.

You can use the Baseline code as a starting point.

Parameters

  • p1 is a bool that's true if you are P1 and false if you are P2
  • id is an integer that is the answer ID of your answer.
    • You can find the ID of an answer by clicking the 'share' link below it and looking for the number right after a/ in the URL.
    • The ID of the Test Entry is -1.
  • eid is an integer that is the answer ID of your enemy's answer.
  • move is an integer from 1 to 1000 that says what move you are on.
  • goal is an object with x and y properties. These are the goal's coordinates. They are given even if the goal is out of your FOV.
  • grid is a function that takes in x and y arguments, e.g. grid(x,y). It returns:
    • -1 for 'unknown' if the arguments aren't two integers or if x,y is not in your FOV.
    • 0 for 'air' if x,y is out of bounds or if the cell at x,y is air.
    • 1 for 'wall' if the cell at x,y is a wall.
  • bots is an array of your 8 bots. Its elements are objects with properties x, y, and hasWall:

    • x and y are the bot's coordinates.
    • hasWall is true if the bot is carrying a wall and false if not.

    bots is always ordered normally, the Nth index corresponds to bot number N.

  • ebots is an array of objects with x, y, and hasWall properties just like bots. Only the enemy bots in your FOV are in ebots. So it would have length 0 if if there are no enemy bots in your FOV. It is ordered randomly.
  • getMem is a function with no arguments that returns your memory.
  • setMem is a function that takes one argument M. If M is a string of 256 characters or less, your memory is updated to M, otherwise nothing happens.

The browser console object is available for the Test Entry alone.

Return Value

Your function needs to return an array of exactly 8 integers, each ranging from 0 to 24. The value at index N is the action that bot number N will take.

All your bots will do nothing if your function:

  • Throws an error of any kind. (error)
  • Takes longer than 20 milliseconds to execute. (timeout)
  • Doesn't return an array of 8 integers ranging from 0 to 24. (malformed)

For convenience, the number of errors, timeouts, and malformed actions are displayed when a game ends.

Each of the numbers from 0 to 24 corresponds to a particular bot action:

  • 0 is for doing nothing.
  • 1-8 are for moving.
  • 9-16 are for grabbing.
  • 17-24 are for placing.

Each of the 8 values for moving, grabbing, and placing corresponds to one of the bot's neighboring cells, as shown here:

So, for example, 15 is the action for grabbing the cell below the bot.

Bot actions are handled in the order bot 0 to bot 7. For example, if during one move bot 0 is told to place a wall in the same air cell bot 1 was told to move to, the air cell will become a wall before bot 1's action is handled and bot 1 will be unsuccessful.

Unsuccessful actions become do nothings and are said to have failed. Failed action counters are also displayed when the game ends.

Rules

I may temporarily or permanently disqualify users or answers that don't follow these rules. Disqualified entries are not eligible to win.

  • When declaring variables or functions, you must use the var keyword.
    e.g. var x = 10 or var sum = function(a, b){ return a + b }
    Things declared without var become global and could interfere with the controller. Steps have been taken so that this interference should be impossible, but do this to make sure.

  • Your code shouldn't run slowly or waste time.
    It's impossible to stop JavaScript functions mid-execution, so each player's code is run to completion. If your code takes a long time to run, everyone running your player will notice and be annoyed. Ideally, entries will always run well within the 20ms limit.

  • You must use code compatible with ECMAScript 5 in the latest version of Firefox as this is where I'll be running it. Do not use features from ECMAScript 6 as it is not yet supported in many browsers.
  • You may answer up to 3 times, but only if each of your strategies is considerably different. You can edit answers as much as desired.
  • You may not attempt to have any sort of memory except through the use of getMem and setMem.
  • You may not attempt to access or modify the controller, other player's code, or external resources.
  • You may not attempt to modify anything built into JavaScript.
  • Answers need not be deterministic. You may use Math.random.

Answer Format

#EntryName

Notes, etc.

<!-- language: lang-js -->

    //function body
    //probably on multiple lines

More notes, etc.

The first multiline code block must contain your function body.
The entry name is limited to 20 characters.

Your entry will show up in the controller with the title EntryName - Username [answer ID], plus [DQ] if it's disqualified.

Winning

When the question has been up for at least 3 weeks and once answering has settled down, I will crown the champion.

I'll use the controller's autorun feature. In an autorun round, every non-disqualified player plays two games with every other, one as P1, one as P2 (a double round-robin).

I'll autorun as many rounds as I can in the period of a few hours. This will depend on how many submissions there are and how time intensive they are. But rest assured, I'm committed to getting an accurate final leaderboard. The player with the most wins is the champion and their answer will be accepted.

I'll be using Firefox on a laptop with Windows 8.1 64-bit, 4 GB ram, and a 1.6GHz quad-core processor.

Prize

I will write and post a PPCG challenge specifically dedicated to the champion. It will somehow involve their username or avatar or something about them. I'll privately decide on what the challenge will be about when this contest is over. I'll write it to the best of my ability and try to make sure it becomes a Hot Network Question.

Controller

Run this snippet or go to this JSFiddle to use the controller. It starts with random players selected. I've only thoroughly tested it in Firefox and Chrome.

<style>html *{font-family:Consolas,Arial,sans-serif}canvas{margin:6px}button,input table,select{font-size:100%}textarea{font-family:monospace}input[type=text],textarea{padding:2px}textarea[readonly]{background-color:#eee}select{width:250pt;margin:3px 0}input[type=radio]{vertical-align:-.25em}input[type=checkbox]{vertical-align:-.15em}.c{margin:12px}.h{font-size:125%;font-weight:700}#main td{padding:12px;text-align:left}#main table{margin-left:auto;margin-right:auto}#main{text-align:center}#title{margin:12px;font-size:175%;font-weight:700;color:#333}#delay{text-align:right}#statsTable table{border-collapse:collapse}#statsTable td{border:1px solid gray;padding:3pt;font-family:monospace;text-align:center}#footnotes{margin:18px 0 0;font-size:75%}#arWrapper{border:2px solid red;background-color:#fff4f4}</style><div id=loadStatus>Loading entries...</div><div id=main><div id=title>Block Building Bot Flocks</div><div><span id=p1Title class=p1Color></span> vs. <span id=p2Title class=p2Color></span></div><canvas id=canvas>Canvas unsupported!</canvas><div><span id=p1Score class=p1Color>0</span> | <span id=moveCounter>0</span> | <span id=p2Score class=p2Color>0</span></div><div class=c><button id=runPause type=button onclick=runPause()>Run</button> <button id=moveOnce type=button onclick=moveOnce()>Move Once</button> <button type=button onclick=newGame()>New Game</button></div><div class=c><input id=delay size=4 value=20> ms delay <input id=showNumbers type=checkbox onclick=toggleNumbers()><label for=showNumbers>Show bot numbers</label>&nbsp;<input id=showLOS type=checkbox onclick=toggleLOS()><label for=showLOS>Show field of view</label></div><table><tr><td><div id=p1Header class="p1Color h">Player 1</div><div><select id=p1Select onchange=changeSelect(!0)></select></div><div><a id=p1Link href=javascript:;>Answer Link</a></div><td><div id=p2Header class="p2Color h">Player 2</div><div><select id=p2Select onchange=changeSelect(!1)></select></div><div><a id=p2Link href=javascript:;>Answer Link</a></div></table><div>Test Entry</div><div><textarea id=testEntry rows=8 cols=64>return [0,0,0,0,0,0,0,0]</textarea></div><div class=c><button type=button onclick=autorun()>Autorun N Rounds</button> N&nbsp;=&nbsp;<input id=N size=4 value=1> <input id=arTestEntry type=checkbox><label for=arTestEntry>Include Test Entry</label></div><div id=footnotes><input id=debug type=checkbox onclick=toggleDebug()><label for=debug>Console debug messages</label>&nbsp;| Scale: <input id=sc1 type=radio name=sc value=1><label for=sc1>Micro</label><input id=sc3 type=radio name=sc value=3><label for=sc3>Small</label><input id=sc6 type=radio name=sc value=6 checked><label for=sc6>Normal</label><input id=sc9 type=radio name=sc value=9><label for=sc9>Large</label>&nbsp;| Colors: <input id=normalCo type=radio name=co value=normal checked><label for=normalCo>Normal</label><input id=pastelCo type=radio name=co value=pastel><label for=pastelCo>Pastels</label><input id=neonCo type=radio name=co value=neon><label for=neonCo>Neon</label>&nbsp; <button type=button onclick=reload()>Reload</button><div id=invalidWrapper><br>No entry name/code found: <span id=invalid></span></div></div></div><div id=arWrapper><div id=arInfo class=c>Autorun in progress. Running game <span id=arProgress></span>.</div><div id=arResults><div class="c h">Autorun Results</div><div class=c>Players: <span id=arPlayers></span><br>Rounds: <span id=arRounds></span><br>Games per round: <span id=arGpR></span><br>Total games: <span id=arTotal></span><br></div><div class=c><strong>Leaderboard:</strong></div><div id=leaderboard class=c></div><div class=c>(W = wins, T = ties, L = losses, G = total goals, E = errors, I = timeouts, M = malformed actions, F = failed actions)</div><div class=c><strong>Player vs. Player Statistics:</strong></div><div id=statsTable class=c></div><div class=c>The top row has the ID's of P1.<br>The left column has the ID's of P2.<br>Every other cell not on the diagonal has the form "[P1 win count] [tie count] [P2 win count]".</div><div class=c><button type=button onclick=closeAutorun()>Close</button></div></div></div><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><script>function setGlobals(e){G={},G.QID=50690,G.SITE="codegolf",G.DQ_ANSWERS=[],G.DQ_USERS=[],G.DEBUG=Q("#debug").is(":checked"),G.SHOW_NUMBERS=Q("#showNumbers").is(":checked"),G.SHOW_LOS=Q("#showLOS").is(":checked"),G.BOTS=8,G.LOS=6,G.W=128,G.H=64,G.SCALE=e?6:parseInt(Q('input[name="sc"]:checked').val()),G.CW=G.SCALE*G.W,G.CH=G.SCALE*G.H,G.TOTAL_MOVES=2e3,G.GOAL_LIFESPAN=500,G.MEM_MAX_LENGTH=256,G.TIME_LIMIT=20;var t=Q('input[name="co"]:checked').val();e||"normal"===t?G.COLORS={AIR:"#ccc",WALL:"#888",GOAL:"rgba(255,255,0,0.6)",BG:"#f7f7f7",P1:"#00f",P1_TEXT:"#008",P1_LOS:"rgba(0,0,255,0.1)",P2:"#f00",P2_TEXT:"#800",P2_LOS:"rgba(255,0,0,0.1)"}:"pastel"===t?G.COLORS={AIR:"#cef0ff",WALL:"#66cc66",GOAL:"rgba(0,0,0,0.3)",BG:"#fdfde6",P1:"#f4a034",P1_TEXT:"#a35f00",P1_LOS:"rgba(255,179,71,0.2)",P2:"#f67cf6",P2_TEXT:"#b408b4",P2_LOS:"rgba(249,128,249,0.2)"}:"neon"===t&&(G.COLORS={AIR:"#000",WALL:"#444",GOAL:"rgba(255,255,0,0.9)",BG:"#999",P1:"#0f0",P1_TEXT:"#5f5",P1_LOS:"rgba(255,128,0,0.15)",P2:"#f0f",P2_TEXT:"#f5f",P2_LOS:"rgba(0,255,255,0.15)"}),G.SCOREBOARD={P1SCORE:void 0,MOVE:void 0,P2SCORE:void 0},G.CTX=void 0,G.PLAYERS=void 0,G.GAME=void 0,G.TIMER=void 0,G.RUNNING=!1}function reload(){var e="undefined"==typeof G;e||stopTimer(),setGlobals(e);var t=Q("#canvas");t.width(G.CW).height(G.CH).prop({width:G.CW,height:G.CH}),G.CTX=t[0].getContext("2d"),G.CTX.font=(2*G.SCALE).toString()+"px Courier New",G.SCOREBOARD.P1SCORE=Q("#p1Score"),G.SCOREBOARD.MOVE=Q("#moveCounter"),G.SCOREBOARD.P2SCORE=Q("#p2Score"),Q("body").css("background-color",G.COLORS.BG),Q(".p1Color").css("color",G.COLORS.P1),Q(".p2Color").css("color",G.COLORS.P2),Q("#invalidWrapper").hide(),Q("#arWrapper").hide(),loadAnswers(G.SITE,G.QID,function(e){Q.isArray(e)?(Q("#loadStatus").remove(),loadPlayers(e),newGame()):Q("#loadStatus").text("Error loading entries - "+e)})}function maskedEval(e,t){var r={};for(i in this)r[i]=void 0;for(i in t)t.hasOwnProperty(i)&&(r[i]=t[i]);return new Function("with(this) { "+e+";}").call(r)}function toKey(e,t){return G.W*t+e}function fromKey(e){return{x:e%G.W,y:Math.floor(e/G.W)}}function outOfBounds(e,t){return 0>e||e>=G.W||0>t||t>=G.H}function rnd(e){return Math.floor(Math.random()*e)}function isInt(e){return"number"==typeof e&&e%1===0}function isString(e){return"string"==typeof e||e instanceof String}function decode(e){return Q("<textarea>").html(e).text()}function shuffle(e){for(var t,r,o=e.length;o;t=rnd(o),r=e[--o],e[o]=e[t],e[t]=r);}function makeTable(e){for(var t=Q("<table>"),r=0;r<e.length;r++){for(var o=Q("<tr>"),a=0;a<e[r].length;a++)o.append(Q("<td>").text(e[r][a]));t.append(o)}return t}function toggleDebug(){G.DEBUG=Q("#debug").is(":checked")}function toggleNumbers(){G.SHOW_NUMBERS=Q("#showNumbers").is(":checked"),drawGame(G.GAME)}function toggleLOS(){G.SHOW_LOS=Q("#showLOS").is(":checked"),drawGame(G.GAME)}function closeAutorun(){Q("#arWrapper").hide(),Q("#main").show()}function changeSelect(e){var t=Q(e?"#p1Select":"#p2Select").val(),r=Q(e?"#p1Link":"#p2Link");null===t&&0>t?r.attr("href","javascript:;"):r.attr("href",G.PLAYERS[t].link)}function stopTimer(){"undefined"!=typeof G.TIMER&&clearInterval(G.TIMER)}function moveOnce(){gameOver(G.GAME)||(moveGame(G.GAME),drawGame(G.GAME),gameOver(G.GAME)&&(stopTimer(),Q("#runPause").text("Run").prop("disabled",!0),Q("#moveOnce").prop("disabled",!0),G.DEBUG&&console.log("======== GAME OVER: "+G.GAME.p1.score+" TO "+G.GAME.p2.score+" ========"),alert(gameOverMessage(G.GAME))))}function runPause(){if(G.RUNNING)stopTimer(),Q("#runPause").text("Run"),Q("#moveOnce").prop("disabled",!1);else{var e=parseInt(Q("#delay").val());if(isNaN(e)||0>e)return void alert("Delay must be a non-negative integer.");Q("#runPause").text("Pause"),Q("#moveOnce").prop("disabled",!0),G.TIMER=setInterval(moveOnce,e)}G.RUNNING=!G.RUNNING}function newGame(){stopTimer();var e=G.PLAYERS[Q("#p1Select").val()],t=G.PLAYERS[Q("#p2Select").val()];G.RUNNING=!1,Q("#runPause").text("Run").prop("disabled",!1),Q("#moveOnce").prop("disabled",!1),Q("#p1Title").text(e.title),Q("#p2Title").text(t.title),G.GAME=createGame(e,t),drawGame(G.GAME)}function tryParse(e,t){var r=parseInt(Q(e).val());return!isNaN(r)&&r>=0?r:void alert(t+" must be a non-negative integer.")}function autorun(){function e(){for(var e=new Array(a.length),t={},r=["wins","goals","errors","timeouts","malformed","invalid"],n=0;n<e.length;n++){t.wins=t.ties=t.losses=t.goals=t.errors=t.timeouts=t.malformed=t.invalid=0;for(var l=0;l<e.length;l++)n!==l&&(t.ties+=s[n][l].ties+s[l][n].ties,t.losses+=s[n][l].p2.wins+s[l][n].p1.wins,r.forEach(function(e){t[e]+=s[n][l].p1[e]+s[l][n].p2[e]}));e[n]={wins:t.wins,text:a[n].title+" : "+t.wins+"W, "+t.ties+"T, "+t.losses+"L, "+t.goals+"G, "+t.errors+"E, "+t.timeouts+"I, "+t.malformed+"M, "+t.invalid+"F"}}e=e.sort(function(e,t){return t.wins-e.wins}).map(function(t,r){return r+1+". "+t.text+(r<e.length-1?"<br>":"")});for(var i=new Array(s.length+1),G=0;G<i.length;G++){i[G]=new Array(s.length+1);for(var c=0;c<i.length;c++){var f;i[G][c]=0===c&&0===G?"P2\\P1":0===c?a[G-1].id:0===G?a[c-1].id:(f=s[c-1][G-1])?f.p1.wins+" "+f.ties+" "+f.p2.wins:"-"}}Q("#arPlayers").text(a.length),Q("#arRounds").text(o),Q("#arGpR").text(S/o),Q("#arTotal").text(S),Q("#leaderboard").empty().append(e),Q("#statsTable").empty().append(makeTable(i)),Q("#arInfo").hide(),Q("#arResults").show()}function t(e,t){for(var r=createGame(a[e],a[t]);!gameOver(r);)moveGame(r);r.p1.score>r.p2.score?s[e][t].p1.wins++:r.p1.score<r.p2.score?s[e][t].p2.wins++:s[e][t].ties++,["p1","p2"].forEach(function(o){s[e][t][o].goals+=r[o].score,s[e][t][o].errors+=r[o].stats.errors,s[e][t][o].timeouts+=r[o].stats.timeouts,s[e][t][o].malformed+=r[o].stats.malformed,s[e][t][o].invalid+=r[o].stats.invalid.reduce(function(e,t){return e+t},0)})}function r(){if(c!==f&&(t(c,f),++p<=S&&Q("#arProgress").text(p+"/"+S)),f+1<a.length)f++;else if(f=0,c+1<a.length)c++;else{if(c=0,!(o>i+1))return void e();i++}setTimeout(r,0)}var o=parseInt(Q("#N").val());if(isNaN(o)||1>o)return void alert("N must be a positive integer.");var a=[];Q("#arTestEntry").is(":checked")&&a.push(G.PLAYERS[0]);for(var n=1;n<G.PLAYERS.length;n++)G.PLAYERS[n].dq||a.push(G.PLAYERS[n]);for(var s=new Array(a.length),n=0;n<a.length;n++){s[n]=new Array(a.length);for(var l=0;l<a.length;l++)n!==l&&(s[n][l]={ties:0,p1:{wins:0,goals:0,errors:0,timeouts:0,malformed:0,invalid:0},p2:{wins:0,goals:0,errors:0,timeouts:0,malformed:0,invalid:0}})}var i=0,c=0,f=0,p=1,S=o*a.length*(a.length-1);Q("#arProgress").text("1/"+S),Q("#main").hide(),Q("#arInfo").show(),Q("#arResults").hide(),Q("#arWrapper").show(),setTimeout(r,0)}function gameOver(e){return e.move>=G.TOTAL_MOVES}function gameOverMessage(e){function t(e,t){return"P"+(t?1:2)+": "+e.entry.title+"\nScore: "+e.score+"\nErrors: "+e.stats.errors+"\nTimeouts: "+e.stats.timeouts+"\nMalformed actions: "+e.stats.malformed+"\nFailed actions: ["+e.stats.invalid.toString().replace(/,/g,", ")+"]"}var r="GAME OVER - ";return r+=e.p1.score>e.p2.score?"PLAYER 1 WINS":e.p1.score<e.p2.score?"PLAYER 2 WINS":"TIE GAME",r+="\n\n"+t(e.p1,!0)+"\n\n"+t(e.p2,!1)}function createGame(e,t){function r(e){return{entry:e,bots:new Array(G.BOTS),mem:"",score:0,stats:{errors:0,timeouts:0,malformed:0,invalid:Array.apply(null,new Array(G.BOTS)).map(Number.prototype.valueOf,0)}}}var o={},a=Math.floor(.875*G.H)-1;o.move=0,o.walls=new Array(G.H);for(var n=0;n<G.H;n++){o.walls[n]=new Array(G.W);for(var s=0;s<G.W;s++)o.walls[n][s]=n>a}o.p1=r(e),o.p2=r(t);for(var l=0;l<G.BOTS;l++)o.p1.bots[l]={x:l,y:a,hasWall:!1},o.p2.bots[l]={x:G.W-1-l,y:a,hasWall:!1};if(-1===o.p1.entry.id||-1===o.p2.entry.id){var i=decode(Q("#testEntry").val());-1===o.p1.entry.id&&(o.p1.entry.code=i),-1===o.p2.entry.id&&(o.p2.entry.code=i)}return resetGoal(o),G.DEBUG&&console.log("======== NEW GAME: "+o.p1.entry.title+" VS "+o.p2.entry.title+" ========"),o}function moveGame(e){movePlayer(e,++e.move%2===1),++e.goal.age>=G.GOAL_LIFESPAN&&resetGoal(e)}function setupParams(e,t){function r(e,t){var r=toKey(e,t);if(!n.hasOwnProperty(r)){n[r]=!1;for(var a=0;a<G.BOTS;a++)if(Math.abs(o.bots[a].x-e)<=G.LOS&&Math.abs(o.bots[a].y-t)<=G.LOS){n[r]=!0;break}}return n[r]}var o=t?e.p1:e.p2,a=t?e.p2:e.p1,n={},s={};s.p1=t,s.id=o.entry.id,s.eid=a.entry.id,s.score=o.score,s.escore=a.score,s.move=Math.floor((e.move+1)/2),s.goal={x:e.goal.x,y:e.goal.y},s.getMem=function(){return o.mem},s.setMem=function(e){isString(e)&&e.length<=G.MEM_MAX_LENGTH&&(o.mem=e)},s.grid=function(t,o){return isInt(t)&&isInt(o)&&r(t,o)?outOfBounds(t,o)?0:e.walls[o][t]?1:0:-1},s.bots=new Array(G.BOTS),s.ebots=[];for(var l=0;l<G.BOTS;l++)s.bots[l]={x:o.bots[l].x,y:o.bots[l].y,hasWall:o.bots[l].hasWall},r(a.bots[l].x,a.bots[l].y)&&s.ebots.push({x:a.bots[l].x,y:a.bots[l].y,hasWall:a.bots[l].hasWall});return shuffle(s.ebots),-1===o.entry.id&&(s.console=console),s}function movePlayer(e,t){var r,o,a=t?e.p1:e.p2,n=t?e.p2:e.p1,s=setupParams(e,t);G.DEBUG&&(console.log("######## MOVE "+e.move+" - P"+(t?1:2)+" ########"),console.log("PARAMETERS:"),console.log(s)),o=performance.now();try{r=maskedEval(a.entry.code,s)}catch(n){return a.stats.errors++,void(G.DEBUG&&(console.log("!!!! ERRORED !!!!"),console.log(n)))}if(o=performance.now()-o,G.DEBUG&&console.log("TIME TAKEN: "+o+"ms"),o>G.TIME_LIMIT)return a.stats.timeouts++,void(G.DEBUG&&console.log("!!!! TIMED OUT !!!!"));if(G.DEBUG&&(console.log("ACTIONS:"),console.log(r)),!Array.isArray(r)||r.length!==G.BOTS)return a.stats.malformed++,void(G.DEBUG&&console.log("!!!! MALFORMED ACTIONS !!!!"));for(var l=0;l<G.BOTS;l++)if(!isInt(r[l])||r[l]<0||r[l]>24)return a.stats.malformed++,void(G.DEBUG&&console.log("!!!! MALFORMED ACTIONS !!!!"));performActions(e,a,r)}function performActions(e,t,r){function o(e){t.stats.invalid[e]++,G.DEBUG&&console.log("!! BOT"+e+" ACTION FAILED !!")}function a(e){return e.x!==i||e.y!==c}for(var n=!1,s=0;s<G.BOTS;s++){var l=r[s];if(l){var i,c;switch((l-1)%8){case 0:i=-1,c=-1;break;case 1:i=0,c=-1;break;case 2:i=1,c=-1;break;case 3:i=-1,c=0;break;case 4:i=1,c=0;break;case 5:i=-1,c=1;break;case 6:i=0,c=1;break;case 7:i=1,c=1}if(i+=t.bots[s].x,c+=t.bots[s].y,outOfBounds(i,c))o(s);else switch(Math.floor((l-1)/8)){case 0:!e.walls[c][i]&&(i>0&&c>0&&e.walls[c-1][i-1]||c>0&&e.walls[c-1][i]||i<G.W-1&&c>0&&e.walls[c-1][i+1]||i>0&&e.walls[c][i-1]||i<G.W-1&&e.walls[c][i+1]||i>0&&c<G.H-1&&e.walls[c+1][i-1]||c<G.H-1&&e.walls[c+1][i]||i<G.W-1&&c<G.H-1&&e.walls[c+1][i+1])?(t.bots[s].x=i,t.bots[s].y=c,i!==e.goal.x||c!==e.goal.y||n||(n=!0,G.DEBUG&&console.log("** BOT"+s+" REACHED GOAL **"))):o(s);break;case 1:e.walls[c][i]&&!t.bots[s].hasWall?(e.walls[c][i]=!1,t.bots[s].hasWall=!0):o(s);break;case 2:!e.walls[c][i]&&t.bots[s].hasWall&&e.p1.bots.every(a)&&e.p2.bots.every(a)?(e.walls[c][i]=!0,t.bots[s].hasWall=!1):o(s)}}}n&&(t.score++,resetGoal(e)),G.DEBUG&&(console.log("FINAL PLAYER STATE:"),console.log(t))}function resetGoal(e){for(var t={},r=[],o=0;o<G.BOTS;o++)t[toKey(e.p1.bots[o].x,e.p1.bots[o].y)]=!0,t[toKey(e.p2.bots[o].x,e.p2.bots[o].y)]=!0;for(var a=0;a<G.H;a++)for(var n=0;n<G.W;n++){var s=toKey(n,a);t.hasOwnProperty(s)||r.push(s)}var l=fromKey(r[rnd(r.length)]);e.goal={age:0,x:l.x,y:l.y}}function drawGame(e){function t(e,t){G.CTX.fillRect(e*G.SCALE,t*G.SCALE,G.SCALE,G.SCALE)}function r(e,t){G.CTX.fillRect(e*G.SCALE+1,t*G.SCALE+1,G.SCALE-2,G.SCALE-2)}G.CTX.fillStyle=G.COLORS.AIR,G.CTX.fillRect(0,0,G.CW,G.CH),G.CTX.fillStyle=G.COLORS.WALL;for(var o=0;o<G.H;o++)for(var a=0;a<G.W;a++)e.walls[o][a]&&t(a,o);if(G.SHOW_LOS){var n=(2*G.LOS+1)*G.SCALE;G.CTX.fillStyle=G.COLORS.P1_LOS;for(var s=0;s<G.BOTS;s++)G.CTX.fillRect((e.p1.bots[s].x-G.LOS)*G.SCALE,(e.p1.bots[s].y-G.LOS)*G.SCALE,n,n);G.CTX.fillStyle=G.COLORS.P2_LOS;for(var s=0;s<G.BOTS;s++)G.CTX.fillRect((e.p2.bots[s].x-G.LOS)*G.SCALE,(e.p2.bots[s].y-G.LOS)*G.SCALE,n,n)}G.CTX.fillStyle=G.COLORS.P1;for(var s=0;s<G.BOTS;s++)t(e.p1.bots[s].x,e.p1.bots[s].y);G.CTX.fillStyle=G.COLORS.P2;for(var s=0;s<G.BOTS;s++)t(e.p2.bots[s].x,e.p2.bots[s].y);G.CTX.fillStyle=G.COLORS.WALL;for(var s=0;s<G.BOTS;s++)e.p1.bots[s].hasWall&&r(e.p1.bots[s].x,e.p1.bots[s].y),e.p2.bots[s].hasWall&&r(e.p2.bots[s].x,e.p2.bots[s].y);if(G.SHOW_NUMBERS){var l=-.1,i=2.75;G.CTX.fillStyle=G.COLORS.P1_TEXT;for(var s=0;s<G.BOTS;s++)G.CTX.fillText(s.toString(),(e.p1.bots[s].x+l)*G.SCALE,(e.p1.bots[s].y+i)*G.SCALE);G.CTX.fillStyle=G.COLORS.P2_TEXT;for(var s=0;s<G.BOTS;s++)G.CTX.fillText(s.toString(),(e.p2.bots[s].x+l)*G.SCALE,(e.p2.bots[s].y+i)*G.SCALE)}G.CTX.fillStyle=G.COLORS.GOAL,t(e.goal.x+1,e.goal.y),t(e.goal.x-1,e.goal.y),t(e.goal.x,e.goal.y+1),t(e.goal.x,e.goal.y-1),G.SCOREBOARD.P1SCORE.text(e.p1.score),G.SCOREBOARD.MOVE.text(e.move),G.SCOREBOARD.P2SCORE.text(e.p2.score)}function loadPlayers(e){var t=/<pre\b[^>]*><code\b[^>]*>([\s\S]*?)<\/code><\/pre>/,r=/<h1\b[^>]*>(.*?)<\/h1>/;G.PLAYERS=[];var o={id:-1,dq:!1,code:void 0,link:"javascript:;",title:"TEST ENTRY [-1]"};G.PLAYERS.push(o);var a=[];e.forEach(function(e){var o=decode(e.owner.display_name),n=t.exec(e.body),s=r.exec(e.body);if(null===n||n.length<=1||null===s||s.length<=1)return a.push(" "),void a.push(Q("<a>").text(o).attr("href",e.link));var l={};l.id=e.answer_id,l.dq=G.DQ_ANSWERS.indexOf(e.answer_id)>-1||G.DQ_USERS.indexOf(e.owner.user_id)>-1,l.code=decode(n[1]),l.link=e.link,l.title=s[1].substring(0,20)+" - "+o+" ["+l.id.toString()+"]",l.dq&&(l.title+="[DQ]"),G.PLAYERS.push(l)}),a.length>0&&(Q("#invalid").empty().append(a),Q("#invalidWrapper").show());for(var n=new Array(G.PLAYERS.length),s=new Array(G.PLAYERS.length),l=0;l<G.PLAYERS.length;l++)n[l]=Q("<option>").text(G.PLAYERS[l].title).val(l),s[l]=Q("<option>").text(G.PLAYERS[l].title).val(l);Q("#p1Select").empty().append(n).val(rnd(G.PLAYERS.length)),changeSelect(!0),Q("#p2Select").empty().append(s).val(rnd(G.PLAYERS.length)),changeSelect(!1)}function loadAnswers(e,t,r){function o(){Q.get("https://api.stackexchange.com/2.2/questions/"+t.toString()+"/answers?page="+(s++).toString()+"&pagesize=100&order=asc&sort=creation&site="+e+"&filter=!YOKGPOBC5Yad4mOOn8Z4WcAE6q",a)}function a(e){e.hasOwnProperty("error_id")?r(e.error_id.toString()):(n=n.concat(e.items),e.hasMore?o():r(n))}var n=[],s=1;o(s,a)}Q=jQuery,Q(reload);</script>

This question has its own chatroom. I'll post leaderboards there every few days.

\$\endgroup\$
  • 11
    \$\begingroup\$ +1 Excessively long. \$\endgroup\$ – orlp May 24 '15 at 4:16
  • 3
    \$\begingroup\$ Thanks to the buttons to adjust the size of the grid, I can run the Stack Snippet on my phone :) \$\endgroup\$ – trichoplax May 24 '15 at 20:20
  • 3
    \$\begingroup\$ Lots of love (codegolf.stackexchange.com/questions/50768/) but that's not easy \$\endgroup\$ – edc65 May 26 '15 at 14:12
  • 3
    \$\begingroup\$ This is mesmerizing to watch. \$\endgroup\$ – DLosc May 27 '15 at 15:55
  • 1
    \$\begingroup\$ @Stephen Yes. Rule bullet 4: "You can edit answers as much as desired." \$\endgroup\$ – Calvin's Hobbies May 28 '15 at 12:53
13
\$\begingroup\$

Black Knight

The bot's name comes from an early plan to have it be able to move like a chess knight: over two, up one, etc, which would be faster in some cases.

var moves = new Array(8),
    mem = getMem(), newMem = '';

var decodeMem = function(){
  //mmtxy
  for(var ind = 0; ind < 8; ind++){
    var sub = mem.substr(ind * 5, 5)
    bots[ind].lastMove = parseInt(sub[0], 36);
    bots[ind].last2Move = parseInt(sub[1], 36);
    bots[ind].timesStill = sub.charCodeAt(2) - 48;
    bots[ind].lastX = sub.charCodeAt(3) - 187;
    bots[ind].lastY = sub.charCodeAt(4) - 187;
  }
}
decodeMem();

var distanceTo = function(fromX, fromY, toX, toY){
  // Chebyshev distance
  return Math.max(Math.abs(fromX - toX),
                  Math.abs(fromY - toY));
}

var direction = function(from, to){ // Math.sign()
  var diff = to - from;
  return diff > 0 ? 1 : (diff < 0 ? -1 : 0);
}

var dirs = [
  [1, 2, 3],
  [4, 0, 5],
  [6, 7, 8]
];

var moveTo = function(from, to){
  var prioritiesWall = [
    [0],
    [1, 2, 4, 17, 18, 20, 19, 22, 23, 21, 3, 6, 5, 7, 24, 8],
    [2, 3, 1, 17, 19, 18, 23, 22, 24, 4, 5, 20, 21, 6, 8, 7],
    [3, 2, 5, 19, 18, 21, 17, 24, 23, 20, 1, 8, 4, 7, 22, 6],
    [4, 1, 6, 22, 17, 20, 21, 24, 19, 2, 7, 18, 23, 3, 8, 5],
    [5, 3, 8, 24, 19, 21, 20, 22, 17, 2, 7, 18, 23, 1, 6, 4],
    [6, 4, 7, 22, 20, 23, 17, 24, 18, 21, 1, 8, 2, 5, 19, 3],
    [7, 8, 6, 22, 24, 23, 18, 17, 19, 4, 5, 20, 21, 1, 3, 2],
    [8, 5, 7, 24, 21, 23, 19, 22, 18, 20, 3, 6, 2, 4, 17, 1]
  ];
  var prioritiesNoWall = [
    [9, 10, 11, 12, 13, 14, 15, 16, 0],
    [1, 2, 4, 9, 16, 10, 12, 3, 6, 11, 14, 5, 7, 13, 15, 8],
    [2, 3, 1, 10, 15, 14, 16, 4, 5, 12, 13, 9, 11, 6, 8, 7],
    [3, 2, 5, 11, 14, 10, 13, 1, 8, 9, 16, 4, 7, 12, 15, 6],
    [4, 1, 6, 12, 13, 16, 11, 2, 7, 10, 15, 9, 14, 3, 8, 5],
    [5, 3, 8, 13, 12, 14, 9, 2, 7, 10, 15, 11, 16, 1, 6, 4],
    [6, 4, 7, 14, 11, 12, 15, 1, 8, 9, 16, 2, 5, 10, 13, 3],
    [7, 8, 6, 15, 10, 9, 11, 4, 5, 12, 13, 14, 16, 1, 3, 2],
    [8, 5, 7, 16, 9, 13, 15, 3, 6, 11, 14, 2, 4, 10, 12, 1]
  ];

  var dir = dirs[direction(from.y, to.y) + 1][direction(from.x, to.x) + 1],
      method = from.hasWall ? prioritiesWall[dir] : prioritiesNoWall[dir];

  if(distanceTo(from.x, from.y, goal.x, goal.y) === 1){
    method.splice(1,2);
  }

  for(var i=0; i<method.length; i++){
    var attempt = method[i];
    if(checkMove(from, attempt)) return attempt;
  }
  return 0;
}

var numWalls = function(x, y, indexes){
  var allCoords = [
    [x - 1, y - 1],
    [x,     y - 1],
    [x + 1, y - 1],
    [x - 1, y    ],
    [x + 1, y    ],
    [x - 1, y + 1],
    [x,     y + 1],
    [x + 1, y + 1],
  ];
  var allTypes = allCoords.map(function(e){
    return grid(e[0], e[1]); // air = 0, wall = 1
  });
  var justWalls = allTypes.filter(function(e){
    return e === 1;
  }).length;

  return indexes ? allTypes : justWalls;
}

var checkMove = function(coords, moveCode){
  var x = coords.x, y = coords.y,
      baseX = [0, -1, 0, 1, -1, 1, -1, 0, 1],
      baseY = [0, -1, -1, -1, 0, 0, 1, 1, 1],
      targetX = x + baseX[(moveCode - 1) % 8 + 1],
      targetY = y + baseY[(moveCode - 1) % 8 + 1];

  if((targetX > 127 || targetX < 0 || targetY > 63 || targetY < 0) || // Don't bother if it's out of bounds
     (coords.timesStill > 2 && x == coords.lastX && y == coords.lastY && (moveCode == coords.lastMove || moveCode == coords.last2Move)))
    // Or is doing the same moves and not moving
    return false;

  var targetGrid = grid(targetX, targetY), enemyNear = false, couldStrandEnemy = false,
      eWallDirMove, hasNeighbor = numWalls(targetX, targetY) > 0;

  ebots.forEach(function(ebot){
    // Don't place a wall where an enemy can take it
    if(distanceTo(targetX, targetY, ebot.x, ebot.y) === 1 && !ebot.hasWall && (y != ebot.y || x != ebot.x))
      enemyNear = true;

    // Don't move if you can strand an enemy
    var eWallDir = numWalls(ebot.x, ebot.y, true).indexOf(1) + 1,
        wallX = ebot.x + baseX[eWallDir], wallY = ebot.y + baseY[eWallDir];

    if(!coords.hasWall && numWalls(ebot.x, ebot.y) === 1 &&
       distanceTo(x, y, wallX, wallY) === 1){
      eWallDirMove = dirs[direction(y, wallY) + 1][direction(x, wallX) + 1] + 8;
      couldStrandEnemy = true;
    }
  })

  if(targetX == goal.x && targetY == goal.y && targetGrid === 0){
    targetGrid = 2 // Don't place a wall in the goal
  } else {
    ebots.concat(bots).forEach(function(bot){
      // Ensure target cell doesn't have a bot in it
      if(bot.x == targetX && bot.y == targetY) targetGrid = 2;
    });
  }

  return ((moveCode < 9 && targetGrid !== 1 && hasNeighbor && !couldStrandEnemy) || // Move
          (moveCode > 8 && moveCode < 17 && targetGrid === 1 && !coords.hasWall && (!couldStrandEnemy || (couldStrandEnemy && eWallDirMove == moveCode))) || // Grab
          (moveCode > 16 && targetGrid === 0 && coords.hasWall && !enemyNear)) // Place
}

var goalClosest = {dist: Infinity}, rescuers = {};
bots.forEach(function(bot, index){

  // Check if bot is stranded
  bot.stranded = false;
  if(numWalls(bot.x, bot.y) / 8 == bot.hasWall){
    bot.stranded = true;
    rescuers[index] = -1;
  }
});

bots.forEach(function(bot, index){
  if(!bot.stranded){
    // Find which bot is closest to the goal
    var goalDist = distanceTo(bot.x, bot.y, goal.x, goal.y);

    if(goalDist < goalClosest.dist){
      goalClosest.dist = goalDist;
      goalClosest.index = index;
    }
  }
});

bots.forEach(function(bot, index){
  var destination = {
    x: 14 + (index % 4) * 32 + 3 * (index > 3),
    y: index > 3 ? 55 : 27
  }
  if(index == goalClosest.index){
    destination = goal;
  }

  moves[index] = moveTo(bot, destination);

  if(moves[index] == bot.lastMove || moves[index] == bot.last2Move) bot.timesStill++;

  newMem += moves[index].toString(36) +
    bot.lastMove.toString(36) +
    String.fromCharCode(bot.timesStill + 48) +
    String.fromCharCode(bot.x + 187) +
    String.fromCharCode(bot.y + 187);
});

setMem(newMem);

return moves;

Explanation

Determining which move to make for each bot can be divided into two main tasks: figuring out where to go and how to get there.

Where to go

The basic task of figuring out where to go is easy: go towards the goal if you're closest, or otherwise try to position yourself as far away from teammates. It first goes through each bot and determines if it is stranded (i.e. it has no blocks surrounding it and isn't holding a wall, or it is surrounded by walls and holds a wall). It then loops through the bots again to find the non-stranded bot closest to the goal. All other bots make their way towards being spaced out, with the bottom row on the surface of the blocks (y=55) and the top row at y=27. Once it knows where to go, it hands it off to the moveTo function.

How to get there

Deciding how to get to the destination is far more difficult because the bots must always be adjacent to a wall to move. It first figures out the direction code (1–8) of the destination relative to its current position. For example, if a bot were at the bottom-left corner and it wanted to go to the top right, it would use the direction code 3. For each direction, I hardcoded a list of moves, with the first being the ideal, top-priority move, and the last being the last resort. This is separated by whether or not the bot has a wall, because you cannot use a place move without a wall or use a grab move while already having a wall.

Of course, using the ideal move doesn't always work, and it would result in a lot of failed actions. This is where checkMove comes in. This function checks the potential move against every requirement, to prevent the bot from moving out of bounds or into a wall, for example. If a nearby enemy bot can be stranded (it has only one adjacent wall that can be taken by the bot), that becomes its priority, so the function will return false for an otherwise legitimate move so it can skip to the grab moves and take out the enemy. The function prevents several other stupid moves like placing a wall in the goal or another bot.

The memory string

Sometimes the bot will not be actually stranded but will keep trying the same move and not end up moving (usually picking up a wall and putting it down, picking it up and putting it down, etc). To prevent this, it uses the memory string to remember its last two moves, its last x and y position, and how many times it has been still. Each datum is encoded as a single character for easy splitting. (The string has to be 256 characters, not bytes, so using multibyte Unicode characters isn't a problem, as it is with typical golfing challenges.)

For example, say a bot grabbed the wall on its left (code 12) this turn, replaced it to its left (code 20) in its previous turn, and has been at the coordinates (107, 3) for the past 16 turns. The memory string for this instance would be encoded as follows:

  • ck: The two latest action codes are converted to base36 to make the two-digit numbers a single letter.
  • @: The number of times it has been still is represented as the ASCII character with that code + 48 to skip over unprintable characters and so the first nine times still shows the actual number (String.fromCharCode(0 + 48)0).
  • Ħ¾: The x and y coordinates are also represented as as the character with that value, this time offset by the somewhat-arbitrary value of 187 to avoid problematic characters.

A typical memory string during the game might be 53äÇØb7¼ðÌ00ßĉÖ7m±ĪÚ00ĝÌò00Ĝìò00ĖČò00ĈĬò, with a group of five characters for each of the eight bots.

\$\endgroup\$
  • 1
    \$\begingroup\$ If a player is in a game against itself, then either Player 1 or Player 2 can win, with no apparent bias. This answer is the exception, as Player 1 nearly always wins by a large margin. I can't see a reason why - it's intriguing. \$\endgroup\$ – trichoplax May 29 '15 at 21:28
  • \$\begingroup\$ @trichoplax I imagine it's because P1 moves before P2, so P1 will strand P2 before it can do the same. \$\endgroup\$ – NinjaBearMonkey May 29 '15 at 22:15
  • 4
    \$\begingroup\$ The challenge is over and the results are in! After 30 rounds, Black Knight had 204 wins, and the next best entry, Seekers, only had 147. Congratulations NinjaBearMonkey! The you specific challenge is on the way. \$\endgroup\$ – Calvin's Hobbies Jun 16 '15 at 0:02
  • \$\begingroup\$ Absolutely ninja! Thank you \$\endgroup\$ – edc65 Jun 18 '15 at 22:47
12
\$\begingroup\$

Outposts

The 8 bots each take a 32 by 32 square and run to the centre of it (I offset the centres slightly otherwise they end up pairing up and travelling vertically with one wall block between them, so one of them gets stranded).

Each bot will stay in the centre of its square unless the goal is within 32 cells of its respective centre, in which case it will run to the goal and then back to its centre.

This still uses the Baseline method of reaching its target (goal or centre) so does not move diagonally. Just a starting point...

var encodeAction = function(type, dx, dy) {
    var d
    if (dx === -1 && dy === -1) d = 1
    else if (dx === 0 && dy === -1) d = 2
    else if (dx === 1 && dy === -1) d = 3
    else if (dx === -1 && dy === 0) d = 4
    else if (dx === 1 && dy === 0) d = 5
    else if (dx === -1 && dy === 1) d = 6
    else if (dx === 0 && dy === 1) d = 7
    else if (dx === 1 && dy === 1) d = 8
    else return 0
    return 8 * type + d
}

var getNeighborCell = function(x, y, wallState) {
    if (x > 0 && y > 0 && grid(x - 1, y - 1) === wallState) return { x: x - 1, y: y - 1 }
    if (y > 0 && grid(x, y - 1) === wallState) return { x: x, y: y - 1 }
    if (x < 127 && y > 0 && grid(x + 1, y - 1) === wallState) return { x: x + 1, y: y - 1 }
    if (x > 0 && grid(x - 1, y) === wallState) return { x: x - 1, y: y }
    if (x < 127 && grid(x + 1, y) === wallState) return { x: x + 1, y: y }
    if (x > 0 && y < 63 && grid(x - 1, y + 1) === wallState) return { x: x - 1, y: y + 1 }
    if (y < 63 && grid(x, y + 1) === wallState) return { x: x, y: y + 1 }
    if (x < 127 && y < 63 && grid(x + 1, y + 1) === wallState) return { x: x + 1, y: y + 1 }
    return null
}

var moveBot = function(n) {
    var assignedX = (n % 4) * 32 + 14 + Math.floor(n/4) * 4
    var assignedY = (Math.floor(n / 4)) * 32 + 16
    if (Math.abs(goal.x - assignedX) < 33 && Math.abs(goal.y - assignedY) < 33) {
        assignedX = goal.x
        assignedY = goal.y
    }
    var b = bots[n], moveX = b.x !== assignedX, x = b.x, y = b.y, type
    if (moveX) {
        x += b.x < assignedX ? 1 : -1
    } else {
        y += b.y < assignedY ? 1 : -1
    }
    if (grid(x, y) === 1) {
        if (b.hasWall) {
            type = 2 //place
            var c = getNeighborCell(b.x, b.y, 0)
            if (!c) { //stuck holding wall with walls all around
                return 0
            }
            x = c.x
            y = c.y
        } else {
            type = 1 //grab
        }
    } else if (grid(x, y) === 0) {
        if (getNeighborCell(x, y, 1)) {
            type = 0 //move
        } else {
            if (b.hasWall) {
                type = 2 //place
                if (moveX) {
                    y += y > 0 ? -1 : 1
                } else {
                    x += x > 0 ? -1 : 1
                }
            } else {
                type = 1 //grab
                var c = getNeighborCell(b.x, b.y, 1)
                if (!c) { //stuck without wall in midair
                    return 0
                }
                x = c.x
                y = c.y
            }
        }
    } else {
        return 0 //should never get here
    }
    return encodeAction(type, x - b.x, y - b.y)
}

var actions = []
for (var i = 0; i < 8; i++) {
    actions[i] = moveBot(i)
}

return actions
\$\endgroup\$
  • 1
    \$\begingroup\$ I know this is just the start, but one thing I noticed while watching the (uneven) battle with the baseline: If the goal is within reach of multiple centers, they all run towards the goal. Might be better to only choose the closest one, and keep the others at their "ideal" position? Fun to watch, btw. \$\endgroup\$ – Reto Koradi May 24 '15 at 15:54
  • \$\begingroup\$ Thanks! Yes that would definitely be an improvement. There's a long list of others to think about too, and a variety of different strategies to use. I'm looking forward to seeing which strategies others choose and how they interact... \$\endgroup\$ – trichoplax May 24 '15 at 19:04
9
\$\begingroup\$

Baseline

This is the simplest consistently functioning bot flock controller I could think of. It will be my only non-disqualified answer and will serve as a baseline to judge other answers by. It is technically in the running to win the contest, but beating it should not be difficult.

Any of the code here may be copied and used in another answer, no attribution required.

var encodeAction = function(type, dx, dy) {
    var d
    if (dx === -1 && dy === -1) d = 1
    else if (dx === 0 && dy === -1) d = 2
    else if (dx === 1 && dy === -1) d = 3
    else if (dx === -1 && dy === 0) d = 4
    else if (dx === 1 && dy === 0) d = 5
    else if (dx === -1 && dy === 1) d = 6
    else if (dx === 0 && dy === 1) d = 7
    else if (dx === 1 && dy === 1) d = 8
    else return 0
    return 8 * type + d
}

var getNeighborCell = function(x, y, wallState) {
    if (x > 0 && y > 0 && grid(x - 1, y - 1) === wallState) return { x: x - 1, y: y - 1 }
    if (y > 0 && grid(x, y - 1) === wallState) return { x: x, y: y - 1 }
    if (x < 127 && y > 0 && grid(x + 1, y - 1) === wallState) return { x: x + 1, y: y - 1 }
    if (x > 0 && grid(x - 1, y) === wallState) return { x: x - 1, y: y }
    if (x < 127 && grid(x + 1, y) === wallState) return { x: x + 1, y: y }
    if (x > 0 && y < 63 && grid(x - 1, y + 1) === wallState) return { x: x - 1, y: y + 1 }
    if (y < 63 && grid(x, y + 1) === wallState) return { x: x, y: y + 1 }
    if (x < 127 && y < 63 && grid(x + 1, y + 1) === wallState) return { x: x + 1, y: y + 1 }
    return null
}

var moveBot = function(n) {
    var b = bots[n], moveX = b.x !== goal.x, x = b.x, y = b.y, type
    if (moveX) {
        x += b.x < goal.x ? 1 : -1
    } else {
        y += b.y < goal.y ? 1 : -1
    }
    if (grid(x, y) === 1) {
        if (b.hasWall) {
            type = 2 //place
            var c = getNeighborCell(b.x, b.y, 0)
            if (!c) { //stuck holding wall with walls all around
                return 0
            }
            x = c.x
            y = c.y
        } else {
            type = 1 //grab
        }
    } else if (grid(x, y) === 0) {
        if (getNeighborCell(x, y, 1)) {
            type = 0 //move
        } else {
            if (b.hasWall) {
                type = 2 //place
                if (moveX) {
                    y += y > 0 ? -1 : 1
                } else {
                    x += x > 0 ? -1 : 1
                }
            } else {
                type = 1 //grab
                var c = getNeighborCell(b.x, b.y, 1)
                if (!c) { //stuck without wall in midair
                    return 0
                }
                x = c.x
                y = c.y
            }
        }
    } else {
        return 0 //should never get here
    }
    return encodeAction(type, x - b.x, y - b.y)
}

var actions = []
for (var i = 0; i < 8; i++) {
    actions[i] = moveBot(i)
}

return actions

Each of the 8 bots independently follows the same basic method. They tend to clump together because of this, unless they get separated by something external. The bots never care about where teammates or enemies are, they only attempt to move toward the goal. They only move orthogonally, first matching their x with the goal x, then their y. Never moving diagonally means they waste a lot of time in travel.

The movement algorithm of each bot is as follows:

If my X is not equal to the goal's X
    P = position to my left or right that is closer to the goal  
    Make a note that I'm trying to move horizontal  
Else  
    P = position above or below me that is closer to the goal  
    Make a note that I'm trying to move vertical  

If P is a wall  
    If I'm holding a wall  
        Place my wall in any neighboring air cell  
    Else  
        Grab the wall at P  
Else if P is air  
    If P has a wall neighboring it (i.e. if I can move to P)  
        Move to P  
    Else  
        If I'm holding a wall  
            If I'm trying to move horizontal  
                Place my wall above or below P  
            Else if I'm trying to move vertical  
                Place my wall to the left or right of P  
        Else  
            Grab wall from any neighboring wall cell   
\$\endgroup\$
6
\$\begingroup\$

Teamplayer

At the moment, this submission is far from perfect. It has a similar strategy like Outposts, but only 6 bots are "in the air". The other 2 bots supply them with walls if they got stolen. Edit: The supporter bots perform much better now.

var outside = function(x,y) {
    return x < 0 || x > 127 || y < 0 || y > 127
}

var distance = function(x1, y1, x2, y2){
  return Math.sqrt(Math.pow(x1-x2, 2) + Math.pow(y1-y2, 2));
}

var isStuck = function(bot) {
    if (bot.hasWall) {
        for (var i=-1; i<=1; i++) {
            for (var j=-1; j<=1; j++) {
                if ((i != 0 || j != 0) && grid(bot.x+i,bot.y+j) == 0 && !outside(bot.x+i,bot.y+j))
                    return false
            }
        }
        return true
    }
    for (var i=-1; i<=1; i++) {
        for (var j=-1; j<=1; j++) {
            if (grid(bot.x+i, bot.y+j) == 1)
                return false
        }
    }
    return true
}

var isPlayer = function(x,y) {
    for (var i = 0; i < bots.length; i++) {
        if (bots[i].x == x && bots[i].y == y)
            return true
    }
    for (var i = 0; i < ebots.length; i++) {
        if (ebots[i].x == x && ebots[i].y == y)
            return true
    }
    return false
}

var encodeAction = function(type, dx, dy) {
    var d
    if (dx === -1 && dy === -1) d = 1
    else if (dx === 0 && dy === -1) d = 2
    else if (dx === 1 && dy === -1) d = 3
    else if (dx === -1 && dy === 0) d = 4
    else if (dx === 1 && dy === 0) d = 5
    else if (dx === -1 && dy === 1) d = 6
    else if (dx === 0 && dy === 1) d = 7
    else if (dx === 1 && dy === 1) d = 8
    else return 0
    return 8 * type + d
}

var surrounding = function(x,y) {
    var cell = {hasStone:false, cells: []}
    for (var i=-1; i<=1; i++) {
        for(var j=-1; j<=1; j++) {
            if ((i != 0 || j != 0) && !outside(x+i,y+j)) {
                cell.cells.push({x:x+i, y:y+j})
                if (grid(x+i,y+j) == 1) {
                    cell.hasStone = true
                }
            }
        }
    }
    return cell
}


var hunt = function(i, destination) {
    destination = destination || {x: 31+((i-2)%3)*32, y: 20+((i-2)%2)*21}, bot = bots[i]
    if (i < 5 && i > 1) {
        destination.x -= 2
    }
    if (bot.isStuck) {
        return 0
    }
    if ((p1 && destination.x >= move + i) || (!p1 && 127 - destination.x > move - i)) {
        destination.y = bot.y
    }
    if (i == bestBotId && move > 50) {
        destination.x = goal.x
        destination.y = goal.y
    }
    var dx = destination.x > bot.x ? 1 : destination.x == bot.x ? 0 : -1, newX = bot.x + dx
    var dy = destination.y > bot.y ? 1 : destination.y == bot.y ? 0 : -1, newY = bot.y + dy
    var surr = surrounding(newX, newY), botSurr = surrounding(bot.x, bot.y)
    if (grid(newX, newY) == 0) {
        if (surr.hasStone) {
            return encodeAction(0, dx, dy)
        } else {
            if (bot.hasWall) {
                for (var i=0; i<surr.cells.length; i++) {
                    var cell = surr.cells[i];
                    if (Math.abs(cell.x - bot.x) <= 1 && Math.abs(cell.y - bot.y) <= 1 && grid(cell.x, cell.y) == 0 && !isPlayer(cell.x, cell.y)) {
                        return encodeAction(2, cell.x - bot.x, cell.y - bot.y)
                    }
                }
            } else {
                if (bot.walls.length == 1) {
                    return encodeAction(1, bot.walls[0].x - bot.x, bot.walls[0].y - bot.y)
                } else {
                    for (var i=0; i<bot.walls.length; i++) {
                        var wall = bot.walls[i], canUseWall = true
                        for (var j=0; j<bots.length; j++) {
                            if (bots[j].walls.length == 1 && bots[j].walls[0].x == wall.x && bots[j].walls[0].y == wall.y) {
                                canUseWall = false
                            }
                        }
                        if (canUseWall) {
                            return encodeAction(1, wall.x - bot.x, wall.y - bot.y)
                        }
                    }
                }
            }
        }
    } else {
        if (bot.hasWall) {
            for (var i=0; i<botSurr.cells.length; i++) {
                var cell = botSurr.cells[i];
                if (grid(cell.x, cell.y) == 0 && !isPlayer(cell.x, cell.y) && !outside(cell.x, cell.y)) {
                    return encodeAction(2, cell.x - bot.x, cell.y - bot.y)
                }
            }
        } else {
            return encodeAction(1, dx, dy)
        }
    }
    return 0 //hopefully never happens
}

var help = function(i) {
    if (bots[i].isStuck) {
        return 0
    }
    var bot = bots[i], destination = helpDestinations[i]
    if (destination.stuckBot == -1) {
        if (bot.walls.length >= 2 || (bot.hasWall && bot.walls.length == 1)) {
            var stuckId = -1
            for (var j = 0; j < bots.length; j++) {
                if (j != helpDestinations[(i+1)%2].stuckBot && bots[j].isStuck)
                    stuckId = j
            }
            if (stuckId != -1) {
                destination.stuckBot = stuckId
                destination.x = bots[stuckId].x
                destination.y = bots[stuckId].y
                return 0
            } else {
                return hunt(i, destination)
            }
        } else if (bot.x == destination.x && bot.y == destination.y) {
            if (move % 2 == 0)
                destination.y += 1
            else
                destination.x -= 1
            return hunt(i, destination)
        } else {
            return hunt(i, destination)
        }
    } else if (bots[destination.stuckBot].isStuck) {
        if (bot.walls.length < 2 && !(bot.hasWall && bot.walls.length == 1)) {
            destination.stuckBot = -1
            destination.x = i == 0 ? 42 : 85
            destination.y = 55
            return hunt(i, destination)
        }
        var dx = destination.x > bot.x ? 1 : destination.x == bot.x ? 0 : -1, newX = bot.x + dx
        var dy = destination.y > bot.y ? 1 : destination.y == bot.y ? 0 : -1, newY = bot.y + dy
        var surr = surrounding(newX, newY), botSurr = surrounding(bot.x, bot.y), surrWalls = 0
        for (var i = 0; i < surr.cells.length; i++) {
            var cell = surr.cells[i]
            if (grid(cell.x,cell.y) == 1)
                surrWalls++
        }
        if (grid(newX, newY) == 0) {
            if (surrWalls >= 2 || (surr.hasWall && bot.hasWall)) {
                return encodeAction(0, dx, dy)
            } else {
                if (bot.hasWall) {
                    for (var i=0; i<surr.cells.length; i++) {
                        var cell = surr.cells[i];
                        if (Math.abs(cell.x - bot.x) <= 1 && Math.abs(cell.y - bot.y) <= 1 && grid(cell.x, cell.y) == 0 && !isPlayer(cell.x, cell.y)) {
                            return encodeAction(2, cell.x - bot.x, cell.y - bot.y)
                        }
                    }
                } else {
                    if (bot.walls.length == 1) {
                        return encodeAction(1, bot.walls[0].x - bot.x, bot.walls[0].y - bot.y)
                    } else {
                        for (var i=0; i<bot.walls.length; i++) {
                            var wall = bot.walls[i], canUseWall = true
                            for (var j=0; j<bots.length; j++) {
                                if (bots[j].walls.length == 1 && bots[j].walls[0].x == wall.x && bots[j].walls[0].y == wall.y) {
                                    canUseWall = false
                                }
                            }
                            for (var j=0; j<surr.cells.length; j++) {
                                if (surr.cells[j].x == wall.x && surr.cells[j].y == wall.y)
                                    canUseWall = false
                            }
                            if (canUseWall) {
                                return encodeAction(1, wall.x - bot.x, wall.y - bot.y)
                            }
                        }
                    }
                }
            }
        } else {
            if (bot.hasWall) {
                for (var i=0; i<botSurr.cells.length; i++) {
                    var cell = botSurr.cells[i];
                    if (grid(cell.x, cell.y) == 0 && !isPlayer(cell.x, cell.y)) {
                        return encodeAction(2, cell.x - bot.x, cell.y - bot.y)
                    }
                }
            } else {
                return encodeAction(1, dx, dy)
            }
        }
    } else {
        destination.stuckBot = -1
        destination.x = i == 0 ? 42 : 85
        destination.y = 55
        return hunt(i, destination)
    }
    return 0 //hopefully never happens
}

var moves = new Array(8)    
var mem = getMem(), helpDestinations = []
if (mem.length == 0) {
    mem = "42,55,-1 85,55,-1"
}
mem = mem.split(" ")
for (var i = 0; i < mem.length; i++) {
    var cell = mem[i].split(",")
    helpDestinations.push({x: parseInt(cell[0]), y: parseInt(cell[1]), stuckBot: parseInt(cell[2])})
}

for (var i = 0; i < 8; i++) {
    var bot = bots[i]
    var surr = surrounding(bot.x, bot.y)
    bot.walls = []
    for (var j = 0; j < surr.cells.length; j++) {
        if (grid(surr.cells[j].x, surr.cells[j].y) == 1) {
            bot.walls.push(surr.cells[j])
        }
    }
}

bots.forEach(function(bot, index) {
    if(isStuck(bot)) {
        bot.isStuck = true
    }
})

var bestDistance = 1000
var bestBotId = -1
for (var i=2; i<8; i++) {
    var dist = distance(bots[i].x, bots[i].y, goal.x, goal.y)
    if (dist < bestDistance && !bots[i].isStuck) {
        bestDistance = dist
        bestBotId = i
    }
}

for (var i=0; i<8; i++) {
    if (i < 2) {
        moves[i] = help(i)
    } else {
        moves[i] = hunt(i)  
    }
}

setMem(helpDestinations[0].x + "," + helpDestinations[0].y + "," + helpDestinations[0].stuckBot + " " + helpDestinations[1].x + "," + helpDestinations[1].y + "," + helpDestinations[1].stuckBot)

return moves
\$\endgroup\$
  • \$\begingroup\$ The supporter idea (nice) seems difficult to implement. \$\endgroup\$ – edc65 May 28 '15 at 9:06
  • \$\begingroup\$ @edc65 It is basically just moving with 2 walls instead of one. But the communication between the two support bots and finding new walls was rather hard to implement :) \$\endgroup\$ – CommonGuy May 28 '15 at 9:12
6
\$\begingroup\$

Seekers

Stll work in progress. I have many ideas, but almost none of them do work.

Above all, big problem with failed actions. Solved!

var action=[], myGrid=[], goalSort=[], i, j, curBot, curAction, goalSeek;

var check = function(x,y) {
  return (myGrid[[x,y]] || (myGrid[[x,y]] = grid(x,y)))|0;
};

var setGrid = function(x,y,v) {
  myGrid[[x,y]] = v + '';
};

var orGrid = function(x,y,v) {
  myGrid[[x,y]] |= v;
};

var encodeDir = function(dx, dy) {
    return dx < 0 && dy < 0 ? 1
    : dx === 0 && dy < 0 ? 2
    : dx > 0 && dy < 0 ? 3
    : dx < 0 && dy === 0 ? 4
    : dx > 0 && dy === 0 ? 5
    : dx < 0 && dy > 0 ? 6
    : dx === 0 && dy > 0 ? 7
    : dx > 0 && dy > 0 ? 8
    : 0;
};

var distance = function(p1, p2) {
  return Math.max(Math.abs(p1.x-p2.x),Math.abs(p1.y-p2.y));
};

var cellNearWall = function(x,y)
{
  var r = check(x,y) == 1 ? 0
  : check(x-1,y-1) == 1 ? 1
  : check(x,y-1) == 1 ? 2
  : check(x+1,y-1) == 1 ? 3
  : check(x-1,y) == 1 ? 4
  : check(x+1,y) == 1 ? 5
  : check(x-1,y+1) == 1 ? 6
  : check(x,y+1) == 1 ? 7
  : check(x+1,y+1) == 1 ? 8
  : 0;
  return r;
};

var cellNearBot = function(x,y,m)
{
  return check(x-1,y-1) & m ? 1
  : check(x,y-1) & m ? 2
  : check(x+1,y-1) & m ? 3
  : check(x-1,y) & m ? 4
  : check(x+1,y) & m ? 5
  : check(x-1,y+1) & m ? 6
  : check(x,y+1) & m ? 7
  : check(x+1,y+1) & m ? 8
  : 0;
};


var tryGrabWall = function(x, y)
{
  var dx, dy, r = 8;
  for(dy = -1; dy < 2; ++dy)
  {
    for(dx = -1; dx < 2; ++dx)
    {
      if (dx|dy)
      {
        ++r;
        if (check(x+dx, y+dy) == 1)
        {
          setGrid(x+dx, y+dy, 0); // remember that the wall is not there anymore
          return r;
        }
      }
    }
  }
  return 0;
};

var tryDropWall= function(x, y)
{
  var dx, dy, r = 16;
  for(dy = -1; dy < 2; ++dy)
  {
    for(dx = -1; dx < 2; ++dx)
    {
      if (dx|dy)
      {
        ++r;
        if (x+dx>=0 & x+dx < 128 & y+dy >= 0 & y+dy < 64 && check(x+dx, y+dy) == 0)
        {
          setGrid(x+dx, y+dy, 1); // remember that the wall is there 
          return r;
        }
      }
    }
  }
  return 0;
};


var approach = function(bot, target)
{
  var dx, dy, tx, ty, r = 0, wallPos;

  var checkDrop = function(dx,dy)
  {
    var x = bot.x+dx, y = bot.y+dy;
    if (check(x,y) == 0 && cellNearBot(x,y,8) == 0)
    {
      setGrid(x, y, 1);
      return 16 + encodeDir(dx, dy);
    }
  };

  dy = target.y - bot.y;
  dy = dy < 0 ? -1 : dy > 0 ? 1 : 0;
  dx = target.x - bot.x;
  dx = dx < 0 ? -1 : dx > 0 ? 1 : 0;
  tx = bot.x+dx;
  ty = bot.y+dy;

  if ((dx|dy) === 0)
  {
    if (!bot.hasWall) {
      return tryGrabWall(bot.x, bot.y);
    }
    return 0;
  }


  if (cellNearWall(tx,ty))
  {
    setGrid(tx, ty, 2);
    return encodeDir(dx, dy);
  }

  if (dx === 0)
  {
    if (cellNearWall(bot.x-1,ty))
    {
      setGrid(bot.x-1, ty, 2);
      return encodeDir(-1, dy);
    }
    if (cellNearWall(bot.x+1,ty))
    {
      setGrid(bot.x+1, ty, 2);
      return encodeDir(1, dy);
    }
    if (bot.hasWall) 
    {
      if (wallPos = checkDrop(1,dy)) { return wallPos; }
      if (wallPos = checkDrop(-1,dy)) { return wallPos; }
      if (wallPos = checkDrop(1,0)) { return wallPos; }
      if (wallPos = checkDrop(-1,0)) { return wallPos; }
    }
  }
  else if (dy === 0) 
  {
    if (cellNearWall(tx,bot.y-1))
    {
      setGrid(tx, bot.y-1, 2);
      return encodeDir(dx, -1);
    }
    if (cellNearWall(tx,bot.y+1))
    {
      setGrid(tx, bot.y+1, 2);
      return encodeDir(dx, 1);
    }
    if (bot.hasWall) 
    {
      if (wallPos = checkDrop(dx,1)) { return wallPos; }
      if (wallPos = checkDrop(dx,-1)) { return wallPos; }
      if (wallPos = checkDrop(0,1)) { return wallPos; }
      if (wallPos = checkDrop(0,-1)) { return wallPos; }
    }
  }
  else
  {
    if (cellNearWall(tx,bot.y))
    {
      setGrid(tx, bot.y, 2);
      return encodeDir(dx, 0);
    }
    if (cellNearWall(bot.x,ty))
    {
      setGrid(bot.x, ty, 2);
      return encodeDir(0,dy);
    }
    if (bot.hasWall) {
      if (wallPos = checkDrop(dx,0)) { return wallPos; }
      if (wallPos = checkDrop(0,dy)) { return wallPos; }
      if (wallPos = checkDrop(dx,dy)) { return wallPos; }
    }
  }

  if (!bot.hasWall)
  {
  if (check(tx, ty) == 1)
  {
      setGrid(tx, ty, 0); // remember that the wall is not there anymore
      return 8 + encodeDir(dx, dy);
    };
    return tryGrabWall(bot.x, bot.y);
  }
  else
  {
    return tryDropWall(bot.x, bot.y);
  }
};

for (i=0; curBot=ebots[i]; i++)
{
  setGrid(curBot.x, curBot.y, curBot.hasWall ? 4 : 8);
}

var goalDistance=[]

for (i=0; curBot=bots[i]; i++)
{
  orGrid(curBot.x, curBot.y, 2);
  goalDistance[i] = distance(curBot, goal);
}
var sorted = goalDistance.slice().sort(function(a,b){return a-b})
var ranks = goalDistance.slice().map(function(v){ return sorted.indexOf(v)});

var tt = p1 
? [ { x:32, y:20 },{ x:32, y:55 },{ x:64, y:20 },{ x:64, y:55 },
   { x:96, y:20 },{ x:96, y:55 },{ x:16, y:30 },{ x:112, y:30 }]
: [ { x:96, y:20 },{ x:96, y:55 },{ x:64, y:20 },{ x:64, y:55 },
   { x:32, y:20 },{ x:32, y:55 },{ x:112, y:30 },{ x:16, y:30 }]

var goalSeek = 3;

for (i=0; curBot=bots[i]; i++)
{
  if (ranks[i] < goalSeek)
  {
    curAction = approach(curBot, goal);
    if (curAction == 0) goalSeek += 1;
  }
  else
    curAction = approach(curBot, tt[i]);

  action[i] = curAction;
}

return action;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.