Train Automaton Theory Pt1

This is Part 1 of the computer science theory behind the Train Automaton game. It describes the internal wiring given at game setup. The next parts will cover player input and the consequences for the underlying state machine.

Under the hood, the game is based on non deterministic finite automata, a computational model to describe regular languages or the more commonly used regular expressions, which is a powerful tool to search for a pattern in a text. Find out more on this type of Automata here: https://en.wikipedia.org/wiki/Deterministic_finite_automaton . Notable difference is that the language accepted by a Train Automaton consists separates the set of all possible words into three sets:

• The mandatorily accepted words: Green Trains that must be part of the accepted set, where a train can run through the railways and stop at all the stations listed in the trains route in order.
• The mandatorily unaccepted words: Red trains with routes that must not be possible.
• The set of other words with an undefined acceptance: Neither acceptance nor denial is required from the automaton.

Behind the scenes the playing field has a state machine that is a little more complex than what is shown to the player. However the projection is not that difficult.

Lets first look at the given internal wiring without any player input for a single tile <3,2> and its surroundings.

Each tile has a x and y position, and 8 internal states. Those states are split up as follows: each of the 4 directions (‘N’,’E’,’S’,’W’) has one ‘in’ (‘I’) and one ‘out’ (‘O’) state.

Each out-state has an ε-transition to the neighbouring tiles in-state of the corresponding counter direction: e.g. <x,y,’S’,’O’> has a transition to <x,y-1,’N’,’I’>, or in other words, the southern Out-state has a transition to the Southern neighbours in-state.

There are two exception cases on the edges of the playing field:

• Regular edge-tiles in the games restrictions do not have some of their neighbors. e.g. the northern edge tiles do not have any more northern neighbors.
• The entry tile outside the western edge and the exit tile outside the eastern edge: Those tiles only hold the Starting-Out-State, connected to the <x,y,’W’,’I’> neighbor state, or respectively Exit/Accept-In-State, connected to the <x,y,’E’,’O’>