Langton’s ant

There are some interesting patterns/behaviours with Langton's ants.

In a wrap around world (e.g. moving off the left/right will enter the other side), the ant will collide with its "hive" (starting blob) or "highway" (diagonal pattern) and repeat a hive-highway construction cycle.

With two ants, depending on their starting position, they will end up in one of 3 patterns:

1. A hive-highway pattern like one ant;

2. As 1, but will collide with each other, then undo their construction until they go back to the beginning and then repeat this pattern;

3. Race around each other in an expanding diamond pattern. If the world is a wrap around world, when they reach one edge, they will start to undo/shrink the diamond, generating an expanding-collapsing diamond pattern.

It's also interesting playing around with more colours/states, and different rules (180deg turn, no turn).

With these generalized turmites, I've seen them create/use "super highway" constructs. -- A "super highway" is a straight line of a single colour where a turmite's behviour for that colour is to not turn. -- It will then race forward along that highway.

I used to play around with Langton's Ant a lot.

The longer patterns remind me of the climbable game assets in "Below the Root" and "The Jungle Book", early games by Dale Disharoon/DeSharone that I played on an Apple II compatible, though they were available on DOS and C64 as well.

I'd always assumed that Dale based his vines on Langton's Ant but the timeline doesn't add up. Dale's games came out several years earlier.

It is an interesting aesthetic subset of digital noise.

Worth noting that Dale also worked on the strange Legend of Zelda CDi games. He had an unusual arc.

https://www.uvlist.net/game-173637-Below+the+Root

http://blog.hardcoregaming101.net/2012/09/dale-desharone-uns...

Langton's ant is really cool, especially considering the extremely simple rules.

- At a white square, turn 90 degrees clockwise, flip the color of the square, move forward one unit.

- At a black square, turn 90 degrees counter-clockwise, flip the color of the square, move forward one unit.

If you look at the images and animations, you might think that it becomes repetitive quickly, and nothing interesting happens. But that is only if you have an infinite grid.

If you have a grid that wraps to the opposite side on the edges, it interacts with its own path a lot more. This produces very chaotic and "random" results. In fact, I've made a toy PRNG based on Langton's ant, and it does quite well on PractRand. It's not a performance king, far from it, but still really cool that two simple rules can do that.

It would be a fun project to make a (probably very slow) cipher based on Langton's ant.

Related:

Langton's Ant - https://news.ycombinator.com/item?id=20123626 - June 2019 (25 comments)

Hexagonal Langton's Ant 2 – Colors, Gliders and Highways - https://news.ycombinator.com/item?id=10324517 - Oct 2015 (13 comments)

Langton's ant - https://news.ycombinator.com/item?id=8265482 - Sept 2014 (42 comments)

Langton's ant - https://news.ycombinator.com/item?id=2230459 - Feb 2011 (20 comments)

Hah. That's a good memory. An implementation (simulation?) of Langton's Ant was the first program I wrote when I was learning COBOL for my mainframe job at >BIG FIN CORP< back in 2014.

See, COBOL doesn't have a console, and there weren't any graphical capabilities to speak off on the system I worked on, so I just "animated" the simulation by producing multiple static screens. But it worked.

I seem to have lost the source though, when I moved from that job.

I keep wondering about the dynamics of Langton's ant within an infinite adversarial environment. The game I have in mind retains the standard behavior and movement patterns of Langton's ant. However, it introduces an adversarial component: upon the ant's first encounter with any given tile, an adversary determines the initial color of the tile, either black or white. The adversary's influence is constrained to this initial tile color determination, without any additional intervention capabilities.

The adversarial objective is twofold: primary is the prevention of 'highway' construction by the ant, and secondary, if the primary objective cannot be fully achieved, is to disrupt the 'highways' as swiftly as possible post-formation.

I do not have a good intuition for who has the upper hand here. The adversary can be deliberate, but its influence is strictly limited to controlling initial conditions of the board.

Maybe this falls under the Cohen-Kong Theorem, or a potential extension of it. I'm not sure whether that applies here since the adversary may provide a board with finite support or may choose to instead provide a board (or board-generating procedure) with infinite support.

Here's my implementation from 2014 that let's you spawn more ants on the grid. http://code-art.chintanghate.me/LangtonsAnt.html

I always considered Rule 110 the simplest system (code complexity wise) that is turing complete:

https://en.wikipedia.org/wiki/Rule_110

I wonder if the Langton's ant algorithm (say in Javascript) is shorter.

My gut feeling is that it's about the same size. But maybe Langton's ant is shorter because it only needs a single loop.

In pseudo-code it is super simple:

    10 INVERT(X,Y)
    20 IF GETCOL(X,Y): TURNLEFT()
    30 ELSE          : TURNRIGHT()
    40 STEPFORWARD()
    50 GOTO 10

But an actual implementation would be quite a few more lines.

I was introduced to Langton's ant by the Science of Discworld books, which used it as an example of emergent phenomena.

This is so cool! Does the term "ant" here have any real-world implications to the behavior of ants, or is it simply a creative term? Obviously ants are known to build highways, but that's through use of pheromone trails rather than a very simple process of turning, right? But I guess the black/white configuration is a binary representation of a pheromone trail? So, maybe?

There’s a good discussion of this in one of my favourite books: William Gary Flake’s The Computational Beauty of Nature (1998).

Wow, that brings me back. My older brother wrote a Langton's ant program in QBasic, and one of my earliest computer memories was watching that thing go.

Nice. I implemented this in Sinclair BASIC on my ZX Spectrum about 35 years ago. :-)

On checking, I see it was brand new stuff at the time!

There must be a minecraft version of this critter somewhere.

I prefer Langton's Phage