MaxCodes.info - Langtons Ant's

Langton's Ants

      So I've been talking about Goblins alot lately, so id figure i'd give them a rest for now This time i'm going to be
talking about ants. And not just any ants either. Oh no. Today i'm talking about Langton's Ants. Whoa, calm down, dont everyone
freak out...Langtons Ants are a type of Cellular Automata. Cellular Automata are a type of state machine which are composed of a grid with each cell
represented by a state. A rather well-known implementation of Cellular Automata which has been well studied is Conways Game of Life.

      Whats interesting these algorithms, and why i choose Langtons Ants in particular, is that they have the potential
to exhibit whats called "emergent behavior". The short explaination of emergent behavior is that when certain components are put together as system
they behave in a way that they could not when on their own. A good example is a bicycle: when a rider and bicycle are combined, they are capable
of gliding foward in smooth movement, which the rider nor the bicycle could achieve without the other.

      Needless to say, these algorithms could be used for all sorts of things, like making your Goblins... oh sorry.
When properly applied these algorithms have interesting results. They work by implementing a set of rules that dictate the behavior or the system
as it exerts its effects on the grid. Langtons Ants has a strikingly simple rule set which makes it a good place to begin.
Most all cellular automata begin with whats called "chaotic behavior meaning that as you watch the steps progress, it appears to be all over
the place with no rhyme or reason. The emergent behavior component means that after a period of these chaotic movements, the system settles down,
or "emerges" into a stable, continuous cycle. Lets take a look.


Chaotic Movement

The rule set for Langtons is as follows:

  1. On a grid of cells, we randomly choose a position to place our "ant".
  2. The ant can move in any four of the cardinal directions N, S, E, W, or Up, Down, Left, and Right, depending how you want to look at it.
  3. To start every grid space colored white.
  4. The ants movement is dictated by the grid cells color:
    • If the ant is standing on a white cell the ant turns 90 degrees clockwise.
    • If the ant is standing on a black cell, the ant turns 90 degrees counter clockwise.
  5. After turning the cell the ants standing on flips colors, black cells become white and white cells become black.
  6. Once flipped the Ant moves foward.

I'll mention that in every description i've encountered mentions that the and is Red. I'm not quite sure
why that matters because the color of the ant doesn't change, and has no effect on state. So color your ant however
you like. Be a rebel, have a green ant.
As a matter of fact it doesnt even need to be an Ant. I could have the same rules and call it "Gorens Goblins."(groan).


Emergent behavior after 10k steps (note the organized spiral coming down from the right corner)
a very good view of the resultant behavior is available here

      In order to start, the first thing we need is a grid for the system. For our grid i'm using a 2d vector of Point's. I also
made two classes, antGrid and ant for handling the grid and the ant respectively:

     typedef uint32_t color_t;

     struct Point {
         int x, y;
         char s;
         color_t color;
     };

     class antGrid {
         private:
            std::vector<std::vector<Point> > layout; //this the grid for our ant
            int mapW;       //grid width
            int mapH;       //grid height
         public:
            void render(ant antbro); //for displaying grid
            void loop(Point spos);  //the driver to keep our ant stepping
            void cleanup(std::vector<string> report);    
            void saveOutput(std::vector<string> report); //saves the final grid to a text file
            antGrid(int h, int w);
     };

     class ant {
         private:
            Point spos; //starting position
            Point pos;  //current position
            int moves;  //for counting how many steps
            int mapW;   //grid width
            int mapH;  //grid height
            char facing; //the direction our ant is facing
            std::array<Points> cards;   //the values to add to the current position to change the ants direction
         public:
            std::vector<std::string> finalReport(Point fpos); //gathers all of the runtime stats to include in output file
            void render();                       //for showing our ant on the grid
            char updateFacing(bool cw);        //determine which direction our ant should face
            std::vector<std::vector<Point>> move(std::vector> layout);  //moves the ant and updates the grid.
            ant(int w, int h, Point loc);
     };
 

      In the code examples shown here i've removed the parts that deal with implementing an NCURSES interface, if you're interested in seeing how
that was handled, check out the GitHub repo for this project.

      our main function simply creates the instances of our grid object and ant object before calling antGrid's loop() function
which is what really drives the show. I'm going to cover the functions "in order of appearance", meaning how they are encountered
as the program is run, not how they're organized in the source files. With that in mind, lets take a look at int main(), the antGrid
constructor and loop() function.


#include "ants.h"

int main(int argc, char *argv[])
{ 
    int x, y;
    if (argc < 2)
    {
        cerr << "Please suplly a starting coordinate as " < < argv[0] < < " x y \n";
        return -1;
    }

    Point spos = {atoi(argv[1]), atoi(argv[2])};
    antGrid AntLife(200, 200);  //<---------------change these values to change grid size.
    AntLife.loop(spos);
    return 0;
}

      At launch our program readings the starting position as arguments from the command line, if these aren't supplied the program
quits. After that, antGrid is defined. we pass the grid width and height to the constructor and then call the main loop while passing
start position as an argument.


    antGrid(int w, int h)
    {
        this->mapW = w; //set the size of the "board"
        this->mapH = h;
        layout.resize(w, vector(h)); //resize the vector to accomodate our layout size.
        int x,y;
        for (x = 0;x < w; x++)
        {
            for (y = 0; y < h; y++)
            {
                layout[x][y].color = 0xFF000000; //start off with a completely white board
                layout[x][y].s = '#';           //ascii version '#' is white and ' ' is black.
            }
        }
    }

    void antGrid::loop(Point spos)
    {
      int k;  
      ant antbro(mapW, mapH, spos); //say hello to my little friend.
      while (true)
      {

        this->layout = antbro.move(this->layout, winds.win2); //call the ants move function
        if (layout[1][1].s == 'X')
        {                                             //before continuing check to if a the flag
            cleanup(antbro.finalReport(antbro.fpos)); //was set that execution is over
        }
        render(antbro); //show our progress
        this_thread::sleep_for(chrono::milliseconds(100)); //slow execution down to a watchable pace
      }
    }   

      Upon initialization the antGrid constructor resizes the 2d vector to an appropriate size for our grid. After that
