Langton's Ant

https://en.wikipedia.org/wiki/Langton%27s_ant

by garycomtois • 7 years ago

115 25 7 years ago

en.wikipedia.org

Townley• 7 years ago

It's fascinating how after periods of stability and chaos, the ant eventually forms "highways" of regular behavior. Aside from fluid motion/sand in an hour glass, I can't think of many analogies in everyday life for this order > chaos > order pattern.

Alongside being interesting mathematically, multi-colored Langton's Ant videos are hypnotic to watch. The patterns they make are beautiful, and I'm embarrassed by how much I find myself rooting for this "ant" to make it as far as it can. https://www.youtube.com/watch?v=gZS7WtRE4_Y

pugworthy2• 7 years ago

Watching the video, it's noteworthy that this system that works and renders in a Cartesian coordinate system is able to essentially create 60 degree rotations of a pattern without any trig function.

Given that a rise of 1 and run of around 0.577 will give you approximately 60 degrees (60.01505399), I have to wonder if there is some correlation between that approximate ratio and the number of steps required to complete the pattern.

With that thought, it's noteworthy that the pattern isn't quite right when it finally comes back to the beginning - which essentially is a little bit of rounding error at the end. That makes sense if what I'm imagining to be a correlation above is true, because a slope/offset to create a perfect 60 degrees is an irrational number.

empath75• 7 years ago

It’s on a hexagonal grid.

pcwalton2• 7 years ago

30 and 60 degrees don't need trig functions. See: https://en.wikipedia.org/wiki/Trigonometric_constants_expres...

pavel_lishin• 7 years ago

I'd love to have that as a web-app that I could run in the background on the large TVs at work.

toufka• 7 years ago

That'd be really fun to have!

The elegance in these kinds of complex behaviors can be artistic in their own right.

plibither8• 7 years ago

Previous discussion on the same: https://news.ycombinator.com/item?id=8265482

garycomtois• 7 years ago

I came across while reading The Science of Discworld (https://en.wikipedia.org/wiki/The_Science_of_Discworld), in the chapter "Where do Rules Come From?" Learning more about the Ant was a fun little side quest.

iscrewyou• 7 years ago

Here's a simulator I found through Google: http://www.langtonant.com/

YeGoblynQueenne• 7 years ago

Heh. Langton's Ant was the first program I wrote when I was learning to program in Cobol on a mainframe, circa 2015, while working at <BIG FINANCIAL CORP>. I daresay I read about it in The Science of Discworld, like another commenter. The Cobol ant was not animated, mind- I just wrote out the end result after a sufficient number of iterations to get the characteristic shape, as in the wikipedia image.

I had a look though and I can't seem to find the code. Shame, as I think the square grid had a very natural representation in Cobol that gave me some nice insights about the language.

tombert• 7 years ago

This, and Conway's Game of Life, are my go-to for learning a new programming language, and I've written about 10 implementations of each.

They're in this nice, happy medium of "easy enough to not get frustrated" and "hard enough to not be trivial".

mbar84• 7 years ago

Years ago I wrote a sketch for the generalized form of langtons ant: https://pcsedit.appspot.com/#view/mbarkhau/langtons_ant.coff...

john-radio• 7 years ago

I don't understand. How is its behavior not completely pre-determined, if it follows a static algorithm and the initial conditions are always the same?

war1025• 7 years ago

It is predetermined. Just the same way Conway's Game of Life is predetermined. The interesting thing is when you have multiple of them or different beginning board states.

pcwalton2• 7 years ago

The behavior is predetermined. What is intriguing is that so much complex behavior emerges from simple rules.

jerf• 7 years ago

If you want the mind-blowing read on this, it is pre-determined, and contains very little information content; only the specification of the field, the rules, the initial state (often very compressible since it's one point), and the number of iterations it runs for. Add a dash of information for the coloration if you want to specify the image rather than the raw state.

And that's how quickly "low-information states" become very superficially-rich-seeming states. You'd think all the things you can represent with just a handful of bits would all be relatively boring or regular things, but this disproves that.

I often find myself boggling at just how little math it takes for our brains to be essentially completely incapable of handling it. If you gave a human who had never seen this before all the information above and asked them to guess what it would do, the odds of them being right are basically zero. And this hardly even wading in to the shallow end of the world of math and where we can get with more bits.

There's some ways we pride ourselves on how good at math we are, and there's some truth in that. But in other ways, we cognitively fall down and go splat on even the simplest systems.

Retra• 7 years ago

Speaking of the richness of low-information states... there's also a kind of opposite to this: a lack of richness of high-information states. Consider a beam of light entering a liquid like water. There's a great deal of noise and variation in the positions of the water molecules, but due to the low-dimension (3) of the space and the high density of the material, there is an inevitable kind of 'regularity' that makes the material act on aggregate as though it were simply a region of simple refraction, rather than a complex superposition of billions of electromagnetic interactions.

Actually, this is probably captured by the idea of randomness.

Sharlin• 7 years ago

Chaotic behavior is by definition deterministic. What it isn't is predictable in a certain well-defined sense.

ajmurmann• 7 years ago

Cellular automata and the Ant in particular have always been fascinating to me because of the complexity of behavior that emerges from very simple rules. This always has made me wonder if there are similarly simple rules at the foundation of our reality.

cr0sh• 7 years ago

Well...you might give this book a read:

https://www.wolframscience.com/nks/

xcombelle• 7 years ago

As far as I know, the general consensus is that Stephen Wolfram is smart, but most what is write is crap especially in this book.

puppyprogram• 7 years ago

Langton's ant will always be near and dear to my heart. It was the first program of my Intro to CS II course and also the point where I went from "Heh I think I can do this programming thing" to "Holy moly what did I get myself into?

aleyan• 7 years ago

When trying out rust, I wrote a little langton's ant implementation[1] that runs in the terminal. It includes the extensions to multiple colors as described in the wikipedia article. Of particular interest is that I ran the simulation and looked through all results of combination of up to 6 colors and included a list of the archetypal ones in the README [2]. It would be interesting to explore ants with larger rotation cycles, but it isn't really scalable to look through the results with human eyeballs. Perhaps there is a computer vision clustering algorithm that can be used to classify them.

[1] https://github.com/aleyan/langtonsant

[2] https://github.com/aleyan/langtonsant#interesting-ants

ddeokbokki• 7 years ago

If you're curious about implementations and some nice visuals, check out Challenge #173 of DailyProgrammer [1].

[1] https://www.reddit.com/r/dailyprogrammer/comments/2c4ka3/730...

Langton's Ant

Related Stories