Snake Game Finite Automaton.

Goal.

Construct a finite automaton representing the snake game.

Snake Game Rules.

A snake and an apple exist on a \(42 \times 24\) board. The snake can move in four directions: up, down, left, and right. The snake's goal is to eat apples without running into itself or the walls. Whenever the snake eats an apple, a new apple is spawned into a randomly generated open space on the board, the player scores 5 points, and the snake grows in length by 5. Also, if the snake is about to collide with itself or a wall, it is given a second chance, lasting one game tick, to change direction before the collision occurs.

Finite Automaton.

The automaton should accept the language: \[ L = \{ w \in \{ \text{↑, →, ↓, ←, ␀} \}^* | w = \text{ a series of inputs that play the snake game exactly to completion} \} \] For example, the automaton should accept the string '↑↑↑', an input in which the snake moves up, collides with the ceiling, and dies. However, the automaton should reject the string '↑↑', in which the game never completes, and '↑↑↑↑', which continues input after the game is complete.

The automaton is a DFA represented as a 5-tuple \((Q, \Sigma, \delta, q_0, F)\), where \begin{array}{ll} Q & \text{ is the set of states} \\ \Sigma & \text{ is the set of inputs} \\ \delta : Q \times \Sigma → Q & \text{ is the transition function between states} \\ q_0 & \text{ is the start state} \\ F & \text{ is the set of accept states} \end{array}

Input.

The alphabet \(\Sigma\) accepts 5 input characters:

NULno input, continue current direction ←left arrow key, move left →right arrow key, move right ↑up arrow key, move up ↓down arrow key, move down

Each character in the input string represents the input for a game tick. The NUL character represents a game tick where the player has entered no new direction.

States And Transitions.

The finite automaton's state is separated into several parts, each with its own set of states and transitions. The snake game tracks:

        the player's score 

        the snake's direction 

        the number of incoming pixels the snake needs to grow by 

        the position of the apple 

        the position of the snake's head 

        the location and order of each pixel on the snake's body

The finite automaton's state \(Q\) and transition function \(\delta\) can be constructed from the respective parts: \begin{array}{ll} Q_\text{points} & & & &\delta_\text{points} \\ Q_\text{direction} & & & & \delta_\text{direction} \\ Q_\text{incoming} & & & & \delta_\text{incoming} \\ Q_\text{apple} & & & & \delta_\text{apple} \\ Q_\text{head} & & & & \delta_\text{head} \\ Q_\text{body} & & & & \delta_\text{body} \\ \end{array}

Points.

The snake starts at 0 points and size 1 (just its head). When the snake eats an apple, the player scores 5 points and increases in size by 5 pixels over the duration of the next five game ticks, at a rate of one pixel per game tick. Because the snake only grows by 1 pixel per game tick, it is possible for the snake to have eaten more than \( ⌊\frac{w \times h - 1}{5}⌋ \) apples while accruing a large number of incoming tail pixels before engulfing the entire board. A state could theoretically occur where the snake, from its starting size of 1, eats an apple every game tick for \( w \times h - 1 = 1007 \) game ticks in a row. Thus, the finite automaton keeps track of \( w \times h - 1 + 1 = 1008 \) states, where the first state \(q_{\text{points } 0}\) represents 0 points and the 1008th state \(q_{\text{points } 1007}\) represents \( (w \times h - 1) \times 5 = 5035 \) points. \begin{array}{cc} Q_\text{points} = \{ 0, 1, \ldots , 1007 \} \end{array} The \((i+1)\)th state \(q_{\text{points } i}\), representing \( i \times 5 \) points, transitions to itself if the snake does not eat an apple, and transitions to the next state \(q_{\text{points } i+1}\) if the snake eats an apple. \begin{array}{cc} \delta_\text{points} : Q_\text{points} \times \{ \text{snake eats apple}, \text{snake does not eat apple} \} \to Q_\text{points} \end{array}
\begin{array}{lcl} \delta_\text{points}(q_{\text{points } i}, \text{snake does not eat apple}) & \to & q_{\text{points } i} \\ \delta_\text{points}(q_{\text{points } i}, \text{snake eats apple}) & \to & q_{\text{points } i+1} \end{array}

