Friday, November 21, 2008

Cellular automata lace

Hi folks!
This is an idea I'd been vaguely intending to develop for quite a while, but didn't get around to seriously implementing until last week.
So, a cellular automaton is a rule for taking a grid of binary numbers, and generating a new grid in which the value of each entry is determined by the previous entry in the same and adjacent squares. So, if you take a 1-dimensional cellular automaton, it takes a row of 1's and 0's, and makes a new row, and each entry is determined by the entry above it and it's two neighbours. They're extremely simple, but they can produce some suprisingly complex patterns.
My idea was to use this to generate lace patterns - the 1's represent holes, the 0's plain stitches. There are some technicalities to overcome - lace knitting has left- and right-leaning holes, and while you could just pick one and apply it everywhere, I wanted something which would reflect the way digits 'travel' in CA patterns, so that you would arrive at a pattern of left and right travelling lines, meeting, annihilating, generating new lines. You can do this in a reasonably canonical ways - by looking at the three digits on the previous row you can more or less say it's heading left or it's heading right. There are some cases where a choice needs to be made though, so I just choose these. This loses some of the generality, but isn't too bad.
Having made these choices, I wrote a short program to choose a cellular automata 'rule' at random, pick some starting conditions, and apply the rule to generate a pattern. A second program then looks through the 1's this gives, and by looking at the arrangement above them translates this into a pattern of K, YO, K2tog and SKP stitches. Putting the output of this into a spreadsheet then gives you a lace pattern, and best of all, this is all entirely automatic. One such spreadsheet is here(for now- may need to move that at some point). (alternate rows are plain)

There's a couple of problems - this particular pattern involves a lot of double yarn overs. I'm told you can manage this by working K1 P1 on the alternate row, but I suspect it may be neater to write a quick program to look through the pattern and eliminate these - I think that wouldn't obscure the pattern and might need to a nicer finished piece, as well as easier knitting. So I need to try those out and see which solution I prefer.
The other problem is that there aren't that many 1D cellular automata, 16, by my count. While CA were very much the motivation for doing this, I kind of feel that sticking with them is selling the lace pattern generating half of the programme a bit short - it could apply equally well to any binary grid. So while this is a good starting point, I'm thinking about maybe inventing some slightly more elaborate generating rules - a quick way would be to allow a block to be decide by the five blocks above it, or the previous two time steps. Another approach I'd like to try would be to replace the binary grid with trinary, which would give a much wider family of rules, then map all the 2's back to 1 to produce a grid to feed into the lacing programme.

So yes, let's to play with. I particularly wanted to mention this because there was an extremely timely xkcd comic about cellular automata. In fact, I think the CA he's talking about simulating the universe with there may well be the same one in my lace pattern, though I haven't looked too closely.

So, anyone for an extremely geeky shawl?


Clare said...

That sounds really cool! I can't wait to see one of the patterns turns out.

Kate said...

I think that has been done before, but I can't remember where I read about it. Maybe "Unexpected Knitting" by Debbie New? Or "Knitting Heretic" by Annie Modesit?

Jhadur said...

Debbie New uses cellular automata to make a cabled hat: (Ravelry link)
Is that the one you're thinking of?
I think this is quite different though. Aside from using lace techniques instead of cables, I'm trying to give it a sense of 'travel', with threads of YOs forming paths, with the CA rule telling you how these interact. The scale is also a big factor - I'm aiming to have something big enough that you can take in the pattern at a glance without knowing what the rules are.

But yes, there are definite similarities, and I'll make sure I mention it next time I write about this(hopefully when I have samples to show off!).


Kate said...

That is what I was thinking of, I had forgotten that it was cables and not lace. I wasn't taking you to task for copyright, I was concerned for preventing you from re inventing the wheel. It would have been frustrating to work that out from scratch only to find out that someone else had written about it, and you could have started where she left off!

Graeme said...

I knew something was wrong with our conversation the other day. The world of 1D binary CAs is not as restrictive as we thought- see here for more details!

Jhadur said...

Ah, sorry to come across so brusque there Kate. What I'm trying to say is I'm really interested in the broad structure here, the way your eye perceives the whole pattern, and if the underlying orderliness makes the pattern 'nice' somehow.

And ah, cool - looks like there's rather more variety than I'd thought! I like that these can be generated from a single block too, that would make for good triangular shawls.
I'm currently wondering too what you'd get if you had more than one rule operating in different segments to produce larger interactions - any ideas how well that is likely to work?

Kate said...

Um... you are making my brain hurt! I think I will just wait for you to post the pretty pictures and admire it then... ;-)

miya^^ said...

hmmm... looks a lot like Sierpinski's Gasket... but not :) man, that's a lot of stitches :P

also, what are you going to do about the sparse bits, but i've seen lots of shawls that are pretty holey!