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?