Humberto Barreto

You must ENABLE MACROS (see below for details) when you open this file.

hbarreto@depauw.edu

Langton's ant follows two simple rules to move around, yet remarkably it produces something ordered.

As of this writing, it seems that no matter the initial grid, the ant will eventually build a highway (this mysterious term, which you will discover as you learn about Langton's ant, is an open-problem that is the subject of current research).

Langton's ant is on a plane with black and white squares. The ant can be facing north, south, east, or west. It follows these two rules, then moves forward:

1) If it is on a white square, it turns right; else (it is on a black square), it turns left.

2) The ant moves forward one square (in the direction it is facing) and the square it was on flips color.

A spreadsheet is the perfect place to implement Langton's ant. Enter a greater than sign, > (representing the ant facing east), in cell B13 below.

We can easily color a cell black (white is the default background color). Click cell C14 and then click the Fill Color button (the bucket in the Font group) to make it black.

Moving the ant is a little trickier. We will do it manually, applying the two rules, to see how it works.

At B13, the ant is on a white square so, following the first rule, it will turn right, becoming a v.

Following the second rule, it will move forward one square, down to cell B14, and the square it was on (B13) flips to black.

The ant is now in cell B14 and facing south so enter the letter v in cell B14.

Delete the > character in cell B13 and change the cell color to black to finish applying the second rule.

This is what cells B13:D15 should look like (if you followed the instructions above):

Can you walk through what the next move will be?

It is on a white square, so it turns left to <, then it hops to cell A14 and cell B14 flips to black.

Moving the ant manually quickly becomes tedious. We can automate the process with Excel's programming language, Visual Basic.

This workbook has macros that will enable Langton's ant to move by following the two simple rules.

It is not necessary, but if you want to see the code, press alt+F11 on your keyboard (or right-click the Intro sheet tab at the bottom left of this window and select View Code).

Read the instructions below before you play with Langton's ant in the Ant sheet.

When you go to the Ant sheet, you will see a controller floating above the screen (see below if you do not see this when you go to the Ant sheet).

Use the controller to move the ant around. Your goal is to generate the highway and understand what it means.

When you first arrive at the Ant sheet, add an ant (enter <, >, v, or ^ in any cell) and have it follow the two simple rules to move around.

Click the Move One Step button a few times to confirm that the ant is moving as expected, following the two rules.

To be able to see the direction the ant is facing, we use yellow instead of black as our non-white cell fill color.

Try the Many Steps button with a few hundreds steps.

If you click the check box, the macro runs much faster because it does not have to show each step. It computes the path and then displays it.

Starting from a completely white grid, Langton's ant starts to build the highway mentioned above around 10,000 steps (OK, the 9,978th step, to be exact).

To see the highway clearly, you need to run around 11,000 steps (starting from a blank grid).

After you confirm that the ant builds a highway, click the Reset button and create other grid patterns by filling some cells with yellow and then adding the ant and using the buttons to move around.

You can try typical geometric shapes (for example, a triangle) or a random smattering of yellow cells.

Do you find any interesting results?

Does the ant ever fail to build the highway? That would be a BIG deal.

After you are finished, take a look at the Lesson sheet to make sure you understand a key idea demonstrated by Langton's ant.

Proceed to the Ant spreadsheet and explore the properties and patterns of Langton's ant!

Software Requirements:

You need "desktop" (not online) Microsoft Excel, Windows version 2007 or greater to get full functionality from this file.

This file can be opened with Mac Excel, but it uses Visual Basic code that may not be fully supported on a Mac.

Online Excel can open this file, but none of the macros will run. You need to have Excel on your computer and open this file with your Excel application.

You must be sure to Enable Content or the buttons and code in this macro-enabled workbook will not work.

If you opened this workbook and did not enable macros, close it, open it again, and click the Enable Content button -->

Search "enable macros" in Excel's Help for more information on how to do this.