Langton's ant

First program

For the grid we will simply use the screen itself.
Each pixel will represent one cell, and its color will be black or white accordingly to the rules.
We will start by initializing the screen and fill it with black pixels.

		#define SCREEN_WIDTH    640
		#define SCREEN_HEIGHT   480
		#define BLACK Color(0, 0, 0)
		#define WHITE Color(255, 255, 255)

		int main(int argc, char* argv[])
		{
			// init the window
			gfx.init("Langton's ant", SCREEN_WIDTH, SCREEN_HEIGHT);
			gfx.init2D();
			gfx.clearScreen(BLACK);

Then for the ant, we will need its x and y position and its direction.
For the direction we will use an integer that can take the following values:

0: the ant is turned towards the up
1: the ant is turned towards the right
2: the ant is turned towards the down
3: the ant is turned towards the left

This way if we want to turn the ant 90 degrees toward the right we just have to add 1 to this value, and of
course to turn left we will subsract 1.
We just need to be careful with the border cases like substracting 1 when the value is 0, but we'll see that later.

			int x = SCREEN_WIDTH / 2;
			int y = SCREEN_HEIGHT / 2;
			int dir = 0; // direction 0=up, 1=right, 2=down, 3=left

Then in our main loop we check if the ant is inside the screen

			// wait till the end
			while (sys.isQuitRequested() == false)
			{
				// if we are on the screen
				if (x >= 0 && x < SCREEN_WIDTH &&
				    y >= 0 && y < SCREEN_HEIGHT)
				{

We get the color of the pixel where the ant is

					// get current color
					Color   c = gfx.getPixel(x, y);

We check this value to turn the ant and change the color of the pixel.

					// turn and change color
					if (c.argb == BLACK.argb)
					{
						dir = (dir - 1 + 4) % 4; // turn left
						gfx.setPixel(x, y, WHITE);
					}
					else
					{
						dir = (dir + 1) % 4; // turn right
						gfx.setPixel(x, y, BLACK);
					}

Notice that for the turnings we take the modulo with 4, because we want a value between 0 and 3.
In the case we turn right, when dir = 3, if we add 1, we get 4, but because of the modulo, this value turns to 0.
In the case we turn left, if dir = 0, we have a problem because if we substract 1 we get -1.
Depending on the language you use the modulo of a negative value may not give the same result, and I'm not even
sure of what it should give in C.
So to avoid problems I add 4. As we take the modulo, adding 4 won't change the value of the result.

Now that our ant has turned, we will make it move forward. Here we just test all the cases.

					// move forward
					if (dir == 0)
					{
						y--; // up
					}
					else if (dir == 1)
					{
						x++; // right
					}
					else if (dir == 2)
					{
						y++; // down
					}
					else
					{
						x--; // left
					}
				}

And we end the main loop

				sys.processEvents();
				gfx.render();
				sys.wait(2);
			}

			gfx.quit();

			return EXIT_SUCCESS;
		}

		Download source code
		Download executable for Windows

Let's see what happens when we run this program.
At the beginning the ant seems to move randomly, drawing a complex pattern.

Then at a certain point it starts to repeat the same pattern, drawing a line that goes on forever.

This is called a highway - we'll see why later.
This automaton seems to always end up building a highway when it find an area full of black or white.
And you can modify this code to add white pixels in the center of the screen. No matter what the pattern you
choose, sooner or later the ant will escape this area and build its highway.

This is quite unexpected for a thing with so simple rules, but it seems that whatever the initial conditions are
the ant manages to "order" the pixels until it reach a configuration where it can build its highway.

Adding more players

Now let's see what happens when we have more than one ant.
We will use arrays for the x, y and dir variables and each ant will have a different color.

		int     x[10];
		int     y[10];
		int     dir[10];
		Color   col[10];

We initialize these values randomly.

		srand(time(NULL));
		for (int i = 0; i < 10; ++i)
		{
			x[i] = rand() % SCREEN_WIDTH;
			y[i] = rand() % SCREEN_HEIGHT;
			dir[i] = rand() % 4;
			col[i] = Color(rand() & 0xff, rand() & 0xff, rand() & 0xff);
		}

And process them in the main loop.

		while (sys.isQuitRequested() == false)
		{
			for (int i = 0; i < 10; ++i)
				lang(x[i], y[i], dir[i], col[i]);

			sys.processEvents();
			gfx.render();
			sys.wait(2);
		}