Direction.

The snake can move up, right, left, and down. The direction is represented with a state for each, four states in total. \begin{array}{cc} Q_\text{direction} = \{ ↑, →, ↓, ← \} \end{array} If the input direction is perpendicular to the direction the snake is already going, the snake's direction will transition to the input direction.
Otherwise, the direction does not change, whether the input direction is NUL, the direction the snake is already moving, or the direction opposite of the direction the snake is moving. \begin{array}{cc} \delta_\text{direction} : Q_\text{direction} \times \Sigma \to Q_\text{direction} \end{array}
\begin{array}{cl} \delta_\text{direction}(q_{\text{direction }i}, \text{␀}) \to q_{\text{direction }i} & \\ \delta_\text{direction}(q_{\text{direction }i}, \sigma) \to q_{\text{direction }i} & \text{if } \sigma \text{ is the direction opposite } i \\ \delta_\text{direction}(q_{\text{direction }i}, \sigma) \to q_{\text{direction }\sigma} & \text{otherwise} \\ \end{array}

Incoming Tail.

After a snake eats an apple, the snake's body increases in length by five pixels over the duration of the next five game ticks. Because a snake could eat an apple and then eat another apple within the next five game ticks, it could potentially have more than four incoming pixels at some point. A state could theoretically occur where a snake, from its starting size of 1, could eat an apple every game tick for 202 ticks in a row, adding 5 to and spending 1 from its incoming tail size each time, until the snake has a size of 203 and an incoming tail size of 808. Because the snake's maximum size is \(w \times h = 1008\), this leads to a maximum incoming tail size of 1008 - 203 = 805, and thus 805 + 1 = 806 states are used to keep track of incoming tail size. This is given by the formula \begin{array}{cc} |Q_\text{incoming}| = ⌊(5 \text{ possible incoming points } - 1 \text{ used incoming point }) \times \frac{w \times h - 1 \text{ start size (head) }}{5 \text{ points per apple }}⌋ + 1 \end{array} \begin{array}{cc} Q_\text{incoming} = \{ 0, 1, \ldots, 805 \} \end{array} If a collision occurs, the snake will not move, and the current state will not change. If the current state is the state representing an incoming tail of length \(i > 0\), \(q_{\text{incoming } i}\), it will transition to \(q_{\text{incoming } i-1}\) if the snake does not eat an apple. \(q_{\text{incoming } 0}\) will transition to itself if the snake does not eat an apple. For any \(q_{\text{incoming } i} \in Q_\text{incoming}\), the snake transitions to \(q_{\text{incoming } i+4}\) if the snake eats an apple. \begin{array}{cc} \delta_\text{incoming} : Q_\text{incoming} \times \{ \text{snake eats apple}, \text{snake does not eat apple} \} \times \{ \text{collision occurs}, \text{collision does not occur} \} \to Q_\text{incoming} \end{array}
\begin{array}{lll} \delta_\text{incoming}(q_{\text{incoming }i}, \text{snake does or does not eat apple}, \text{collision occurs}) & \to q_{\text{incoming }i} & \\ \delta_\text{incoming}(q_{\text{incoming }0}, \text{snake does not eat apple}, \text{collision does not occur}) & \to q_{\text{incoming }0} & \\ \delta_\text{incoming}(q_{\text{incoming }i}, \text{snake does not eat apple}, \text{collision does not occur}) & \to q_{\text{incoming }i-1} & i \geq 1 \\ \delta_\text{incoming}(q_{\text{incoming }i}, \text{snake eats apple}, \text{collision does not occur}) & \to q_{\text{incoming }i+4} & i \leq 801 \\ \delta_\text{incoming}(q_{\text{incoming }i}, \text{snake eats apple}, \text{collision does not occur}) & \to q_{\text{incoming }805} & i \gt 801 \\ \end{array}

Second Chance.

