Self-Playing Snake Game / Simple-Planning Agent

<

Snake Screen View


The following demo/game self-plays a version of the snake game using a goal-based agent called a simple-planning agent. It is recommended that you run the demo/game continuously for a period of time while noting the highest score. As the length of the snake grows, eventually the agent / algorithm reaches a No Operation State (NOP).


Try it here >>   Self-Playing Game/Simple-planning Agent



The self-playing game is a combination of multiple code sources.


Snake Game Code:

The source code is implemented in jQuery/JavaScript. For the source code or to play the game go here: Snake Game .


Path Finding Code:

This code source is a basic path finding algorithm, implemented in JavaScript. It requires an array with a start location, a goal, and grid coordinates. It quickly calculates the shortest path using the Breadth-First Search technique to find the shortest path from "square A" to "square B" along with evading the snake body since it is the obstacle to avoid.

The source code for the search algorithm, along with an excellent description of how it works is found here: Basic Path-finding Algorithm

I created a visualization to demonstrate how the path-finding search works >> Algorithm Visualization.


Simple-Planning Agent Code (Mine):

The simple-planning agent runs against the snake game, and knows the Initial State (Start) and the Goal State (Finish) and uses the basic path finding algorithm (Plan) to obtain a sequence of actions that achieves the given goal. Once the first goal is achieved, a new Initial State and new Goal State are determined based on the current state. As the length of the snake grows, eventually the agent reaches a No Operation State (NOP).



Project Files




Anatomy of the Snake Game


Anatomy of the snake components



snake.html

  
<html>
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
		<meta charset="utf-8">
		<title>Self-playing Snake Game / Simple-Planning Agent</title>
