Javascript Snake

Question

I have implemented a little snake game with Javascript and Html. This is my first game with Javascript. I use a Linkedlist to represent the snake. Both code snippets are in snake.js file.

It would be really nice if someone could give me feedback.

LinkedList:

function Point(x, y) {
 this.x=x;
 this.y=y;

 this.toString = function toString() {
 return this.x +" "+this.y;
 }
}

function Node(point) {
 var next =null;
 this.point=point;

  this.getX = function getX() {
    return this.point.x;
 }

  this.getY = function getY() {
     return this.point.y;
 }

  this.setX = function setX(x) {
   this.point.x=x;
 }

  this.setY = function setY(y) {
   this.point.y=y;
 }

  this.toString = function toString() {
    return this.point.x +" "+this.point.y + " "+this.next;
 }
}

function LinkedList() {

 var first = null;
 var elements = 0;

 this.getLength = function getLength() {
     return elements;
 }

 this.addFirst = function addFirst(point) {

     elements++;
     var newNode = new Node(point);
     newNode.next = first;
     first = newNode;
 }

this.addLast = function addLast(point) {
  elements++;
        var newNode = new Node(point);
        var currentNode = first;

        while(currentNode.next!=null) {
            currentNode = currentNode.next;
        }
   currentNode.next = newNode;
         newNode = currentNode;
    }

  this.getX = function getX(index) {

  var currentNode = first;
  var tmp =0;

    while(true) {

             if(index> elements - 1) {
                 //console.log("Fehler: ungültiger Index");
        return null;
             }

             if(tmp==index) {
      return currentNode.getX();
             }

             tmp++;
             currentNode= currentNode.next;
     }
   }

 this.setX = function setX(index, value) {

  var currentNode = first;
  var tmp =0;

while(true) {

             if(index> elements - 1) {
                 //console.log("Fehler: ungültiger Index");
        return null;
             }

             if(tmp==index) {
       currentNode.setX(value);
        return currentNode;
             }

             tmp++;
             currentNode= currentNode.next;
     }
   }

 this.setY = function setX(index, value) {

  var currentNode = first;
  var tmp =0;

 while(true) {

             if(index> elements - 1) {
                 //console.log("Fehler: ungültiger Index");
        return null;
             }

             if(tmp==index) {
       currentNode.setY(value);
        return currentNode;
             }

             tmp++;
             currentNode= currentNode.next;
     }
   }

 this.getY = function getY(index) {

 var currentNode = first;
 var tmp =0;

 while(true) {

     if(index> elements - 1) {
       //console.log("Fehler: ungültiger Index");
        return null;
     }

     if(tmp==index) {
      return currentNode.getY();
     }
     tmp++;
     currentNode= currentNode.next;
   }
 }
}

Snake:

 var boardWidth = 40;
 var boardHeight = 40;
 var canvas;
 var context;
 var snakeList = new LinkedList();

 function Food() {
  var positionX;
  var positionY;

 this.randomFood = function randomFood() {
    this.positionX= Math.floor((Math.random() * (boardWidth-1)));
    this.positionY = Math.floor((Math.random() * (boardHeight-1)));
 }

this.getX = function getX() {
    return this.positionX;
 }

this.getY = function getY() {
    return this.positionY;
 }
}

function Snake() {

var positionX = Math.floor((Math.random() * (boardWidth-5)));
var positionY = Math.floor((Math.random() * (boardWidth-5)));
var interval = setInterval(update, 100);
var pressedKey = 0; // start game with arroa key
var food = new Food();
var points =0;

food.randomFood();
snakeList.addFirst(new Point(positionX,positionY));
snakeList.addFirst(new Point(positionX-1,positionY));
snakeList.addFirst(new Point(positionX-2,positionY));

 function update() {

  if(pressedKey!=0) {
   move();
 }

   eatApple();
   changeDirection();
   checkGameOver();
   repaint();

         if(pressedKey==0) {
            context.strokeText("Start Game with arrow key, new Game with F5",100,20,150);
         }
}

function move() {

 for(var i= snakeList.getLength()-1; i > 0; i--) {
     snakeList.setX(i,snakeList.getX(i-1));
     snakeList.setY(i,snakeList.getY(i-1));
   }
 }

function eatApple() {

 if(snakeList.getX(0)==food.getX(0) && snakeList.getY(0)==food.getY(0)) {
 snakeList.addLast(new Point());
 points++;
    document.getElementById("textareapoints").value = "Points: "+points;
    food.randomFood();
  }
}

function changeDirection() {

 var xDirection= snakeList.getX(0);
 var yDirection= snakeList.getY(0);

 window.onkeydown = function(evt) {

if (evt.keyCode == 37) { pressedKey=37;} //left

if (evt.keyCode == 38) { pressedKey=38;} //up

if (evt.keyCode == 39) { pressedKey=39;} //right

if (evt.keyCode == 40) { pressedKey=40;} //down

}

switch(pressedKey) {
 case 37: snakeList.setX(0,xDirection-1); break;
 case 38: snakeList.setY(0,yDirection-1); break;
 case 39: snakeList.setX(0,xDirection+1); break;
 case 40: snakeList.setY(0,yDirection+1); break;
 default: break;
  }
} 

 function checkGameOver() {

  for(var i=1; i<snakeList.getLength(); i++) { // eat itself

 if(snakeList.getX(0)== snakeList.getX(i) && 
   snakeList.getY(0)==snakeList.getY(i)) {
     clearInterval(interval);
     context.strokeText("new Game with F5",100,20,150);
  }
 }

 if(snakeList.getX(0) < 0 || snakeList.getX(0) > boardWidth-1 || // hit border
    snakeList.getY(0) < 0 || snakeList.getY(0) > boardHeight-1) {
    clearInterval(interval);
    context.strokeText("new Game with F5",100,20,150);
   }
 }

function repaint() {

 context.fillStyle = "yellow"; // repaint whole canvas
  for(var i=0; i<boardWidth; i++) {
   for(var j=0; j<boardHeight; j++) {
  context.fillRect(i*10, j*10,10,10);
 }
}

context.fillStyle = "green"; // food
context.fillRect(food.getX()*10, food.getY()*10, 10, 10)

context.fillStyle = "red"; //snake head
context.fillRect(snakeList.getX(0)*10, snakeList.getY(0)*10,10,10);

context.fillStyle = "blue"; // snake body

for(var i=1; i<snakeList.getLength(); i++) {
  context.fillRect(snakeList.getX(i)*10, snakeList.getY(i)*10,10,10);
  }
 }
}

