Bot: Outsnake the game!

5

So, I wrote a simple Javascript game (as yet unnamed) and naturally I wanted to write an API so I could write a bot to play it for me, and naturally I wanted to let the PPCG community have a go for themselves.

It's a 'snake' game with the simple goal of collecting as many blue squares as possible while avoiding red squares or the edge of the board. It was initially controlled with a mouse.

Example of gameplay

Find the API edition of the game here: https://ajfaraday.github.io/game_name_here/api.html

Gameplay:

  • Type the code for your bot in the field under 'Your function': This will repeat automatically when you tell it to run.
    • Only in Javascript, sorry.
    • See restrictions, below.
  • You can try it step-wise by clicking 'step'.
  • I suggest you 'Run (fast)' once you have a workable function.
  • Click 'Reset' to try a fresh game.
  • Every 10 points will increase the points per blue square by 1.
  • Every 10 points will increase the red squares spawned by 1.
  • You can lose lives by:
    • Gobbling up a red square (Be aware that, while you lose a life, it also breaks down the wall. Sacrificing lives to break through walls is a legitimate tactic).
    • Attempting to leave the game board.
    • Running down the 'Timeout' clock of 20 seconds between blue squares.
  • You will not lose a life by 'stepping on your tail' in this version.
  • Every 100 points will earn an additional life.
  • Be aware that all coordinates are x, y starting in the top left corner. 0 indexed.

Restrictions:

  • There is no security in this code. Please do not hack the game!
    • Only use standard JS and the API methods described.
    • PLEASE! Don't change API.coord
    • You may not interact directly with Sketch, Cell or other entities defined within the game.

The competition

  • Please give your entry title a short name for your snake.
  • Include your JS code and any explanation you'd like to include.
  • The OP will copy/paste the code into the game, and run it 5 times (using 'Run (fast)').
  • The highest score achieved in those attempts is your score.
  • The OP will add your score to the answer, and to a leader board in the question.
  • You may submit more than one function.

Leader Board

+--------------------------+---------------------------------+----------+
| Username                 | Snake Name                      | Score    |
+--------------------------+---------------------------------+----------+
| orlp                     | Simple A*                       | 595      |
+--------------------------+---------------------------------+----------+

Rendering Issue

This rendering issue has now been fixed and deployed.

Please be aware that if you call more than one of the direction methods during your function, the snake will visit all of the squares and collect points or lose lives accordingly. However, due to a rendering issue, it will only display the ending position of your snake.

Be aware that the snake can not travel diagonally between walls without losing a life.


Responsible disclosure: This is written in pure Javascript, it contains no logging, analytics or other data gathering processes. It's hosted on github pages, typically a trusted home of code.

If you want to confirm this, or would prefer to develop your answer on a locally hosted instance, the code is available here: https://github.com/ajfaraday/game_name_here


This is my first attempt at a competitive non-golf challenge, so I'm open to suggestions about how I could make it more suitable for this kind of situation.

Happy snaking!

AJFaraday

Posted 2018-06-29T08:17:22.097

Reputation: 10 466

1"Running down the 'Timeout' clock of 20 seconds between blue squares." How fast is the snake going, so how many cells can be traveled in those 20 secs from blue to blue? (And I assume the run-fast button, also increases this countdown speed?) – Kevin Cruijssen – 2018-06-29T08:32:41.283

@KevinCruijssen The fast run will call your method every 100 ms. 20 seconds is easily enough time to get from corner to corner. You can also call more than one direction method in your function to go faster (causing the rendering issue mentioned). The time-out is really an objective method of detecting when your snake has become stuck. If it's looping, or sat in one place for 20 seconds per life, it's safe to say that snake is not going to get the blue square. – AJFaraday – 2018-06-29T08:39:18.533

@JoKing Good point, well made. I've finished it off. – AJFaraday – 2018-06-29T08:56:22.330

4I don't think this is [tag:king-of-the-hill] because as far as I can tell the submissions don't interact with each other. – Peter Taylor – 2018-06-29T10:05:22.160

@PeterTaylor Perhaps I've misunderstood the meaning of the tag, how would this kind of challenge be described? – AJFaraday – 2018-06-29T10:06:03.393

1[tag:code-challenge], maybe also [tag:puzzle-solver] although I think that's a stretch for this question. – Peter Taylor – 2018-06-29T10:10:45.087

Can I move multiple squares at a time like let[[x,y],[X,Y]]=[API.coord,API.goal];while(x<X)++x,API.right();while(x>X)--x,API.left();while(y<Y)++y,API.down();while(y>Y)--y,API.up()? (note that it doesn't perform well because it doesn't avoid red squares) – user202729 – 2018-06-29T10:21:31.153

@user202729 Yes, you can, but it's not as good as it sounds. a: The snake visits all the intervening squares, so it will lose lives for walls it passes through. b: The rendering issue will kick in, and you won't be able to see the path of your snake (until I fix that issue). So go ahead, but be aware of the costs. – AJFaraday – 2018-06-29T10:27:00.167

Can red blocks be placed under blue ones? I just faced an issue where a red block and a blue block were placed in the same coordinates – Luis felipe De jesus Munoz – 2018-06-29T13:44:59.003

@LuisfelipeDejesusMunoz That's an issue with the app, on the board itself the blue goal wins out and that space is not also a red wall. It appears the API still adds it to the list of walls, tho. I'll fix it soon. – AJFaraday – 2018-06-29T13:47:02.257

