While it's cool, I don't think it's particularly mysterious. When playing around with graphical algorithms you step on these kinds of patterns all the time.
+1 to that. I remember computer graphics classes in college where we'd basically start off with a fixed algorithm and then play around with random variables and steps and end up with stuff that looked amazing (even though noone really knew why!) :P
A simple breakdown of the algorithm:
1. Choose an order for the four directions UP, DOWN, LEFT, RIGHT.
2. Choose a starting point and add to list, draw white.
3. Add all neighboring points to list in order chosen in step 1. The points that are already added (even if now removed) or would be outside are omitted.
4. Let n be number of points drawn white, m number of points currently in list. Remove the point at list index n%m.
5. Color said point white and goto 3.
In order to understand what is going on, lets first discount the conditions for a point not to be added to the last. Lets say they were added but ignored when popped. We would then iterate over every other point in the list, because for every step, we both increment our list index, AND remove one element. If the directions at index 0, and 2 were then non opposite (i.e. left - top), then we would flood fill in left-top direction. If the directions were opposite we would first fill a line.
Anyway, we need not go deeper into what would happen after that, it was just to get a feel for it. Because we actually have those two conditions for not inserting a point into the list. This could probably be thought as giving rise to a pseudo random disturbance in our index picking.
If this approximation is accepted the algorithm looks like this
1. Choose an order for the four directions UP, DOWN, LEFT, RIGHT.
2. Choose a starting point and add to list, draw white.
3. Add all neighboring points to list in order chosen in step 1.
4. Let n be number of points drawn white, m number of points currently in list. Remove the point at list index Math.floor(n*(1+Math.random())%m.
5. Color said point white and goto 3.
From this we can get a feel for what is happening. The reason we proceed outwards is that we the points we color are more and more recently added (i.e. further out). The reason for the gaps is that we a) effectively increase our index by 2+a random small integer.
The reason that we start filling again from the beginning is not explained by the random model, but can be understood from the fact that in the original algorithm, when we reach the borders, n starts increasing faster than m. This is because there is a high chance that added points are illegal. Since n increases faster than m, n%m will wrap around, and we start drawing points with low indices again.
I am not completely sure about these points: I have not tested them, but they seem a likely explanation.
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.
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.)
Hi all, basically it has a lot to do with keeping the open array expanding at the same rate, as the open array expands the numbers that get pulled by the selectNode function are kept at the same spacing let pattern grow at the same rate on all size of the pattern.
Some of the patterns that get generated are really cool. Would be glad to know how it works, so if someone does drop you a line on Twitter, please do update all of us.
Seems like an example of a Rapidly-Exploring Random Tree (RRT) algorithm, mostly used in motion planning. Granted this display seems like the RRT* variant.
It is a great primer, particularly if you can look past the Wolfram "I invented everything, how awesome am I" language. Read up on some criticisms of it too, there are some things that are over-the-top, and a lot of "ink" (and bits..) has been spent on the subject.
yes I hate that attitude too actually "I invented everything, how awesome am I" .
I'm not here to defend it.
But still he deserve some recognition, afterall he is the first bringing AI to the masses with Alfa, and helped some million researcher's life with Mathematica. And, 10 years after NKS, these are somehow good results -> http://blog.stephenwolfram.com/2012/05/its-been-10-years-wha... ...
You can judge people from many different perspectives, but when it comes to "getting things done", you should step back and congratulate him. again, IMHO
