4 ms·

OP (well, discoverer of the algorithm) here: Thing is there is no per-step randomness. The small integer (pickOffset) only adds some variation to the algorithm

by akx 14y ago

OP (well, discoverer of the algorithm) here: Thing is there is no per-step randomness. The small integer (pickOffset) only adds some variation to the algorithm, and is initialized only when you hit Space. I'm pretty sure that if pickOffset was changed on each step(), the magic would be lost. What I'm wondering is why this simple change of the picking algorithm (open.pop(nStep % open.length) instead of open.pop(0) (simple radial outward fill)) causes this beautiful, organic sort of pattern to emerge.

gjm11 14y ago
I haven't thought this through very carefully and it may be twaddle, but: With pop(0) you have a queue, you always take out the oldest thing in it, and so you get breadth-first search. Instead you're doing pop(0) then pop(1) then pop(2), etc., which means you're taking out "every other" entry from the queue. (Until the popping overtakes the adding, which happens around about the time when a typical newly explored pixel generates fewer than 2 new neighbours to explore, by which time most of the interesting pattern generation has already happened.) Now, when any pixel is processed its (not-yet-visited) neighbours get pushed consecutively. That means that when the exploration process reaches them it'll only explore one or two of them. In the usual "early" case there are three such neighbours; half the time one will get explored, half the time two will. The other neighbours get left behind until the exploration wraps (i.e., "step" passes the end of the queue), which doesn't happen for ages. Hence the branching tree structure you see: right at the start we explore only two of the starting pixel's four neighbours, and the other two get left behind; so now we have two growing "tips", and when we process each one we either grow it one step further or split it two ways. And we don't return to the other neighbours for ages, so the tree grows basically until it fills the available space before the gaps start getting filled in. (There are plenty of details not explained by the above. More thought required.)
im3w1l 14y ago
There is no per-step randomness, but per step chaos, which looks like per step randomness.

by akx 14y ago

gjm11 14y ago

I haven't thought this through very carefully and it may be twaddle, but: With pop(0) you have a queue, you always take out the oldest thing in it, and so you get breadth-first search. Instead you're doing pop(0) then pop(1) then pop(2), etc., which means you're taking out "every other" entry from the queue. (Until the popping overtakes the adding, which happens around about the time when a typical newly explored pixel generates fewer than 2 new neighbours to explore, by which time most of the interesting pattern generation has already happened.) Now, when any pixel is processed its (not-yet-visited) neighbours get pushed consecutively. That means that when the exploration process reaches them it'll only explore one or two of them. In the usual "early" case there are three such neighbours; half the time one will get explored, half the time two will. The other neighbours get left behind until the exploration wraps (i.e., "step" passes the end of the queue), which doesn't happen for ages. Hence the branching tree structure you see: right at the start we explore only two of the starting pixel's four neighbours, and the other two get left behind; so now we have two growing "tips", and when we process each one we either grow it one step further or split it two ways. And we don't return to the other neighbours for ages, so the tree grows basically until it fills the available space before the gaps start getting filled in. (There are plenty of details not explained by the above. More thought required.)

im3w1l 14y ago

There is no per-step randomness, but per step chaos, which looks like per step randomness.