function initCanvas() {
 canvas  = document.getElementById("canvas");
 context = canvas.getContext("2d");
 canvas.width = 400;
 canvas.height = 400;
 context.fillStyle = "yellow";
 context.fillRect(0,0,canvas.width, canvas.height);
 context.fillStyle = "black";
}

window.onload = function() {
 initCanvas();
 var s = new Snake();
}

Html page:

<!DOCTYPE html>
<html lang="de">

<head>
<meta charset="utf-8" />
<title>Snake</title>
<link href="snakecss.css" rel="stylesheet">
<script src="snake.js"></script>
</head>

<body>

<header>
<h1>Snake</h1>
</header>

<canvas id="canvas"> </canvas>

<textarea id="textareapoints" type="text" rows="1" cols="30">
Points: 0
</textarea>

</body>
</html>

Answer 1

Worst use of linked list, ever!

Linked list are convenient for many reasons, one of them is fast splicing, much faster than array splicing and thus the best option when you are often inserting and deleting items at random positions in the list.

Linked list are very (VERY) poor at random access. Worst case to find the last item on the list you have to iterate each item. Compared to arrays that are very very good at random access, any item can be accessed in the same fixed time.

Linked list and arrays are equally good at push/pop and shift/unshift (if you keep a head and tail on the linked list, and if the array can grow up and down)

Looking at your code the linked list has the functions addFirst, addLast which are the equivalent to array push / unshift. You do not do any splicing, and all the access is via an index (random access).

You create a linked list and only use its worst attributes, and never even implement its best.

Snake games use stacks.

Modern variants of the game use stacks. Memory is cheap and plentiful so the stack is a practical solution. The stack is O(1) time and O(n) memory.

The JS array is also a stack. The snake's head at the bottom and the tail at the top (or you can do it the other way around)

To move the snake one step forward, you pop the tail, set its x,y to the new head position and then unshift it to the bottom of the stack.

To move and grow you don't pop the tail, but create a new head and just unshift it to the bottom of the stack.

Moving forward using the your linked list is O(n (log n)) while the array stack is O(1) in time complexity. (where n is the length of the snake)

An alternative is the display list.

Snake game

A well designed classic style snake game is O(1) in time and storage. Almost all modern versions of this game that I have seen are O(n) in time and storage (where n is the max snake length)

In the game there are only two points of change, the head and the tail, all the rest is static (and on occasion an apple). To determine if the snake eats it self you need only check the display list (a single lookup O(1)) and not iterate each body segment. And the same applies to the apple. The display list also encodes the tail direction so it can be removed in the correct sequence.

Property access

Don't use functions to access public properties, its slow due to call stake quaking. (quake as in rapidly oscillating)

Each variable access requires a new function context that needs to be created and pushed to the stack. Because you do it over two levels of abstraction, linkedList then point updating a single coordinate (x,y) requires 8 functions calls and 4 new function contexts. While direct access requires 0 function calls, and no stack or heap changes

Besides the negative performance it is also syntactically poor as direct access or getters and setters would provide cleaner code.

Minor points

• Only add the key event once in the onload event. You have window.onkeydown = function (evt) { in the function changeDirection and should be in the window onload event.

• window is redundant and you do not need to use it.

• KeyboardEvent.keyCode has depreciated, you should use KeyboardEvent.key or KeyboardEvent.code

• Add events using addEventListener

• Idiomatic name for CanvasRenderingContext2D is ctx, or use context2D because context could be anything.

• Magic numbers and strings all over the place, many for the same abstract. Put them in one place at the top of the code as a named constant. For example, say you want to change the cell size from 10 to 20 pixels. In your code you would have to manually change 16 numbers, and you can not just search replace, as the 10 may have other meanings. You would have to check each and every instance of 10.

  With const cellSize = 10; at the top of the code and ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize); when you use it making changes is easy and fast. Same applies to all numbers and all strings. even if used only once, keeping them all in one place makes it easy.