Colouring Turtle - an FSM[40C]

Contributed by Francis Glassborow

The idea for this project comes from an article in the Mathematical Games section of The Scientific American from some time in the 1980's. The C classification is because you will need graphics and a way to determine the colour of a pixel (either by asking the system or by keeping track in some form of database)

Consider that you have an infinite grid of square cells that are initially all white. You also have a 'turtle' sitting on one of those cells.

There is also a table that identifies the action to be taken by the turtle depending on the clour of the square it is currently occupying. The actions take the form (change colour of current cell --that could be to the same colour -- turn left or right, no turn, or reverse, and move to the cell it is now facing.

For example, a very simple set of rules would be:

• If white, change to red and turn left.
• If red, change to blue and turn right
• If blue, no change, no turn

Initially limit yourself to only a few colours. Four is plenty to start with.

Note that some sets of rules produce very boring results and others produce qyite startling and unexpected ones.

Program elements

You will need a container to store the rules (strictly speaking you could avoid this, but that would be a poor solution because changing the rules would result in essential change to the source code).

You will need a way to find out the colour of the cell the turtle currently occupies. One way to do this is to keep you own 2D array of cells whose values are the current colour.

You will need a way to display the results as they happen. That means you will need to handle some form of graphics window.

You will also need to ensure that your program handles attempts by the turtle to go out-of-bounds.

Variants

In this case most of the variants tend to be harder than the basic project because they need greater insight as to how to map the results to an essentially reactangular grid of pixels

• Modify the program so that it has an option to prompt the user for the rules and store them in a file.
• Allow the turtle to make diagonal as well as orthogonal moves (like the King's move in Chess).
• Try the idea using hexagonal grid. One way to deal with mapping a hexagonal grid to a rectangular one is to use two by one rectangles with each row staggered (like in a brick wall). You will find that each rectangular cell is adjacent to six others.
• Try it for a triangular grid. No hints about a mapping to a rectangular array this time.