Javascript Snake Game - too much recursion error-CodePudding

so I'm working on this snake game, and I'm basically trying to prevent the food from spawning on top of the snake tail. My setup variables:

let headX = 10; //snake starting position
let headY = 10;

let appleX = 5; //food starting position
let appleY = 5;

This is the function that checks head/food collision

function checkAppleCollision() {
  if (appleX === headX && appleY === headY) {
    generateApplePosition();
    tailLength  ;
    score  ;
  }
}

And this is the function that randomizes the apple position after collision, and also returns the "too much recursion" error, after a couple of collisions:

function generateApplePosition() {
  let collisionDetect = false;
  let newAppleX = Math.floor(Math.random() * tileCount);
  let newAppleY = Math.floor(Math.random() * tileCount);

  for (let i = 0; i < snakeTail.length; i  ) {
    let segment = snakeTail[i];
    if (newAppleX === segment.x && newAppleY === segment.y) {
      collisionDetect = true;
    }
  }
  while (collisionDetect === true) {
    generateApplePosition();
  }
  appleX = newAppleX;
  appleY = newAppleY;
}

Please help, I have no idea what to do here. Everything else works as intended.

CodePudding user response：

Using recursions or do while is a bad idea (I'll explain later)

meanwhile, you could simplify your logic by creating:

reusable samePos() and collides() functions
a recursive createApple() function, which will return itself if the randomly generated x,y positions are occupied by the snake body

const world = {w:6, h:1}; // height set to 1 for this demo only
const snake = [{x:0, y:0}, {x:1, y:0}, {x:2, y:0}, {x:3, y:0}];
const apple = {pos: {x:0, y:0}}; 

// Check if two object's x,y match
const samePos = (a, b) => a.x === b.x && a.y === b.y; 

// Check if object x,y is inside an array of objects
const collides = (ob, arr) => arr.some(o => samePos(ob, o));

const createApple = () => {

  const randPos = {
    x: ~~(Math.random() * world.w),
    y: ~~(Math.random() * world.h),
  };
    
  if (collides(randPos, snake)) {
    console.log(`position ${randPos.x} ${randPos.y} is occupied by snake`);
    return createApple(); // Try another position.
  }
  
  // Finally a free spot!
  apple.pos = randPos;
  console.log(`Apple to free position: ${apple.pos.x} ${apple.pos.y}`);
}

createApple();

Run this demo multiple times

The problem

Useless random guesswork!
As you can see from the example above, if you run it multiple times, very often the randomly generated number is the same as the previously generated one:

...
position 2 0 is occupied by snake    <<<
position 1 0 is occupied by snake
position 2 0 is occupied by snake    <<<
position 2 0 is occupied by snake    <<<
position 1 0 is occupied by snake
position 2 0 is occupied by snake    <<<
...

therefore, as your snake grows in size, the recursion might go wild — ad absurdum, iterating way too many times, repeating and failing on the same xy positions, until finally hitting a rare free spot...
This is a really bad design.

Solutions

One solution would be to keep track of the already used randomized positions inside an Array - but that implies unnecessarily to go trough such an Array.

A best solution would be to actually treat the game not as a 2D game, but as a 1D game:

Consider this 2D map of size 4x3 as indexes:

0  1  2  3
4  5  6  7
8  9  10 11

now, let's place a snake into this map:

0  ⬛  2  3
4  ⬛  ⬛  7
8  9  ⬛  11

here's the linear map with the Snake as a 1D list:

[ 0  ⬛  2  3  4  ⬛  ⬛  7  8  9  ⬛  11 ]

therefore, instead of using an array of objects {x:n, y:n} for the snake body positions, all you need is:

[1, 5, 6, 10]  // Snake body as indexes

Now that you know all the indexes where you're not allowed to place an Apple, all you need to do when creating the new apple is:

Create an Array of 0-N indexes of length: world.w * world.h
Loop the snake body indexes and delete those indexes from the array of indexes to get an Array of free spots indexes
Simply get only once a random key from that array of free spots!

const indexToXY = (index, width) => ({ x: index%width, y: Math.trunc(index/width) });

const world = {w:4, h:3};
const snakeBody = [1, 5, 6, 10];

const createApple = () => {
  const arr = [...Array(world.w * world.h).keys()]; // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
  snakeBody.forEach(i => delete arr[i]); 
  const freeIndexes = arr.filter(k => k !== undefined); // [0, 2, 3, 4, 7, 8, 9, 11]
  const appleIndex = freeIndexes[~~(Math.random() * freeIndexes.length)];
  const applePos = indexToXY(appleIndex, world.w);
  console.log("New apple position: %o", applePos);
};

createApple();

Run this demo multiple times

Having that free spot index simply draw your apple at the XY coordinates using this simple formula

X = index % mapWidth
Y = floor(index / mapWidth)

CodePudding user response：

As others have said, this doesn't need to be recursive, and you should also take into account the (however unlikely) possibility where there are no more tiles to spawn on which would result in an infinite loop.

function generateApplePosition() {
    // Count how many tiles are left for spawning in
    const tilesLeft = (tileCount * tileCount) - snakeTail.length;
    let collisionDetect;
    
    if (tilesLeft > 0) {
        do {
            const newAppleX = Math.floor(Math.random() * tileCount);
            const newAppleY = Math.floor(Math.random() * tileCount);
            collisionDetect = false;
            
            for (let i = 0; i < snakeTail.length; i  ) {
                const { x, y } = snakeTail[i];
                if (newAppleX === x && newAppleY === y) {
                    collisionDetect = true; // Collision
                    break;
                }
            }
            
            if (!collisionDetect) {
                // Found spawn point
                appleX = newAppleX;
                appleY = newAppleY;
            }
        } while (collisionDetect);
    }
}