Hi folks, I've just realised how long it's been since I've posted anything here, and I have a whole bunch of stuff waiting!
A few weeks (well, months) ago, I gave a talk in our PG Colloquium series on the subject of geometry and knitting. The idea was to show off a few mathematical knitting projects I've been playing with, and use them to illustrate some maths.
I'll write about the projects individually later, but in the meantime you can read the slides here:
Slides (pdf)
A couple of the projects used computer programs to calculate the patterns, based on inputted parameters. These programs are written in Ruby, and if you'd like to give them a try they can be found here:
Universal cover scarf
Cellular automata shawl
Hopefully their operation should be pretty clear, and is explained in more detail in the slides. If anyone's interested in knitting from these I'd be delighted to give some tips!
Also, thanks again to my Glamorous Assistant Pamela!
Also also, the Juliana hearts project is still ongoing, and open to all, so if I can send you one let me know. (Hmm, have I really not posted about that here before? More on that to follow then.)
Happy knitting, and more posts soon,
Hugh.
Showing posts with label CA. Show all posts
Showing posts with label CA. Show all posts
Friday, July 9, 2010
Monday, March 15, 2010
More on Cellular Automata
Hi again!
So, ages ago I talked about the possibility of using cellular automata to generate lace patterns. A key step in this is to interpret the cellular automaton as a collection of rules for interactions between chains of digits, travelling left or right, or remaining stationary.
On closer inspection it turns out this is rather more complicated than I'd expected. The problem is that these interpretations can be influenced by neighbouring digits, so:
looks like it should to be a left-travelling chain, but if the neighbouring digits are:
then we need to see this as a chain bifurcating into left-travelling and stationary chains. Worse, if it was
we would probably want to see this as two left-travelling chains running alongside each other.
Because of these problems, I think it is impossible to interpret general cellular automata as chains in this way -- what's needed is a non-local approach. What can be done is to come up with a procedure to read through the pattern and divide each of the `1' digits into chains travelling left, right, or remaining stationary (and some `orphan' digits left by themselves). This is then fairly straightforward to convert into a lace pattern.
I feel this is cheating a bit, it's not really in the spirit of cellular automata and there are a lot of arbitrary decisions to be made. There are further complexities I haven't dealt with -- how do you deal with chains bifurcating? Or colliding? So far my chains are just left hanging.
Still, it generates some very nice patterns with some interesting features. Mostly though I'm just enjoying the idea of computer-generated lace, there's something magical about putting in a set of logical rules and generating a pattern.
So, applying this to rule 30, generating the pattern starting from a single `1', I get something like this:
(not sure how that'll turn out, but it's just to give an impression)
So, this turns out to be rather more complicated than I'd expected, and very much less canonical than I'd hoped. It does produce viable patterns though, and makes me rather keen to try to elaborate this method.
Pictures of the finished shawl soon!
Hugh.
So, ages ago I talked about the possibility of using cellular automata to generate lace patterns. A key step in this is to interpret the cellular automaton as a collection of rules for interactions between chains of digits, travelling left or right, or remaining stationary.
On closer inspection it turns out this is rather more complicated than I'd expected. The problem is that these interpretations can be influenced by neighbouring digits, so:
001
-1-
looks like it should to be a left-travelling chain, but if the neighbouring digits are:
0010
0110
then we need to see this as a chain bifurcating into left-travelling and stationary chains. Worse, if it was
00110
01100
we would probably want to see this as two left-travelling chains running alongside each other.
Because of these problems, I think it is impossible to interpret general cellular automata as chains in this way -- what's needed is a non-local approach. What can be done is to come up with a procedure to read through the pattern and divide each of the `1' digits into chains travelling left, right, or remaining stationary (and some `orphan' digits left by themselves). This is then fairly straightforward to convert into a lace pattern.
I feel this is cheating a bit, it's not really in the spirit of cellular automata and there are a lot of arbitrary decisions to be made. There are further complexities I haven't dealt with -- how do you deal with chains bifurcating? Or colliding? So far my chains are just left hanging.
Still, it generates some very nice patterns with some interesting features. Mostly though I'm just enjoying the idea of computer-generated lace, there's something magical about putting in a set of logical rules and generating a pattern.
So, applying this to rule 30, generating the pattern starting from a single `1', I get something like this:
(not sure how that'll turn out, but it's just to give an impression)
So, this turns out to be rather more complicated than I'd expected, and very much less canonical than I'd hoped. It does produce viable patterns though, and makes me rather keen to try to elaborate this method.
Pictures of the finished shawl soon!
Hugh.
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?
Hugh.
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?
Hugh.
Subscribe to:
Posts (Atom)