Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

Cellular Automata :: Langton's Ant

by Elgon (Curate)
on Aug 19, 2004 at 16:36 UTC ( #384360=CUFP: print w/ replies, xml ) Need Help??

One of the things that has always amazed me is the ability of systems with extremely simple rules to exhibit "intelligent" or "chaotically ordered" behaviour. One such example is Langton's Ant, which follows such extremely simple rules and initially appears to behave chaotically, however after a certain number of steps a recurring pattern emerges.

The rules are as follows; An ant sits on a bit of graph paper where all the squares are initially empty. It moves into a neighbouring square and does one of two things, based on the colour of the square;

  1. If the square is white, it turns to the left and colours the square black.
  2. If the square is black, it turns to the right and colours the square white.

...and so on, ad infinitum. The interesting thing about this is that after a fixed number of steps, the ant builds a highway and hotfoots it into infinity. There are, in fact, any number of "ants" with different rules, however it has been proven that all of them which do not actually reverse their direction in a single move build highways and do not return to their starting position.

I got bored and wrote a program which models this behaviour. Feel free to play, although you'll probably need to build a bigger board to see the highway form. Trivial but very fun!

#! /usr/bin/perl -w # Use bondage and discipline use strict; use POSIX qw( ceil ); # Set up vars my $xmagnitude = 20; my $ymagnitude = 20; my @board; my %dir = ("x" => 0, "y" => -1); my $iterations = 1000; my $pause = 1; # Initialise board for (my $y = 0; $y < $ymagnitude; ++$y) { for (my $x = 0; $x < $xmagnitude; ++$x) { $board[$y][$x] = " "; } } # Find centre of board and X marks the spot my %pos; $pos{"x"} = ceil(($xmagnitude / 2) - 1); $pos{"y"} = ceil(($ymagnitude / 2) - 1); $board[$pos{"y"}][$pos{"x"}] = "X"; # start the loop my $count = 0; while ($count < $iterations) { system(($^O eq 'MSWin32') ? 'cls' : 'clear'); # Thx QandA Edit +ors map {print join ("", @$_)."\n"} @board; $pos{"x"} += $dir{"x"}; $pos{"y"} += $dir{"y"};; # Exit if out of bounds if($pos{"x"} >= $ymagnitude || $pos{"x"} < 0 || $pos{"y"} >= $ +xmagnitude || $pos{"y"} < 0) { print "\nAnt has reached the edge of the board!\n\n"; exit; } if ($board[$pos{"y"}][$pos{"x"}] eq "X") { # Turn left and make an O $board[$pos{"y"}][$pos{"x"}] = " "; # Remember your trig calculus my $tempvar = - $dir{"x"}; $dir{"x"} = $dir{"y"}; $dir{"y"} = $tempvar; } else { # Turn right and make an X $board[$pos{"y"}][$pos{"x"}] = "X"; # Remember your trig calculus my $tempvar = - $dir{"y"}; $dir{"y"} = $dir{"x"}; $dir{"x"} = $tempvar; } ++$count; sleep $pause; } # ##### End of Script ##### #

Update: This won't work on Win32 (yet.)

Update^2: This should work on Win32 now. Could someone test it please to check? Thx...

Update^3:Thanks to roju for testing on Win32. roju++

"Stercus! Dixit Pooh. Eeyore, missilis lux navigii heffalumporum iaculas. Piglet, mecum ad cellae migratae secundae concurras."

Comment on Cellular Automata :: Langton's Ant
Download Code
Re: Cellular Automata :: Langton's Ant
by roju (Friar) on Aug 19, 2004 at 18:45 UTC
    Tested on WinXP SP2. No problems in cmd.exe, emacs M-x shell or Cygwin's rxvt. Elgon++
Re: Cellular Automata :: Langton's Ant
by tachyon (Chancellor) on Aug 20, 2004 at 04:27 UTC

    For the impatient:

    - sleep $pause; + select undef, undef, undef, $pause/10; # small sleep

    It looks better with a 1/10 second delay IMHO.



      I must be *really* impatient, I took the pause out completely!

      Plus, I was getting ready to give up on it creating a "highway". It didn't become apparent until almost 40,000 iterations.

      Thanks for the kewl program! Elgon++
Re: Cellular Automata :: Langton's Ant
by ~~David~~ (Hermit) on Aug 20, 2004 at 15:42 UTC
    You can see the highway form with the following parameters:
    X magnitude = 75
    Y magnitude = 75
    Iterations = 50000
    (I also cranked up the speed or I would still be watching...)
      Highway appears near iteration 11000.
Re: Cellular Automata :: Langton's Ant
by Velaki (Chaplain) on Aug 21, 2004 at 02:46 UTC

    Thank for a cool program! Over lunch I whipped up a very quick and dirty Tk version.


    "Perl. There is no substitute."


      It struck me (having just just read LW's "State of the Onion 2004"), that if you sat and watched that in a room full of Freudian psychoanalysts, calling out all the things you saw as the Ant crawls around, you could very quickly raise them to near orgasm as you satisfied their every, "If I had a patient that displayed X form of neurosis, I'd write a paper and present it to...", wet dreams.

      Examine what is said, not who speaks.
      "Efficiency is intelligent laziness." -David Dunham
      "Think for yourself!" - Abigail
      "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://384360]
Approved by awwaiid
Front-paged by been42
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (9)
As of 2014-07-14 08:40 GMT
Find Nodes?
    Voting Booth?

    When choosing user names for websites, I prefer to use:

    Results (257 votes), past polls