Hi, im making a simple snake game where all GameObjects are placed on a grid of columns and rows.

There are different 3 GameObjects: SnakeBody, SnakeHead and a cheese to eat.

When the snake eats the cheese, then the cheese have to find a new available spot to spawn.

Note it cannot spawn on top of a SnakeBody or the SnakeHead.

So what is the best way to find an available spot for the new cheese to spawn?

I have so far 3 different methods i mind:

Method 1

Get a random column and row, and then check if that spot is available, if not, then iterate it over and over again until it finds an available spot.

Pros:

if there are a few Snakebodies on the map, and there are many available spots, then the chance of a single iterationcheck is pretty big and an available spot is found very easily.

Cons:

If the grid is almost full of SnakeBodies and a very few spots are available, then the chance to find an available spot is pretty low and the program could even check the same spot multiple times because its a random check which can be so much waste of processingpower.

Method 2

Create a List(C#) and iterate over the whole grid. Add every Spot to the list that is available, then get a random number from 0 to the amount - 1 in the list, and then set that new cheese to that position. Clear the list after its done.

Pros:

Unlike the Method 1, It doesn't matter how many spots there are taken or not, the count of iteration will always be the same.

Cons:

The bigger the map is, the slower the program is gonna be. So if the grid was 100000x100000, it would need to iterate and add spots MANY TIMES, and then the Method 1 would be a better choice if the grid was that big.

Method 3

Create a HashSet<Point> at the beginning before any GameObjects gets created on the map. The Point contains the X & Y to determine if an exisiting Point is already in that HashSet. Add all the Points of the grid to the HashSet. When GameObjects spawn, then remove the Point of the GameObject in the HashSet, and add it back when the GameObject gets destroyed or moved.

When the snake eats the cheese and need to find a new position, then just find take a random number from 0 to the HashSets Count - 1 and get that Point of it.

Pros:

When you need a random position, you have them in the HashSet, and then you just need to take a Point out of it from a random index, .

Cons:

Everytime something moves, it needs to remove and add (which is pretty fast). Also when you want to take a random object out of the HashSet, then the bigger the random index is, the slower the algoritm is gonna be, because you cannot just take the index and get the object directly out of the HashSet, you must iterate over it.

----------------------------------------------------------------------

So every method seems to have its Pros & Cons, but is there a way better algoritm to do this stuff?

int freeTiles; // A global free tile counter.
int[] freeTilesOnRow; // Each cell in the array represents the count of free cells in each row.

When the snake head enters a cell, decrement that row's free-tile count.
When the snake tail exits a cell, increment that row's free-tile count.
When the snake is expanding after eating cheese, decrement the global free tile counter each time the snake expands.

When the snake eats the cheese:
{
  randomCell = Pick a random number between 0 and global free tile count.
  Loop over rows:
  {
    if (randomCell > freeTilesOnRow[row])
      randomCell -= freeTilesOnRow[row];
    else
      Loop over cells in that row
        if cell is empty
          if randomCell == 0
            place cheese in this cell and return
          else
            randomCell--;
  }
}

As others have said, just about any implementation is likely to work well for this game. However, this is a problem that also appears when programming the game of go using Monte Carlo techniques: You want to be able to find a random empty spot on the board, and the code has to be fast because this is the core of the tightest loop in a CPU-hungry program.

If you want to give all the moves available the same probability, the fastest solution is to keep an array of empty spots and a map indicating the index to this array. That way you can quickly locate elements and remove them.

If you want to be able to specify different probabilities for different moves (more realistically what is needed for a strong Monte Carlo go program), the obvious modification of what Nypyren proposes is a good way to go.