it loops over the grid and sets the inital state of every tiles. the color is being represented by an unsigned int32
in 0xAARRGGBB format. To begin with every cell is white. Entering the loop we initialize the ant and begin our loop.
You might be wondering what that funky if() statement is all about. It's because when our ant steps "out of bounds"
execution stops. to signal this to the rest of the program we change position (1,1) on the grid's symbol to 'X'.
If that condition is true we call our cleanup function, otherwise we continue stepping through our cycles. lets
see whats going on in the move() function because thats pretty much where all of the action in this program takes
place, but first antBro is initialized by its constructor.

        ant::ant(int w, int h, Point loc)
        {
            cards[0] = {0,-1}; //N    by adding these values to the ants current position
            cards[1] = {0,1}; //S     we can dictate which cell to move to.
            cards[2] = {-1,0}; //W
            cards[3] = {1,0}; //E
            this->facing = 'N'; //start facing north - there is no mandatory starting direction or position
            spos = pos = loc; //starting position
            moves = 0;
            mapW = w;
            mapH = h;
        }

        std::vector> ant::move(std::vector> layout, WINDOW* win)
        {
            char d; //for retrieving direction
            //get the color of where the ant is.
            Point nPos; //tile of the next position
            
            color_t currentColor = layout[pos.x][pos.y].color; //get the color of the tile the ant is on
            if (currentColor == white)
            {
              this->facing = d = updateFacing(true);      //change direction as outlined in the rule set
              layout[pos.x][pos.y].color = black;         //based on the direction currently facing
              layout[pos.x][pos.y].s = '#';               //flip the tiles color.
            } else { 
              this->facing = d = updateFacing(false);   //same as above in reverse.
              layout[pos.x][pos.y].color = white;
              layout[pos.x][pos.y].s = ' ';
            }
            
            switch (d)                  //obtain the next tile based on the rule set.
            {
                case 'N': nPos = {pos.x + cards[0].x, pos.y + cards[0].y}; break;
                case 'S': nPos = {pos.x + cards[1].x, pos.y + cards[1].y}; break;
                case 'E': nPos = {pos.x + cards[3].x, pos.y + cards[3].y}; break;
                case 'W': nPos = {pos.x + cards[2].x, pos.y + cards[2].y}; break;
                default: break;
            }
  
            if (nPos.x > 0 && nPos.x < mapW && nPos.y > 0 && nPos.y < mapH)
            {
                this->pos = nPos;   //if the next tile is not out of bounds, make it the current tile.
                moves++;
            } else {
                msg = "Out of bounds during move #: "+to_string(moves);
                fpos = nPos;
                layout[1][1].s = 'X';        //if were out of bands, return to loop without changing position, layout[1][1].s = 'X'
            }                                //is used a flag to denote the ant's tour is over
            return layout;
        }

That really is the meat and potatoes of this program, ill break down the sequence for you, be cause the sequence
illustrates the algorithm.

  1. A the ant is placed on a tile whose position is arbitrary, as is the ants direction.
  2. The color of the tile the ant is currently standing on is obtained and evaluated:
    if the tile is white, the ant changes direction by turning to the right.
    if the tile is black the ant changes direction by turning to the left
  3. The color of the tile the and is standing on flips its color.
    a white tile would be come black, a black tile would become white.
  4. The ant moves foward one tile, and the process repeats.

The updateFacing function is past a boolean value representing a white/black tile as true/false
The new direction is determined based on the current direction and the color of the tile

    char ant::updateFacing(bool cw)
    {
    char cur = this->facing;
    if (cw)
    {
        if (cur == 'N') {
          this->facing = 'E'; 
          return facing;
        }
        if (cur == 'E') {
          this->facing = 'S'; 
          return facing;
        }
        if (cur == 'S') {
          this->facing = 'W'; 
          return facing;
        }
        if (cur == 'W') {
          this->facing = 'N'; 
          return facing;
        }
    }
    if (!cw)
    {
        if (cur == 'N') {
          this->facing = 'W'; 
          return facing;
        }
        if (cur == 'W') {
          this->facing = 'S'; 
          return facing;
        }
        if (cur == 'S') {
          this->facing = 'E'; 
          return facing;
        }
        if (cur == 'E') {
          this->facing = 'N'; 
          return facing;
        }
    }
    return facing;
}

The loop sequence repeats until the ant moves to a space off of the grid, at which point the algorithm terminates.
I added a quick function to save the resulting final grid as a text file:


        void antGrid::saveOutput(vector report)
        {
            int x, y;
            fstream antpic;
            antpic.open("langton.txt", ios::out|ios::trunc);
            if (antpic.is_open())
            {
                for (auto str : report)
                  antpic << str;
                for (x = 0; x < mapW; x++)
                {
                    for (y = 0; y < mapH; y++)
                    {
                        antpic << layout[x][y].s;
                    }
                    antpic << endl;
                }
                antpic.close();
            } else {
                cout<<"Error opening file for output.\n";
                antpic.close();
            }
        }
        

an example of the resulting text file can be viewed here The full source code for this project is
as always, available on my Github: Github repo


(c) 2020 Max Goren
MaxCodes.info


(c) 2020 Max Goren
MaxCodes.info