If a snake is about to hit a wall or itself, a second chance lasting one game tick is given, during which the snake does not move and the player has one more oppurtunity to move the snake away from the obstacle. Because the second chance acts as a boolean, two states are used. \begin{array}{cc} Q_\text{chance} = \{ \text{off}, \text{on} \} \end{array} If the second chance state is off, it transitions to on if the snake collides with an obstacle. The second chance state always transitions to off if it does not collide with an obstacle. \begin{array}{cc} \delta_\text{chance} : Q_\text{chance} \times \{ \text{collision occurs}, \text{collision does not occur} \} \to Q_\text{chance} \end{array}
\begin{array}{lll} \delta_\text{chance}(q_{\text{chance } i}, \text{collision does not occur}) & \to q_\text{chance off} & q_{\text{chance } i} \in Q_\text{chance} \\ \delta_\text{chance}(q_{\text{chance off}}, \text{collision occurs}) & \to q_\text{chance on} & \end{array} If the second chance state is on and the snake collides with an obstacle, the final automaton transitions to its accept state. \begin{array}{lll} \delta(q_{\text{chance on}}, \text{collision occurs}) & \to q_\text{accept} & q_\text{accept} \in F \subset Q \end{array}

Snake Head Position.

The position of the snake's head is kept track of using a list of states \(w \times h = 42 \times 24 = 1008\) long. The \((i+1)\)th position, represented the state \(q_{\text{head } i}\), is located at \((x,y) = (i \text{ mod } w, ⌊i \div w⌋\)). \begin{array}{cc} Q_\text{head} = \{ 0, 1, \ldots 1007 \} \end{array} Unless the snake collides with itself or a wall, the snake's head transitions one unit in the direction defined by the direction state. If the snake does collide with itself or a wall, it will remain still for one game tick, as defined by the second chance state. \begin{array}{cc} \delta_\text{head} : Q_\text{head} \times Q_\text{direction} \times Q_\text{chance} \to Q_\text{head} \end{array}
\begin{array}{llll} \delta_\text{head}(q_{\text{head } i}, & q_{\text{direction } d}, & q_\text{chance on}) & \to q_{\text{head } i} \\ \delta_\text{head}(q_{\text{head } i}, & q_{\text{direction } ↑}, & q_\text{chance off}) & \to q_{\text{head } i - 1 \times w} \\ \delta_\text{head}(q_{\text{head } i}, & q_{\text{direction } ↓}, & q_\text{chance off}) & \to q_{\text{head } i + 1 \times w} \\ \delta_\text{head}(q_{\text{head } i}, & q_{\text{direction } ←}, & q_\text{chance off}) & \to q_{\text{head } i - 1} \\ \delta_\text{head}(q_{\text{head } i}, & q_{\text{direction } →}, & q_\text{chance off}) & \to q_{\text{head } i + 1} \\ \end{array}

Apple Position.

Similar to head position, the apple's position is kept track of using a list of states \(w \times h = 42 \times 24 = 1008\) long. The \((i+1)\)th position, represented the state \(q_{\text{apple } i}\), is located at \((x,y) = (i \text{ mod } w, ⌊i \div w⌋\)). \begin{array}{cc} Q_\text{apple} = \{ 0, 1, \ldots 1007 \} \end{array} The apple's position transitions to itself if the snake does not eat it, or transitions to a new pseudo-randomly generated open spot on the board if the snake does eat it. \begin{array}{cc} \delta_\text{apple} : Q_\text{apple} \times Q_\text{head} \to Q_\text{apple} \end{array}
\begin{array}{lll} \delta_\text{apple}(q_{\text{apple } i}, q_{\text{head } j}) & \to q_{\text{apple } i} & \text{if } i \neq j \\ \delta_\text{apple}(q_{\text{apple } i}, q_{\text{head } j}) & \to q_{\text{apple } \texttt{new_apple}()} & \text{if } i = j \end{array} The pseudo-random generation is given by the algorithm:

\(\texttt{new_apple} \text{ :}\)
\(\text{snake_body_length} = \text{points} - \text{incoming_tail}\)
\(\text{open_spaces} = w \times h - \text{snake_body_length} - 1\)
\(\text{apple_index} = \texttt{hash}(\text{open_spaces}, \text{state}) \)