The lang() function contains the same code we saw before with only a small modification for the color.

		void lang(int &x, int &y, int &dir, Color& col)
		{
			// if we are on the screen
			if (x >= 0 && x < SCREEN_WIDTH &&
			    y >= 0 && y < SCREEN_HEIGHT)
			{
				// get current color
				Color   c = gfx.getPixel(x, y);

				// turn and change color
				if (c.argb == BLACK.argb)
				{
					dir = (dir - 1 + 4) % 4; // turn left
					gfx.setPixel(x, y, col);
				}
				else
				{
					dir = (dir + 1) % 4; // turn right
					gfx.setPixel(x, y, BLACK);
				}

				// move forward
				if (dir == 0)
				{
					y--; // up
				}
				else if (dir == 1)
				{
					x++; // right
				}
				else if (dir == 2)
				{
					y++; // down
				}
				else
				{
					x--; // left
				}
			}
		}

		Download source code
		Download executable for Windows

If you run this program several times you will see some interesting behaviors.

While most of the ants quickly reach the border of the screen and stop, sometimes the interaction between two ants
makes them enter in a complex cycle and they never exit the screen.

Some ants will decide to turn around and undo all the pixels they drew when they touch the pixels of another ant.

And when an ant meets a highway drawn by another one, most of the time it will follow it at high speed.
That's probably where the "highway" name comes from.

Adding colors

So far we only played with ants that live in a world that can only take 2 colors. Mut how can we add more colors to
this automaton ?

First, let's remember that the ant's actions are linked to the colors.
We had 2 colors - black or white - and the ant had 2 actions - turn left or turn right.

If we keep these 2 actions, we can define the behavior of the ant when we have more colors as a string of letters.
We will use the letter "L" for left and "R" for right.
For example the string "RLR" would define the rules for an ant with 3 colors. The first letter gives the action
when the ant is on a pixel of color 0, the second letter is for color 1 and the third letter is for color 2.

So, we will have a "rule" that defines the number of colors of the automaton.

		char    rule[] = "RLR";
		int     nbColors = strlen(rule);

We will use a palette for these colors. It is initialized with random colors except the color 0 which is black.

		Color*  palette;

		// init palette
		srand(time(NULL));
		palette = new Color[nbColors];
		palette[0] = Color(0, 0, 0);

		for (int i = 1; i < nbColors; i++)
		{
			palette[i] = Color(rand() % 256,
			                   rand() % 256,
			                   rand() % 256);
		}

As it will not be easy to retrieve the color number from its RGB value as we did with black and white, we will
store these numbers in an array that is initialised with 0s.

		int     world[SCREEN_WIDTH][SCREEN_HEIGHT];

		// init world
		for (int yy = 0; yy < SCREEN_HEIGHT; yy++)
			for (int xx = 0; xx < SCREEN_WIDTH; xx++)
				world[xx][yy] = 0;

Now, in the main loop, we first get the color where the ant is

		// wait till the end
		while (sys.isQuitRequested() == false)
		{
			// if we are on the screen
			if (x >= 0 && x < SCREEN_WIDTH &&
			    y >= 0 && y < SCREEN_HEIGHT)
			{
				// get current color
				int c = world[x][y];

We decide to turn left or right according to the letter in the rule that corresponds to this color:

				// turn
				if (rule[c] == 'R')
				{
					dir = (dir + 1) % 4; // turn right
				}
				else
				{
					dir = (dir - 1 + 4) % 4; // turn left
				}

To change the color of the cell, in the 2 colors world we turned a black cell to white and vice versa.
Here we will set the cell to the following color in the palette.

				// change color
				c = (c + 1) % nbColors;
				world[x][y] = c;
				gfx.setPixel(x, y, palette[c]);

And we move forward...

				// move forward
				if (dir == 0)
				{
					y--; // up
				}
				else if (dir == 1)
				{
					x++; // right
				}
				else if (dir == 2)
				{
					y++; // down
				}
				else
				{
					x--; // left
				}
			}

		Download source code
		Download executable for Windows

As the ants are more complex now, we will get different results depending on the rule we set in this program.
The rule "RLR" will produce a random pattern, but the ant will never build a highway.

The rule "RLLR" creates a square structure with complex patterns inside.

The rule "RLRRRRLLLR" creates another square that looks simpler.

The rule "RLRRRRLLLR" is probably the strangest. It produces a triangular shape that grows and moves downwards.