Langton's Ant is a simulation devised by Chris Langton in 1986. It uses remarkably simple rules to produce surprisingly complicated results.
The ant walks on a grid of black and white squares and obeys the following two simple rules:
- If the ant is on a white square, it turns 90° right, changes the color of its square, and moves forward one square
- If the ant is on a black square, it turns 90° left, changes the color of its square, and moves forward one square
For this problem, build a Langton's Ant program similar to the one shown in the following screenshot:
The rules that the ant follows are about as simple as you can imagine, but the ant's behavior is extremely complex. Initially, it follows a fairly restricted path and generates small, sometimes symmetric patterns.
After a few hundred steps, the patterns become much larger and more chaotic, but still remain bounded. Some time after 10,000 steps, the ant begins generating a repeating pattern that creates a highway leading away from the center of the ant's little world.