I'm implementing a Snake game in javascript for fun, I have successfully implemented the snake, its movements and the snake-growth thing as it eats an apple.

To calculate the apple position I'm currently following these steps:

1. create a new apple object
2. create random coordinates (X and Y, between game-container boundaries) for the apple
3. check if the coordinates of the apple are equal to one of the snake-blocks coordinates
4. if step #3 is TRUE, recalculate the position of the apple, else draw the apple in the game-container

Unfortunately I found out that this algorithm is very weak.. let's say I have a 10 x 10 game container, the red square is the apple, the green square is my snake head (initial game state)

as the game progresses the snake eats more and more apples, increasing its length and leaving less and less empty cells to place an apple

Now suppose that the snake reaches a length equals to 99 while eating an apple. This means that there's only one square left to place the next apple. My algorithm (this is the worst case obviously) could take forever in order to randomize the correct value, as it discards any randomized position that it's already taken by the snake's head or tail, not caring at all to randomize the new position in a range of "empty cells" only but instead randomizing on the whole 10 x 10 game canvas.

How should I proceed to solve my busillis? Can you give me any advice on a good algorithm that I can use?

Thank you

I'm implementing a Snake game in javascript for fun, I have successfully implemented the snake, its movements and the snake-growth thing as it eats an apple.

To calculate the apple position I'm currently following these steps:

1. create a new apple object
2. create random coordinates (X and Y, between game-container boundaries) for the apple
3. check if the coordinates of the apple are equal to one of the snake-blocks coordinates
4. if step #3 is TRUE, recalculate the position of the apple, else draw the apple in the game-container

Unfortunately I found out that this algorithm is very weak.. let's say I have a 10 x 10 game container, the red square is the apple, the green square is my snake head (initial game state)

as the game progresses the snake eats more and more apples, increasing its length and leaving less and less empty cells to place an apple

Now suppose that the snake reaches a length equals to 99 while eating an apple. This means that there's only one square left to place the next apple. My algorithm (this is the worst case obviously) could take forever in order to randomize the correct value, as it discards any randomized position that it's already taken by the snake's head or tail, not caring at all to randomize the new position in a range of "empty cells" only but instead randomizing on the whole 10 x 10 game canvas.

How should I proceed to solve my busillis? Can you give me any advice on a good algorithm that I can use?

Thank you

• javascript
• algorithm
• random

Share Improve this question Follow asked Feb 23, 2015 at 23:11 BeNdErRBeNdErR 17.9k2121 gold badges7777 silver badges106106 bronze badges 8

• 4 The easiest solution I can think now is to make a list of free coordinates and choose randomly from them? – mkabanen Commented Feb 23, 2015 at 23:15
• @kabanen: In fact that's the best solution :-) – Bergi Commented Feb 23, 2015 at 23:17
• I think this is not optimal as I have to refresh this list every time the snake moves, removing the occupied cells (I have to scan the list in order to find the cell) and adding the freed ones. Am I wrong? – BeNdErR Commented Feb 23, 2015 at 23:17
• Do you add apples on every step? If not, then you can calculate free coordinates only if needed. – mkabanen Commented Feb 23, 2015 at 23:19
• 2 Even if it wasn't the best solution, it's still a good answer, and you should always feel free to add those. :) – Shomz Commented Feb 23, 2015 at 23:29

 |  Show 3 more ments

1 Answer 1

Sorted by: Reset to default 6

As said in ments, the easiest solution I can think is to make a list of free coordinates and then just choose randomly from them. And you can calculate free coordinates only if needed(when you need to add an apple).