Trying to not waste time on RNG

Hi,
I wrote a little snake game(Link)
My current issue is that I don't know how to implement a logic to disable the RNG from placing the food dots inside the body of the snake.

I know that I could just get a position from the RNG and check the whole length of the body if my possible new food dot is in there... In the worst case I would have to check serveral hundreds of point just to place one dot...

Another possibility would be to maintain an array of empty spaces while the snake is moved within the field...

But is there an alternative way that I can chose a point?

Side note: There is another issue where the game ends itself because the snake is able the change in the opposite direction. To my understanding this should not be possible I don't change the direction if the input is the opposite of the current direction...

In randomness it's usually fine to throw away "wrong" result and keep trying until you get the right one. It might be a problem if your game allows the snake to occupy almost all of the screen.

You can also decide to pick position as the position of n-th free square. Take area, subtract size of the snake, pick random number in that range, and then iterate empty squares to find the n-th.

8 Likes

You're probably overthinking this.

Basic probability theory tells us that, for a board where a fraction r of the tiles is filled, the expected number of random numbers you'll need to draw is:

image

In other words:

  • When the board is 50% full, it will take on average two rolls to get a free tile.
  • When the board is 90% full, it will take on average 10 rolls to get a free tile.
  • When the board is 99% full, it will take on average 100 rolls to get a free tile.

100 rolls isn't much. I don't know if I've ever seen a board 99% full in snake.

(that said, if it does happen, then the cost will quickly shoot up for the last few tiles)

6 Likes

If one is worries about the board filling up (or a bad RNG roll always ending up in the wrong place), a good paranoid mitigation would be to keep track of the number of free tiles, and switch to a different strategy when it drops too low.

5 Likes

Another option: if the dot is inside the snake, just do nothing and wait until next loop to try again. That way food might be ever-so-slightly slower to appear, but won't risk any noticeable responsiveness delay.

2 Likes

If the stars is the snake, you could enumerate the spots like this:

0 1 2
3 * *
4 * 5
* * 6
7 8 9

Then pick a random number from 0 to 9.

1 Like