Sign in to follow this  
Assassinbeast

What is the most efficient way to solve this simple problem?

Recommended Posts

Assassinbeast    271

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?

Share this post


Link to post
Share on other sites
Giallanon    1893
At start fill an array with all grid cells. Select a random cell from the array and spawn cheese. Remove this cell from the array (swap with last).
Every time you place a piece of snake on the map, remember to remove the cell from the array and remember to update the number of free cells stored in your array everytime you remove a cell from it

Share this post


Link to post
Share on other sites
Strewya    2798

Use the first and second at the same time.

While the snake is small, use the random algorithm.

When the snake size increases to a certain threshold (or if you get a certain number of misses using the random method), use the second method.

 

And are you really going to make a grid that big? Snake works best when grid sizes are small-ish. What if one of your cheese segments spawns in 1,1, and after you eat it, it spawns a new one at 99999,99999? It would take you forever to get all the way across the map.

Share this post


Link to post
Share on other sites
PKLoki    1492

Agreed with ApochPiQ. Substitute "perfectly sufficient" for "most efficient" and just code something that works. People don't play your code, they play your game.

Share this post


Link to post
Share on other sites
Nypyren    12065
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--;
  }
}
Only recommended if your grid is excessively large. Edited by Nypyren

Share this post


Link to post
Share on other sites
iMalc    2466

Method 1 should be more than sufficient...

Generally that game ends before the grid gets very full, but lets assume that the grid gets 90% full, i.e. only 10% of the spaces remain unoccupied.

The chance that more than 20 iterations of picking and testing a random point are required is 0.920 or about 12%

At 50 iterations, that drops to 0.950 or about 0.005%

 

I would expect that even if you have to do 200 iterations (and the chances of that are less than one in a billion), that it's still going to be well under a millisecond. 1000 iterations of generating a random number and looking up a grid cell, is peanuts on a modern PC.

 

If that turns out to be insufficient, because your snake moves so slow making all your players experts who fill the entire board, or you are writing this for a machine with specs similar to PCs of 30 years ago, then it would be simple enough to use algorithm 2 instead when the percentage of occupied cells goes above a certain threshold.

Probably the more important thing for this game in terms of efficiency, is how you represent the snake. The clever way, as you appear to have worked out, is to store the body parts in the grid, along with each cell storing the direction of the segment that is one place closer to the head. Then for updates you need only track where the head and the tail are, and only need to touch two cells each time the snake extends. Unlike storing all the segments in a separate queue, you get O(1) lookup time to see if the snake crashed into itself.

Edited by iMalc

Share this post


Link to post
Share on other sites
LorenzoGatti    4443

Abstractly, you can initialize the set of empty cells with all cells at the beginning and update it with one insertion and one deletion per snake per turn (add vacated tail location, add entered head location) plus a negligible number of deletions, when you spawn cheese or new snakes, and insertions, if snakes and cheese disappear.

In typical set data structures the cost of insertions and deletions is constant or logarithmic in the number of existing elements, but choosing a random set element with equal probability (for you, the cheese spawn location) might be unsupported.

However, the cost is no worse than proportional to the number of empty cells: you can always maintain the count of empty cells, use it as a limit for generating a random integer, and iterate through set elements to skip that many empty cells.

Share this post


Link to post
Share on other sites
alvaro    21247

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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this