<style type="text/css">
		body { font-family: "Verdana"; font-size:10pt; color:#000000; }
    p {  margin-top: 0px; margin-bottom: 5px; }
</style>
</head>
<body>
	<p id="direction"></p>
	<p id="location"></p>
	<p id="goal"></p>
	<p id="highestscore"></p>
	<br>
<canvas id="canvas" width="450" height="450"></canvas>
<script src="js/jquery.js" type="text/javascript"></script><script src="jquery.js" type="text/javascript"></script>
<script src="js/snake.js" type="text/javascript"></script>
</body>
</html>    
      


snake.js


Snake Game Code

I am not covering the snake game code in depth. Refer to the link provided for more information on how that code works. However, I made modifications to the snake game code as follows so that it would interface with the simple-planning agent code.


Added the variables from line 16 thru line 32

 
//http://thecodeplayer.com/walkthrough/html5-game-tutorial-make-a-snake-game-using-html5-canvas-jquery
$(document).ready(function(){
$(document).ready(function(){
	//Canvas stuff
	var canvas = $("#canvas")[0];
	var ctx = canvas.getContext("2d");
	var w = $("#canvas").width();
	var h = $("#canvas").height();
	
	//Lets save the cell width in a variable for easy control
	var cw = 10;
	var d;
	var food;
	var score;
	//The following are not part of original Snake code
	var grid = []; 
	var starty;
	var startx;
	var goaly;
	var goalx;
	var obstacley;
	var obstaclex;
	var snakepath;
	var displaypath;
	var pathlength;
	var pathstep;
	var foodchanged;
	var foodx;
	var foody;
	var highestscore = 0;
	var removetail;
	var endlength;

Added some code to record the highest score

//ORIGINAL SNAKE GAME CODE(with a few modifications I made) *************************************
	//Lets create the snake now
	var snake_array; //an array of cells to make up the snake
	
	function init()
	{
		d = "right";     //default direction
		
		create_food();   //Now we can see the food particle
		create_snake();                                       
		
//finally lets display the score
    //The following 6 lines are not part of the orignal code	
		if(highestscore < score)  
		{
		highestscore = score;
		} else {
		highestscore = highestscore;
		}                            
		
		score = 0;
		
//Lets move the snake now using a timer which will trigger the paint function
//every 60ms
		if(typeof game_loop != "undefined") clearInterval(game_loop);
		game_loop = setInterval(paint, 60);
	}
	init();
	
	function create_snake()
	{
		var length = 5; //Length of the snake
		snake_array = []; //Empty array to start with
		for(var i = length-1; i>=0; i--)
		{
//This will create a horizontal snake starting from the top left
			snake_array.push({x: i, y:0});
		}
	}

Added a flag called "foodchanged" to signal to the simple-planning agent that the goal has been reached. Anytime the snake reaches the goal (food), the goal is randomly placed to another location on the screen.

//Lets create the food now
	function create_food()
	{
		food = {
			x: Math.round(Math.random()*(w-cw)/cw), 
			y: Math.round(Math.random()*(h-cw)/cw), 
		};
		
//This will create a cell with x/y between 0-44
//Because there are 45(450/10) positions accross the rows and columns
		foodchanged = 1;  //Not part of original code
	}

Beginning of the paint() function. I commented out the lines that redrew the canvas between each loop iteration. I needed the ability to display the newly calculated path that the snake follows to the new goal (food). This is described in further detail below.

//Lets paint the snake now
	function paint()
	{
//To avoid the snake trail we need to paint the BG on every frame
//Lets paint the canvas now
    //I commented out the next two original lines of code, to apply a better solution.
		//ctx.fillStyle = "white";
		//ctx.fillRect(0, 0, w, h);
		ctx.strokeStyle = "black";
		ctx.strokeRect(0, 0, w, h);

I am providing the code below, not because I made modifications, but it provides context on how the control of the snake works in the actual game.

With each up, right, down, left key press the d variable is set by incrementing or decrementing the x or y coordinate by one step.

//The movement code for the snake to come here.
//The logic is simple
//Pop out the tail cell and place it infront of the head cell
		var nx = snake_array[0].x;
		var ny = snake_array[0].y;
//These were the position of the head cell.
//We will increment it to get the new head position
//Lets add proper direction based movement now
		
		if(d == "right") nx++;
		else if(d == "left") nx--;
		else if(d == "up") ny--;
		else if(d == "down") ny++;
	
//Lets add the game over clauses now
//This will restart the game if the snake hits the wall
//Lets add the code for body collision
//Now if the head of the snake bumps into its body, the game will restart
		 
		if(nx == -1 || nx == w/cw || ny == -1 || ny == h/cw || check_collision(nx, ny, snake_array))
		{
//restart game
			init();
//Lets organize the code a bit now.
			return;
		}

The modification beginning at line 138 was to correct an oversight in the original game. The Atari Snake Game had a rule that that food could not spawn on the body of the snake.


Modifications were added beginning at line 152, to clear the tail of the snake as it moves. This was originally handled with lines 93-94, that redrew the entire canvas.

//Lets write the code to make the snake eat the food
//The logic is simple
//If the new head position matches with that of the food,
//Create a new head instead of moving the tail
		if(nx == food.x && ny == food.y)
		{
			var tail = {x: nx, y: ny};
				
			score++;
			create_food();
		
		//The next six lines I added because of an oversight in the original code.
		//The Atari snake game prohibited food spawning on the body of the snake, so I added this as a fix.	
    foodx = food.x;   
    foody = food.y;  
		if(check_collision(foodx, foody, snake_array)) 
		{
		create_food();  
		}  
			
		}
		else
		{
		
		//debugger;
		//The next three lines removes/whites out the tail as the snake moves. The original redrew the entire screen
		//which caused problems drawing other colors
		endlength = snake_array.length-1;       //Not part of original code
		removetail = snake_array[endlength];    //Not part of original code
		var color = "white";       //to erase the trailing snake tail
		paint_cell(removetail.x, removetail.y, color); //Not part of original code
		
		var tail = snake_array.pop(); //pops out the last cell
		tail.x = nx; tail.y = ny;
	
		}

I added code to color the goal (food) red. In the original game it was blue.

I also changed the font color and size of the score. Since the canvas is no longer being redrawn each iteration, I added a white rectangle behind the score to paint over the old score and allow the new score to display as the score changes

//The snake can now eat the food.
		snake_array.unshift(tail); //puts back the tail as the first cell
		
		
			
		for(var i = 0; i < snake_array.length; i++)
		{
			var c = snake_array[i];
//Lets paint 10px wide cells
      var color = "blue";   //I modified this
			paint_cell(c.x, c.y, color);  //I modified this
		}
		
//Lets paint the food
    //paint_cell(food.x, food.y); //Commented out. Part of original code
    ctx.fillStyle = "white";
		ctx.fillStyle = "red"; //Not part of original code, added for troubleshooting purposes
		ctx.fillRect(food.x*cw,food.y*cw,cw,cw);  //Not part of original code
		//ctx.fillStyle = "blue"; //Commented out. Part of original code
		//ctx.fillRect(x*cw, y*cw, cw, cw);  //Commented out. Part of original code
		
//Lets paint the score
    var score_text = "Score: " + score;
    ctx.font = "14px verdana";
    ctx.fillStyle = "black";
    ctx.clearRect(10, 428, 85, 15)
    ctx.fillText(score_text, 10, h-10);


STAGE ONE: Identify new goal (food) and calculate the path

Embedded within the Paint() function is the simple-planning agent code, that plays the snake game.

If the foodchanged flag is set (value of "1") then it is time to recalculate the new path to the new goal (food). Since the canvas is 450 x 450 and the snake is 10 px wide we set the grid to 45. Then for each element in the array set the values to "Empty".

//I ADDED THE FOLLOWING CODE, THAT SELF-PLAYS THE SNAKE GAME***************************************
//The paint() function is called repeatedly with setinterval
//So identify the var food.x food.y location (GOAL) 
//Locate the current snake head location (START)
//then based on the coordinates call keystrokes and set variable d

if(foodchanged == 1) 
{
foodchanged = 0;  

//this is where the snake reaches the food and then the food is moved...
//Initialize the array to set it up for the search algorithm
// Create a 45x45 grid
// Represent the grid as a 2-dimensional array
var gridSize = 45;  //food is placed between 0-44 so 45 was used  
//var grid = [];
for (var g=0; g<gridSize; g++) {
  grid[g] = [];
  for (var j=0; j<gridSize; j++) {
    grid[g][j] = "Empty";   //set intial values to empty
  }
}

The search algorithm requires a "Start", a "Goal", and "Obstacle" written in the array elements that correspond to the position of the snake on the grid. The result is a string that looks like the following: "down,down,down,right,right,up"

Then call the findShortestPath() with parameters of the starting x and y, and the grid array

//SNAPSHOT OF THE START STATE
//set the 'start' as the head of the snake
starty = ny;  
startx = nx;  
grid[starty][startx] = "Start";
//set the food as the 'goal'
goaly = food.y;
goalx = food.x;
grid[goaly][goalx] = "Goal";
//Identify the obstacles -- modifying the snake collision function code to locate the 'obstacles'
for(var s = 0; s < snake_array.length; s++)  
  {
			obstacley = snake_array[s].y;
			obstaclex = snake_array[s].x;
			grid[obstacley][obstaclex] = "Obstacle";
	}
//Here is an example of the grid that is sent to findShortestPath() which is the start point for the search algorithm/code
//grid[0][0] = "Start";
//grid[2][2] = "Goal";
//grid[1][1] = "Obstacle";
//grid[1][2] = "Obstacle";
//grid[1][3] = "Obstacle";
//grid[2][1] = "Obstacle";
//Here are the results that are returned, directions of which way to turn:
//down,down,down,right,right,up
snakepath = findShortestPath([starty, startx], grid); //returns a comma delimited string converted to an array

Using the directions (a comma delimited string converted to an array) returned from findShortestPath() function, color the calculated path silver-gray for visual effect calling the paint_cell() function.

displaypath = snakepath;
for(var i = 0; i < displaypath.length; i++)  
		{
			var p = displaypath[i];
			//Lets paint 10px wide cells
			
		if(p == "right") nx++; 
		else if(p == "left") nx--; 
		else if(p == "up") ny--; 
		else if(p == "down") ny++; 
			var color = 'rgb(192,192,192)'; //to paint the color of the new calculated path silver-gray
			paint_cell(nx, ny, color); 
		}

Move the snake forward one step, and then after this the game loop takes affect and we move to Stage Two.

pathlength =  snakepath.length; 
pathstep = 0; // meaning that we are starting over with a new path to the food
      if (snakepath[pathstep] == "up" ) { d = "up";}		
      if (snakepath[pathstep] == "down" ) { d = "down";}
      if (snakepath[pathstep] == "left" ) { d = "left";}
      if (snakepath[pathstep] == "right" ) { d = "right";}
      pathstep = pathstep + 1;
}

STAGE TWO: Continue to follow instructions (path) to the next Goal stage

For each loop in the paint() function move the snake forward one step at a time toward the goal (food).

else
{
      if ( pathstep < pathlength )
      {
      if (snakepath[pathstep] == "up" ) { d = "up";}		
      if (snakepath[pathstep] == "down" ) { d = "down";}
      if (snakepath[pathstep] == "left" ) { d = "left";}
      if (snakepath[pathstep] == "right" ) { d = "right";}
          pathstep = pathstep + 1;
      }
}
//The following used for troubleshooting purposes
document.getElementById("direction").innerHTML = "Direction = " + d;
document.getElementById("location").innerHTML = "Snakehead Location = y: " + ny + " x: " + nx;
document.getElementById("goal").innerHTML = "Food / Goal = y: " + goaly + " x: " + goalx;
document.getElementById("highestscore").innerHTML = "Highest Score: " + highestscore;
}  
// END MY CODE THAT SELF-PLAYS AGAINST THE SNAKE GAME *********************************************
// END OF THE Paint() FUNCTION ********************************************************************

Lines 280-288 Function which paints cells using specified color in the color parameter. I modified this from the original code.

Lines 289-300 Checks collisions between the snake head and snake body

Lines 302-309 Monitors keyboard controls. We do not use this.

Line 304 I commented out to prevent users from pressing keys while the code is running

/Lets first create a generic function to paint cells
	function paint_cell(x, y, color) //I modified this
	{
		ctx.fillStyle = color;  //I added this                          
		ctx.fillRect(x*cw, y*cw, cw, cw);
		ctx.strokeStyle = "white";
		ctx.strokeRect(x*cw, y*cw, cw, cw);
	}
	
	function check_collision(x, y, array)
	{
//This function will check if the provided x/y coordinates exist
//in an array of cells or not
		for(var i = 0; i < array.length; i++)
		{
			if(array[i].x == x && array[i].y == y){
         			   
		     return true;}
		}
			   return false;
	}
	
	//Lets add the keyboard controls now
	$(document).keydown(function(e){
		//var key = e.which;  //Part of original code, I commented out to prevent users from pressing keys while the code is running
		//We will add another clause to prevent reverse gear
		if(key == "37" && d != "right") d = "left";
		else if(key == "38" && d != "down") d = "up";
		else if(key == "39" && d != "left") d = "right";
		else if(key == "40" && d != "up") d = "down";
		//The snake is now keyboard controllable
	})
//END OF ORIGINAL SNAKE GAME **********************************************************************


Basic Path Finding Algorithm Code


This is the beginning of the Basic Path Finding Algorithm. The full code is not listed here but can be found in its entirety at the URL listed below, along with an in-depth explanation of how the algorithm and code works.

//THE BASIC PATH FINDING ALGORITHM ****************************************************************
//Refer to http://gregtrowbridge.com/a-basic-pathfinding-algorithm/
// Start location will be in the following format:
// [distanceFromTop, distanceFromLeft]
var findShortestPath = function(startCoordinates, grid) {

I made a few modifications to align it with the snake game code. Renaming North, East, South, West to up, right, down, left.

// Explore North
//I modified "North" to "up" to match the Snake code
    var newLocation = exploreInDirection(currentLocation, 'up', grid); 
    if (newLocation.status === 'Goal') {
      return newLocation.path;
    } else if (newLocation.status === 'Valid') {
      queue.push(newLocation);
    }

    // Explore East
    //I modified "East" to "right" to match the Snake code
    var newLocation = exploreInDirection(currentLocation, 'right', grid);
    if (newLocation.status === 'Goal') {
      return newLocation.path;
    } else if (newLocation.status === 'Valid') {
      queue.push(newLocation);
    }

    // Explore South
    //I modified "South" to "down" to match the Snake code
    var newLocation = exploreInDirection(currentLocation, 'down', grid);
    if (newLocation.status === 'Goal') {
      return newLocation.path;
    } else if (newLocation.status === 'Valid') {
      queue.push(newLocation);
    }

    // Explore West
    //I modified "West" to "left" to match the Snake code 
    var newLocation = exploreInDirection(currentLocation, 'left', grid);
    if (newLocation.status === 'Goal') {
      return newLocation.path;
    } else if (newLocation.status === 'Valid') {
      queue.push(newLocation);
    }
  }

The snake game cannot run forever, eventually it begins to fill the canvas space.


At some point the algorithm, with no place to go, calculates itself into a trap, enclosed inside the snake body and results in a No Operation State (NOP). The simple-planning agent cheats by trying to re-spawn food, but mostly this does not work and the game is forced to start over.


Ultimately the canvas is repainted to clear up any failed, color-coded paths attempted by the algorithm.


I added lines 380 and 382-386

//If you are here, then No valid path found
//The randomly generated food can literally "paint" the snake into a corner 
//trapped inside the snake body loop, so this is set up to allow it to a "do-over"
//when food is spawned inside the body loop and the path is calculated toward it.
    create_food();  //I added this 
//The game results ends in a No Operation State (NOP) 
    ctx.fillStyle = "white";     //I added this
		ctx.fillRect(0, 0, w, h);    //I added this
		ctx.strokeStyle = "black";   //I added this
		ctx.strokeRect(0, 0, w, h);  //I added this
 // return false;  //Part of original code. I commented this out, not needed.

Once again a few modifications to the direction references, to align it with the snake game code.

// Explores the grid from the given location in the given
// direction
var exploreInDirection = function(currentLocation, direction, grid) {
  var newPath = currentLocation.path.slice();
  newPath.push(direction);

  var dft = currentLocation.distanceFromTop;
  var dfl = currentLocation.distanceFromLeft;

  if (direction === 'up') {
    dft -= 1;
  } else if (direction === 'right') {
    dfl += 1;
  } else if (direction === 'down') {
    dft += 1;
  } else if (direction === 'left') {
    dfl -= 1;
  }