for \(y \in [0, h - 1]\)
for \(x \in [0, w-1]\)
if \(x + y \times w ≤ \text{apple_index}\)
for \((x',y') \in \text{snake}\)
if \((x,y) = (x',y')\)
\(\text{apple_index} = \text{apple_index} + 1\)
\(\text{apple_position}.x = \text{apple_index mod } w\)
\(\text{apple_position}.y = ⌊\text{apple_index} \div w\)⌋
return \(\text{apple_position}\)

\(\texttt{hash}(\text{max}, n\)):
if \(\text{max} = 1\) return \(0\)
\(h = 0\)
while \(n > 0\)
\(h = h + (n \text{ mod max}) \times 37 \text{ (radix)}\)
\(n = ⌊n \div \text{ max}⌋\)
return \(h \text{ mod max}\)

Note that the \(\text{state}\) argument used to call the \(\texttt{hash}\) function is the enumeration of the current state of the final automaton; \(n\), for \(q_n \in Q\). Because the \(\text{state}\) argument relies partially on the old apple position, the state of the first apple position represented by \(q_\text{start} \in Q\) is given by an apple position initialized at (3, 0), then reinitialized through a call to \(\texttt{new_apple}\).

Snake Body.

For the purpose of this section, the snake's body excludes the head.

The snake can have a body size of \([0, w \times h - 1]\) pixels. Its size can be represented by an automaton with 1008 states: \[ Q_\text{size} = \{ 0, 1, \ldots, 1007 \} \] Each pixel can be represented by its direction from the pixel preceding it, with the first pixel being preceded by the head. The number of states is therefore given by: \[ |Q_\text{body}| = \sum_{i=0}^{|Q_\text{size}| - 1}{ |Q_\text{direction}|^i} = \sum_{i=0}^{1007}{ 4^i } = \frac{4^{1008} - 1}{3} \approx 2.508 E+606 \] \[ Q_\text{body} = \bigcup\limits_{i=0}^{|Q_\text{size}| - 1}{[Q_\text{direction}]^i} \]

The body with size \(n \in Q_\text{size}\) can have a size-agnostic set of directions represented as an \(n\)-digit quaternary number, where the \(i\)th digit represents the enumerated direction the snake was moving \(i - 1\) moves in the past. This representation is given by the algorithm:

\(\texttt{enumerate_representation}(\text{snake_body})\):
\(n = 0\)
for \(\text{index } i, \text{ enumerated direction } d \in \text{snake_body} \)
\(n = n + d \times 4^i\)
return \(n\)

Note that the directions are enumerated \(q_0 = \text{↑}, q_1 = \text{→}, q_2 = \text{↓}, q_3 = \text{←}\).

To offset the representations with size \(k \lt n\), the body with size \(n\) and representation \(r\) can enumerate to \[ q_{\text{body}(\text{size } n, \text{representation } r)} = r + \sum_{i=0}^{n - 1}{ 4^i } = r + \frac{4^n - 1}{3} \] If the snake enters the second chance state, the snake's body transitions to itself. Otherwise, the snake's body will gain the pixel where the snake's head was during the last game tick. If the incoming tail is 0, the snake's body will lose the pixel at the end of its tail. The body's new state represents this new orientation. \begin{array}{cc} \delta_\text{body} : Q_\text{body} \times Q_\text{direction} \times Q_\text{incoming} \times Q_\text{chance} \to Q_\text{body} \end{array}
\begin{array}{llrclll} \delta_\text{body}( & q_{\text{body } b}, q_{\text{direction }d}, q_{\text{incoming }i}, q_{\text{chance on}} & ) & \to & q_{\text{body } b} & & \\ \delta_\text{body}( & q_{\text{body } b}, q_{\text{direction }d}, q_{\text{incoming }i \geq 1}, q_{\text{chance off}} & ) & \to & q_{\text{body } 4 \times (b - o_n) + d + o_{n+1}} & n = \lfloor\log_4{(3b + 1)}\rfloor & o_n = \frac{4^n - 1}{3} \\ \delta_\text{body}( & q_{\text{body } b}, q_{\text{direction }d}, q_{\text{incoming }i = 0}, q_{\text{chance off}} & ) & \to & q_{\text{body } 4 \times ((b - o_n) \text{ mod } 4^{n-1}) + d + o_n} & n = \lfloor\log_4{(3b + 1)}\rfloor & o_n = \frac{4^n - 1}{3} \\ \end{array}

