I am working on a "greedy snake" game. I am using a 2d array to store the value of each location/grid of the map: either egg or snake body or empty. The egg needs to be generated on the empty spot. One solution could be:

```
while (new egg location overlaps snake body)
     Within the range of 2d array randomly generate an egg location

```

However when the snake grows very big and fills up most area of the map, the generating new egg become very inefficient, since it has to check almost every element of the 2d array. How can this be optimized?