1Was this sandboxed? If not, it should have been – mbomb007 – 2018-06-29T13:49:35.070

@LuisfelipeDejesusMunoz I've fixed and deployed that issue, thank you for the feedback! – AJFaraday – 2018-06-29T13:52:05.537

Another thing I notice is that sometimes blue dots doesn't appear. Check this out

– Luis felipe De jesus Munoz – 2018-06-29T14:01:03.087

@LuisfelipeDejesusMunoz Is it fixed in that position? Could you check if API.goal and API.coord are the same? – AJFaraday – 2018-06-29T14:02:18.217

@AJFaraday sure, next time it happens I check. It just has happened 2 times – Luis felipe De jesus Munoz – 2018-06-29T14:04:42.490

@LuisfelipeDejesusMunoz Thank you! You could also log issues with the github repo: https://github.com/ajfaraday/game_name_here

– AJFaraday – 2018-06-29T14:05:34.660

1

Do you know the leaderboard snippet? It helps automatize the process of making a leaderboard.

– user202729 – 2018-06-29T15:13:31.903

@user202729 interesting, I'll have a proper look at some point, it looks like it might need a bit of time to get used to it. – AJFaraday – 2018-06-29T15:16:28.353

@user202729 You might want to check my earlier comment on that issue, travel time really isn't an issue (10 function calls a second means you have 200 steps time to get around), so multiple calls really doesn't create an advantage (it looks cool, tho). The timeout is basically a way to answer the question "has it had enough time to try and find a route?" more objective. It'll only really kick in when the snake is stuck, or looping, with or without multiple calls. – AJFaraday – 2018-06-29T15:24:31.553

Some rendering bugs: (1) this should remove "wall" class.

– user202729 – 2018-07-01T03:17:08.197

Note: Have you considered the case where a blue/red square spawn on the square the snake is on? – user202729 – 2018-07-01T03:24:51.853

@user202729 Thanks for the feedback! Could you please log the second one as an issue on the github repo? (It’ll take a bit more time than I can give it today, particularly with the two methods of input.) – AJFaraday – 2018-07-01T06:14:43.070

Answers

4

Simple A* - Official score: 595

This solution uses simple A* pathfinding, with no long-term strategy - it always finds the optimal route towards just the next blue square.

var h = function(p, q) {
    // Manhattan distance.
    return Math.abs(p[0] - q[0]) + Math.abs(p[1] - q[1]);
};

var s = JSON.stringify;
var p = JSON.parse;
var walls = API.walls.map(s);
var start = API.coord;
var goal = API.goal;

var is_closed = {};
is_closed[s(start)] = 0;
var open = [s(start)];

var came_from = {};
var gs = {};
gs[s(start)] = 0;
var fs = {};
fs[s(start)] = h(start, goal);

var cur;
while (open.length) {
    var best;
    var bestf = Infinity;
    for (var i = 0; i < open.length; ++i) {
        if (fs[open[i]] < bestf) {
            bestf = fs[open[i]];
            best = i;
        }
    }

    cur = p(open.splice(best, 1)[0]);
    is_closed[s(cur)] = 1;

    if (s(cur) == s(goal)) break;

    for (var d of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
        var next = [cur[0] + d[0], cur[1] + d[1]];
        if (next[0] < 0 || next[0] >= API.width ||
            next[1] < 0 || next[1] >= API.height) {
            continue;
        }

        if (is_closed[s(next)]) continue;
        if (open.indexOf(s(next)) == -1) open.push(s(next));
        var is_wall = walls.indexOf(s(next)) > -1;
        var g = gs[s(cur)] + 1 + 10000 * is_wall;
        if (gs[s(next)] != undefined && g > gs[s(next)]) continue;

        came_from[s(next)] = cur;
        gs[s(next)] = g;
        fs[s(next)] = g + h(next, goal);
    }
}

var path = [cur];
while (came_from[s(cur)] != undefined) {
    cur = came_from[s(cur)];
    path.push(cur);
}

var c = path[path.length - 1];
var n = path[path.length - 2];
if (n[0] < c[0]) {
    API.left();
} else if (n[0] > c[0]) {
    API.right();
} else if (n[1] < c[1]) {
    API.up();
} else {
    API.down();
}

orlp

Posted 2018-06-29T08:17:22.097

Reputation: 37 067

I love this! Particularly how it factors the number of red blocks into the decision making. – AJFaraday – 2018-06-29T14:42:07.877

1This will be pretty hard to beat since almost every pathfinding algorithm is created from this one. Nice solution +1 – Luis felipe De jesus Munoz – 2018-06-29T14:50:28.763

So this will always find the path that need to break least red squares? – user202729 – 2018-06-29T16:10:37.733

@user202729 Yes it does, but only considering the current objective - not thinking ahead at all. – orlp – 2018-06-29T16:23:41.277

This will probably raise some runtime error when the blue square is at the position of the snake. – user202729 – 2018-07-01T03:25:24.737

@user202729 If the blue square is at the position of the snake, we eat the blue square and it spawns somewhere else. – orlp – 2018-07-01T06:20:04.200

I don't think so. (implementation bug? I didn't test it but I believe there is a bug) – user202729 – 2018-07-01T06:25:53.497

@user202729 It's not currently aware of the location of the current square. It should be easily fixable, tho. – AJFaraday – 2018-07-03T08:14:47.637