Bringing It All Together.

The finite automata for each of these parts combine so that each state indicates the number of points, movement direction, incoming tail, second chance, apple position, snake head position, and snake body, for a total of: \begin{array}{ccr} & (w \times h - 1 + 1) & \text{points} \\ & 4 & \text{directions} \\ & ⌊(5 \text{ points} - 1 \text{ used point}) \times (\frac{w \times h - 1}{5} \text{ points per apple})⌋ + 1 & \text{incoming tail} \\ & 2 & \text{second chance states} \\ & 1008 & \text{apple positions} \\ & 1008 & \text{head positions}\\ \times & \frac{4^{1008} - 1}{3} & \text{body states} \\ \hline & 1008 & \text{points} \\ & 4 & \text{directions} \\ & 806 & \text{incoming tail} \\ & 2 & \text{second chance states} \\ & 1008 & \text{apple positions} \\ & 1008 & \text{head positions}\\ \times & \frac{4^{1008} - 1}{3} & \text{body states} \\ \hline \\ \end{array} 16563672272219750403525322809157601712925344419975291428732222914102436064320502239029063366713812189588185946501561722485452187616891630802747565804184042568634789856993557761692333291866798808595060380019752197915128309883917492137179816589082536072062093640883082848738304670449442848432880350045409101902084552349842423537993374653390567505480762768500834468675948953728201690076158994534550340164557316532932150128341997857758810165219963431517272160694101665443825204072109190752166657509623924996785239391460075558835204727278770380388491825235557016441805249597906104888699461348226854091083203088058820601118720 \begin{array}{cc} & & & & & & & & & & & & & & 1 & \text{accept state} & & & & & & & & & & & & & & \\ + & & & & & & & & & & & & & & 1 & \text{reject state} & & & & & & & & & & & & & & \\ \hline \end{array} 16563672272219750403525322809157601712925344419975291428732222914102436064320502239029063366713812189588185946501561722485452187616891630802747565804184042568634789856993557761692333291866798808595060380019752197915128309883917492137179816589082536072062093640883082848738304670449442848432880350045409101902084552349842423537993374653390567505480762768500834468675948953728201690076158994534550340164557316532932150128341997857758810165219963431517272160694101665443825204072109190752166657509623924996785239391460075558835204727278770380388491825235557016441805249597906104888699461348226854091083203088058820601118722 \begin{array}{cc} |Q| = 1008 \times 4 \times 806 \times 2 \times 1008 \times 1008 \times \frac{4^{1008} - 1}{3} + 1 + 1 \approx 1.656 E+619 \text{ states} \end{array} \begin{array}{cc} Q = Q_\text{points} \times Q_\text{directions} \times Q_\text{incoming} \times Q_\text{chance} \times Q_\text{apple} \times Q_\text{head} \times Q_\text{body} \cup \{q_\text{accept}\} \cup \{q_\text{reject}\} \end{array}

Enumerating States.

