This page is part of the Snake in MIT Scratch Tutorial.

Moving the Apple

When the snake’s head touches an apple the snake should eat it and grow longer.

After an apple is eaten the system creates a new apple at a random location.

The random location that the system chooses for the apple should not already be occupied by the snake.

Checking if an Apple is Eaten

Before moving the snake as part of the Update Snake function in the Game Controller sprite script a check is made to see if the next position the snake will move to contains an apple:

An if statement compares the next position of the snake to the current position of the apple.

If the check passes then the snake grows on its next move, the score increases and messages are broadcast to move the apple.

If the check does not succeed then the snake does a normal move.

Moving the Apple

When the apple is eaten its sprite moves to a random location that is not occupied by the snake.

When searching for an appropriate space the system tests grid positions in a random order until it finds one that is empty.

The script used to move the Apple can be found in the Apple sprite in the Scratch project.

Data Structures

Three Scratch lists are used when moving the apple:

• Spawn Positions: This list holds a value for every unique cell on the grid recording if this cell is EMPTY or BLOCKED by the snake.
• Spawn Candidates: A list of all positions on the grid.
• Snake Positions: A list of all grid positions that the snake occupies.

These lists allow all the grid positions to be checked against snake positions within a loop.

The lists make use of Positon values. Position values allowed a two-values X and Y grid coordinate to be represented using a single number.

Calculating Position Values

Positions on the grid are described using two values:

• The horizontal position X.
• The vertical position Y.

It is possible to store all possible combinations of these values in a single list by creating a unique ID for each grid position using its X and Y coordinates.

The following diagram shows the grid with a unique value assigned to each position:

The Position ID of a cell can be calculated from its X and Y coordinates with the following equation:

Position = (Y * Grid Width) + X

The (Y * Grid Width) portion calculates the row and the X value is added onto it to get the position within that row.

This calculation appears in the Scratch script as follows:

The X and Y coordinates can be calculated from the Position value with the following equations:

X = Position mod Grid Width

Y = Position / Grid Width

The X value which was added in the previous equation can be extracted with mod. The Y value was recorded as the number of rows so dividing the position value will find it.

This calculation appears in the Scratch script as follows:

The position value used in the calculation is being referenced from the Spawn Candidates list.

The floor operation is used to round the result of division down as it could have a remainder and only whole values are allowed as grid coordinates.

Creating the Data Structures

When the green flag is clicked in scratch to start the game running the system creates the structure of the data:

The Define Enumerations function is called first. This defines the EMPTY and BLOCKED values so that they can be referred to elsewhere in the code.

The Init Spawn Lists function gives the grid position lists their structure:

First all lists are cleared of any data they might already contain using delete all.

The loop counter i is set to 0 and a repeat (Grid Width * Grid Height) is used to repeat the next statements once for every grid position. Note: (Grid Width * Grid Height) = Grid Size.

On each iteration of the loop the value of i is inserted into the Spawn Candidates list. After the loop the Spawn Candidates will contain a unique value for each grid space from 0 to Grid Size – 1.

A value of EMPTY is added to Spawn Positions on each loop so that it will contain an EMPTY value for every square on the grid.

The list’s index will be used to locate specific positions on the grid. Scratch list index values start at 1 as opposed to the value in Spawn Candidates that start at 0.

Both are used to refer to positions on the grid so there will be times when it is necessary to add one to to refer to the same grid position.

Setting Data Values for a New Game

Each time the player starts a new game the system resets the values in the lists.

A new game is triggered when the New Game message is broadcast:

When the New Game event is received the system does the following:

1. Shuffle Spawn Candidates: Shuffling the list allows the spawn candidates to be tried in a random order when moving the apple.
2. Reset Spawn Positions: Calling this function resets every item in the list to EMPTY.
3. Delete all of Snake Positions: The list of snake positions so that the positions from the previous game are forgotten.

Shuffle Spawn Candidates

The Spawn Candidates list contains all the locations on the grid.

Shuffling a list of all the candidates allows the system to try the positions in a random order while still trying each position only once.

The algorithm used to shuffle the list is called the Fisher-Yates Shuffle. It works like this:

1. Set i to the position of the last item in the list – the length of the list is used for this.
2. Set j to a random number between 1 and i. (Pick a random value between the start of the list and i)
3. Swap the list values at i and j
4. Decrease the value of i by 1. (Move back one position in the list.)
5. If i > 1 then go to step 2 else exit.

The algorithm starts at the end of the list and works its way to the beginning swapping random items forward. With each iteration i is decreased so each value is shuffled only once.

A visualization of how the algorithm works can be found in the start of this video:

The Scratch implementation is as follows:

The steps in the Scratch implementation are the same as previously described.

The i value that is used throughout the project as a loop counter is used to count from the end of the list to the beginning.

Another counter j is used to select a random value between the start of the list and i.