States are enumerated as follows: \begin{array}{cc} & & & & & & & & & & & & & q_{\text{body}} \\ & & & & & & & & & & & q_{\text{head}} & \times & |Q_{\text{body}}| \\ & & & & & & & & & q_{\text{apple}} & \times & |Q_{\text{head}}| & \times & |Q_{\text{body}}| \\ & & & & & & & q_{\text{chance}} & \times & |Q_{\text{apple}}| & \times & |Q_{\text{head}}| & \times & |Q_{\text{body}}| \\ & & & & & q_{\text{incoming}} & \times & |Q_{\text{chance}}| & \times & |Q_{\text{apple}}| & \times & |Q_{\text{head}}| & \times & |Q_{\text{body}}| \\ & & & q_{\text{direction}} & \times & |Q_{\text{incoming}}| & \times & |Q_{\text{chance}}| & \times & |Q_{\text{apple}}| & \times & |Q_{\text{head}}| & \times & |Q_{\text{body}}| \\ + & q_{\text{points}} & \times & |Q_{\text{direction}}| & \times & |Q_{\text{incoming}}| & \times & |Q_{\text{chance}}| & \times & |Q_{\text{apple}}| & \times & |Q_{\text{head}}| & \times & |Q_{\text{body}}| \\ \hline \\ \end{array} \begin{array}{cc} \text{subscript } i \text{ for state } q_i \in Q \end{array}
Conversely, the game's state can be resolved from \(\text{subscript } i \text{ for state } q_i \in Q\): \begin{array}{llccccc} q_{\text{body } b} & b = & i & \text{mod} & |Q_\text{body}| & & & & & & & & & & & & \\ q_{\text{head } h} & h = & i & \div & |Q_\text{body}| & \text{mod} & |Q_\text{head}| & & & & & & & & & & \\ q_{\text{apple } a} & a = & i & \div & |Q_\text{body}| & \div & |Q_\text{head}| & \text{mod} & |Q_\text{apple}| & & & & & & & & \\ q_{\text{chance } c} & c = & i & \div & |Q_\text{body}| & \div & |Q_\text{head}| & \div & |Q_\text{apple}| & \text{mod} & |Q_\text{chance}| & & & & & & \\ q_{\text{incoming } t} & t = & i & \div & |Q_\text{body}| & \div & |Q_\text{head}| & \div & |Q_\text{apple}| & \div & |Q_\text{chance}| & \text{mod} & |Q_\text{incoming}| & & & & \\ q_{\text{direction } d} & d = & i & \div & |Q_\text{body}| & \div & |Q_\text{head}| & \div & |Q_\text{apple}| & \div & |Q_\text{chance}| & \div & |Q_\text{incoming}| & \text{mod} & |Q_\text{direction}| & & \\ q_{\text{points } p} & p = & i & \div & |Q_\text{body}| & \div & |Q_\text{head}| & \div & |Q_\text{apple}| & \div & |Q_\text{chance}| & \div & |Q_\text{incoming}| & \div & |Q_\text{direction}| & \text{mod} & |Q_\text{points}| \\ \end{array} Exceptions are the special reject state and the accept state, which represent no specific orientation of body, head, etc., but instead signify that the game has been played to or past completion. These states are enumerated to \(|Q|-1\) and \(|Q|-2\) respectively.

Start State.

The finite automaton starts with the snake's head at position (1,1) \(q_{\text{head } 43}\), direction right \(q_{\text{direction } 1}\), no pixels in the incoming tail queue \(q_{\text{incoming } 0}\), not on second chance \(q_{\text{chance } 0}\), apple at (9, 8) \(q_{\text{apple } 345}\), and no pixels in the snake's body \(q_{\text{body } 0}\). This maps to:
\(q_0\): q4108925974003472556773404746808833763787617692495985444441148743688769654871379890896319949479361638064287131922455513105965401326299216806527210731096237857313165435920146766476351189771345822380699120818447825508077119369895428462409196769977258605605312902380229810044978492858059814417094769528986693047498998786305292043206924956711135743542042797261538201549417874193988912926794849482761771852157460461628595532708149461362055519630505538438469758357302393592109465778422183064354619614692808600292246479252744152223017655512046438783807376315126596298012468218343832191646560532271919661003104773832509541495

Accept State.

The finite automaton moves to its accept state when the game ends. This occurs when the snake is already on its second chance and hits itself or a wall. This is enumerated to \(|Q|\) - 1 (reject state) - 1:
\(q_\text{accept}\): q16563672272219750403525322809157601712925344419975291428732222914102436064320502239029063366713812189588185946501561722485452187616891630802747565804184042568634789856993557761692333291866798808595060380019752197915128309883917492137179816589082536072062093640883082848738304670449442848432880350045409101902084552349842423537993374653390567505480762768500834468675948953728201690076158994534550340164557316532932150128341997857758810165219963431517272160694101665443825204072109190752166657509623924996785239391460075558835204727278770380388491825235557016441805249597906104888699461348226854091083203088058820601118720
\[ F = \{q_\text{accept}\} \]
Any string that finishes the game before the input is complete should not be accepted. \begin{array}{cc} \delta(q_\text{accept}, \sigma) \to q_\text{reject} & \sigma \in \Sigma \end{array}

Reject Strings.

The finite automaton rejects any set of inputs that either never enters the accept state or continues after entering the accept state. A special \(q_\text{reject}\) state after the accept state is enumerated to \(|Q| - 1\):
\(q_\text{reject}\): q16563672272219750403525322809157601712925344419975291428732222914102436064320502239029063366713812189588185946501561722485452187616891630802747565804184042568634789856993557761692333291866798808595060380019752197915128309883917492137179816589082536072062093640883082848738304670449442848432880350045409101902084552349842423537993374653390567505480762768500834468675948953728201690076158994534550340164557316532932150128341997857758810165219963431517272160694101665443825204072109190752166657509623924996785239391460075558835204727278770380388491825235557016441805249597906104888699461348226854091083203088058820601118721 \[ q_\text{reject} \notin F \] \begin{array}{cc} \delta(q_\text{accept}, \sigma) \to q_\text{reject} & \sigma \in \Sigma \\ \delta(q_\text{reject}, \sigma) \to q_\text{reject} & \sigma \in \Sigma \end{array} Note that this is not the only reject state; any string that does not end in the accept state will be rejected.

Transition Function.

Now the final transition function can be defined. \begin{array}{cc} \delta: Q \times \Sigma \to Q \end{array}

\(\delta(q_i, \sigma):\)
if \(i \lt |Q| - 2\)
// define current game state
\(q_{\text{body } b}\):\( b = i \text{ mod } |Q_\text{body}| \)
\(q_{\text{head } h}\):\( h = i \div |Q_\text{body}| \text{ mod } |Q_\text{head}| \)
\(q_{\text{apple } a}\):\( a = i \div |Q_\text{body}| \div |Q_\text{head}| \text{ mod } |Q_\text{apple}| \)
\(q_{\text{chance } c}\):\( c = i \div |Q_\text{body}| \div |Q_\text{head}| \div |Q_\text{apple}| \text{ mod } |Q_\text{chance}| \)
\(q_{\text{incoming } t}\):\( t = i \div |Q_\text{body}| \div |Q_\text{head}| \div |Q_\text{apple}| \div |Q_\text{chance}| \text{ mod } |Q_\text{incoming}| \)
\(q_{\text{direction } d}\):\( d = i \div |Q_\text{body}| \div |Q_\text{head}| \div |Q_\text{apple}| \div |Q_\text{chance}| \div |Q_\text{incoming}| \text{ mod } |Q_\text{direction}| \)
\(q_{\text{points } p}\):\( p = i \div |Q_\text{body}| \div |Q_\text{head}| \div |Q_\text{apple}| \div |Q_\text{chance}| \div |Q_\text{incoming}| \div |Q_\text{direction}| \text{ mod } |Q_\text{points}| \)

// next direction
\(d' = \delta_\text{direction}(q_{\text{direction } d}, \sigma)\)

// next head if collision does not occur
if \(d'.\text{direction} = ↑\) (\(d' = 0\))
\(h_0 = h - 1 \times w\)
if \(d'.\text{direction} = →\) (\(d' = 1\))
\(h_0 = h + 1\)
if \(d'.\text{direction} = ↓\) (\(d' = 2\))
\(h_0 = h + 1 \times w\)
if \(d'.\text{direction} = ←\) (\(d' = 3\))
\(h_0 = h - 1\)

// check for collision
\((x, y) = (h \text{ mod } w, \lfloor h \div w \rfloor)\)
\((x_0, y_0) = (h_0 \text{ mod } w, \lfloor h_0 \div w \rfloor)\)

// collision with wall
if \(x_0 \notin [0, w - 1]\)
\(\text{collision occurs}\)
if \(y_0 \notin [0, h - 1]\)
\(\text{collision occurs}\)