A temporary value called temp is used to swap the list values found at positions i and j.

At the end of the loop the value of i is decreased. The loop will repeat until the value of i is 1. When the first element is reached the list has been completely shuffled.

Reset Spawn Positions

The Spawn Positions list records a value of EMPTY or BLOCKED for every possible position on the grid.

If a position is empty then an apple can be spawned there but if it is BLOCKED by the snake then the apple cannot spawn there.

At the start of the game all the values are set to EMPTY:

The system uses i as a loop count to loop through all the grid positions and replaces the values in the list with EMPTY.

The list was created with the Init Spawn Lists function so the structure already exists and the values can simply be reset.

Updating the Spawn Positions List During the Game

The Spawn Positions list contains a value for every cell in the grid that is either EMPTY or BLOCKED depending on whether the snake occupies the position.

In order to record the position of the snake as it moves and grows the list must be updated every time the snake changes.

The process for updating the Spawn Positions list has the following steps:

When the snake is updated:

1. Convert the (X, Y) coordinates of the snake’s head to a single-valued position ID.
2. Add the head position to the Snake Positions list.
3. Set the value at the head’s position in Spawn Positions to BLOCKED.
4. If the length of the Snake Positions list is greater that the number of snake parts then:
   1. Replace the value in the Spawn Positions at the position of tail of Snake Positions with EMPTY
   2. Delete the tail of Snake Positions

When the snake changes the position of its head is marked as BLOCKED in the Spawn Positions list.

Both the snake move and grow operation update the head so by marking the head as blocked the most recent change to the snake will be included in the Spawn Positions list.

The Snake Positions list is used to revert grid positions to EMPTY in the Spawn Positions list after the snake moves away.

When the snake is changed the new head is added to the Snake Positions list. The length of the Snake Positions list is compared to the length of the snake’s body.

If the snake has grown the lists will be the same size and no action will be taken.

If the snake has moved the Snake Positions will be one item longer as the new head has been added but the old tail has not yet been removed. The system marks the tail as EMPTY in the Spawn Positions list and then deletes it from the Snake Positions list.

The operation appears in the Scratch project as follows:

First the position of the head is calculated using the first item in the snake parts lists.

The position is added to the Snake Positions list and marked as BLOCKED in the Spawn Positions list.

The length of the Snake Positions list is compared to the length of the snake parts lists. If it is greater then the event is treated as the snake moving so the old tail must be marked as empty.

Deciding Where to Move the Apple

Using the shuffled list of Spawn Candidates the system tests items from the Spawn Positions list in a random order to see if they are recorded as EMPTY or BLOCKED.

After finding an empty grid space the single value position is converted into an X and Y coordinate pair that can be used to move the apple.

After moving the apple the system records the last Spawn Candidate so that the next time the apple is moved the search can start from the next position in the Spawn Candidates list.

This should avoid repeating spawn locations if possible. The list is accessed in a circular fashion by using mod to loop to the start of the list.

The process for updating the Spawn Positions list has the following steps:

When the snake is updated:

1. Set the loop counter i to the next spawn candidate.)
2. Repeat until all spawn candidates have been tried.
   1. If the position i of Spawn Candidates is BLOCKED:
      1. Set the loop counter i to the next spawn candidate.
   2. Else:
      1. Convert the spawn candidate position value to an X and Y coordinate pair.
      2. Move the apple to the X/Y location on the grid.

The operation appears in the Scratch project as follows:

A value called Previous Spawn Candidate is used to record the last spawn candidate that was used.

At the start of the operation the loop count i is set to this value plus one with mod used to constrain the value to length of the list.

Using mod in this way allows the list to be looped through in a circular fashion so that all list positions can be tried when starting from any position.

The Spawn Candidates list holds all the Spawn Positions in a random order. This enables all the positions to be tested in a random order to find a position that is not BLOCKED by the snake.

When checking the position indicated by a Spawn Candidate in the Spawn Positions list it is necessary to add one because the positions start at zero but Scratch list addresses start at one.

Converting the single valued positions to a coordinate pair is done with the equations described previously. The apple sprite contains a Move To Grid Pos function that can be used to move it on screen.

Conclusion

To move the apple to a random location on the grid that is not blocked by the snake the system uses 3 lists:

1. Spawn Candidates: A shuffled list of all positions on the grid.
2. Spawn Positions: Holds a value of either EMPTY or BLOCKED for every position on the grid.
3. Snake Positions: A list holding the positions the snake occupies.

Grid X and Y values are converted into a single position value so that only one list item is needed to hold the position.

The Spawn Positions list is updated as the snake moves using the Snake Positions list.

When it is time to move the snake the system loops through the list of Spawn Candidates and checks the Spawn Positions list to see if the position is empty. If it is then the apple can be moved there.

This method allows the system to search for a random unoccupied grid cell while only testing each position once during the search.

Next Section: Sound Playback

Table of Contents