// collision with tail
\(\text{size } = \lfloor\log_4{(3b + 1)}\rfloor = p - t\) (two methods of determining size)
\(r = b - \frac{4^n-1}{3}\) // quaternary representation of body with \(\text{size}\) digits
let \(p = (x, y)\)
for \(j \in [0, \text{size}-1]\)
let \(d_j = \lfloor\frac{r \text{ mod } 4^{j+1}}{4^j}\rfloor\) // direction of pixel \(j\) = (\(j + 1\))th digit of \(r\)

// unshift pixel \(p\) (shift \(p\) opposite of direction \(d_j\))
if \(d_j.\text{direction} = ↑\) (\(d_j = 0\))
\(p.y = p.y + 1\) // shift down
if \(d_j.\text{direction} = →\) (\(d_j = 1\))
\(p.x = p.x - 1\) // shift left
if \(d_j.\text{direction} = ↓\) (\(d_j = 2\))
\(p.y = p.y - 1\) // shift up
if \(d_j.\text{direction} = ←\) (\(d_j = 3\))
\(p.x = p.x + 1\) // shift right

if \(h_0 = p\)
\(\text{collision occurs}\)

// next chance
if \(\text{collision occurs}\) AND \(c.\text{chance} = \text{off}\)
\(c' = \delta_\text{chance}(c, \text{collision occurs})\)
otherwise if \(\text{collision does not occur}\)
\(c' = \delta_\text{chance}(c, \text{collision does not occur})\)

// next head
\(h' = \delta_\text{head}(q_{\text{head } h}, q_{\text{direction } d'}, q_{\text{chance } c'})\)

// next apple
\(a' = \delta_\text{apple}(q_{\text{apple } a}, q_{\text{head } h'})\)

if \(a = h'\)
\(\text{snake eats apple}\)
otherwise
\(\text{snake does not eat apple}\)

// next points
if \(\text{snake eats apple}\)
\(p' = \delta_\text{points}(q_{\text{points } p}, \text{snake eats apple})\)
otherwise
\(p' = \delta_\text{points}(q_{\text{points } p}, \text{snake does not eat apple})\)

// next incoming tail
if \(\text{collision occurs}\)
\(t' = \delta_\text{incoming}(q_{\text{incoming } t}, \text{snake does not eat apple}, \text{collision occurs})\)
otherwise if \(\text{snake eats apple}\)
\(t' = \delta_\text{incoming}(q_{\text{incoming } t}, \text{snake eats apple}, \text{collision does not occur})\)
otherwise
\(t' = \delta_\text{incoming}(q_{\text{incoming } t}, \text{snake does not eat apple}, \text{collision does not occur})\)

// next body
\(b' = \delta_\text{body}(q_{\text{body } b}, q_{\text{direction } d'}, q_{\text{incoming } t'}, q_{\text{chance } c'})\)

if \(c.\text{chance} = \text{on}\) AND \(\text{collision occurs}\)
\(i' = |Q| - 2\) (accept state)
otherwise if \(i = |Q| - 2\) (accept state)
\(i' = |Q| - 1\) (reject state)
otherwise if \(i = |Q| - 1\) (reject state)
\(i' = |Q| - 1\) (reject state)
otherwise
// enumerate next state \(q_{i'}\)
\(i' = b'\)
\(+ |Q_\text{body}| \times h'\)
\(+ |Q_\text{body}| \times |Q_\text{head}| \times a'\)
\(+ |Q_\text{body}| \times |Q_\text{head}| \times |Q_\text{apple}| \times c'\)
\(+ |Q_\text{body}| \times |Q_\text{head}| \times |Q_\text{apple}| \times |Q_\text{chance}| \times t' \)
\(+ |Q_\text{body}| \times |Q_\text{head}| \times |Q_\text{apple}| \times |Q_\text{chance}| \times |Q_\text{incoming}| \times d' \)
\(+ |Q_\text{body}| \times |Q_\text{head}| \times |Q_\text{apple}| \times |Q_\text{chance}| \times |Q_\text{incoming}| \times |Q_\text{direction}| \times p' \)

\(\delta(q_i, \sigma) \to q_{i'}\)