If you can't pick up a knotted piece of string without untying it, whatever you do, do not click that link!
Planarity
I have now been cursed with the knowledge of the most addictive flash game I've seen since Bubbels:
Tags: firstperson, toys
Current Music: Echo and the Bunnymen -- Pictures On My Wall ♬
25 Responses:
The Flash version gets horrendously slow around levels 25-30. Beyond there, it's basically unplayable.
And yes, a friend of mine has played up to there. Geez, that's a lot of nodes.
I found that some aspects of the optimal strategy didn't become obvious until the later levels. Mileage varies, of course.
What is your strategy? I hit level 4 and then lose all interest. I saw it late last year, tried it again, and I still find myself thinking about anything else. :)
I like unknotting string, but I think because I enjoy the physical/spatial manipulation more than the puzzle factor.
It's difficult to articulate. The userpic actually says it better than I can. *) I move all 4-nodes to the center and all 2- and 3-nodes to the outside, and I look for the edge of the cloud. I form the edge first and then untangle the middle bits, kind of like doing a jigsaw puzzle. Does that make sense?
Actually it does. Thanks, I'll give it a try next time I stumble on the game. :)
what other versions are there?
I usually play up to about level 20 or so, then my powerbook's screen isn't big enough. hehe.
http://web.mit.edu/xiphmont/Public/gPlanarity.html
A Cocoa version probably wouldn't be all that hard to write, either.
Oh crap, you've done it now!!!
And if we're listening to Echo songs, this one feels more like "Villiers Terrace". Ow.
Planarity is the new Tetris
there's a version in Simon Tatham's portable puzzle collection that can handle several hundred nodes easily.
the Multi-Touch Interaction video includes a planarity demo that lets you move multiple nodes simultaneously with your fingers.
This is the kind of thing I loved about your bookmarks... no better way to get through the work day than this!
Ugh. A while back, I came up with a system that allowed me to solve every level I tried. I basically turned it into mindless, time consuming drudge work, but I was STILL ADDICTED for a while.
Curious to know, what was the optimal strategy? I tried playing for a little while, and was mostly working on something that looked like a random-move algorithm with a cost function based on distance to 1st neighbors (basically, Metropolis Monte-Carlo with a Boltzman cost-function). So most of the time you move nodes closer to 1st neighbors, but occasionally you move one way off which helps untangle global knots. I also found that moves were only significant if they change the topography -- i.e., if you move a node across a line. Had me thinking of topoisomerases.
The game is actually rather similar to something I was doing awhile back while testing a spring embedder algorithm. In order to see how well the algorithm worked, I created a random connected graph with shuffled vertices (it looked like the output of the 'randomize' button in the game).
The algorithm just treats the edges as springs (the metal sproingy kind) and has all of the nodes repulse each other. The system computes forces on the nodes each round and adjusts the nodes position. The results are really neat looking animations (though perhaps not neat enough for xscreensaver) and an aesthetically-pleasing representation of the graph. The Eades 1984 spring embedder algorithm that most people tend to use doesn't explicitly remove overlap though (but it certainly helps) so you'd have to add a force for that characteristic, too.
It looks like someone created a variation of the algorithm for solving things like this puzzle: Using Spring Algorithms to Remove Node Overlapping (PDF).
Ah, found the link to the Peter Eades 1984 spring embedder algorithm (PDF). It's a well-written paper that's easy to implement, although this particular PDF is a very poorly-scanned copy.
I neglected to get back to you earlier on this. Let's see if I can explain this without getting too wordy.:-)
The first thing I did was click on each node and sorted them according to how many neighbors they had. If a node had two neighbors, I'd set them aside in a row near one of the corners. Same thing with nodes that had three neighbors -- I'd set a row of those nodes next to the twos.
That'd leave me a large clump of nodes with four neighbors. I'd check each one of those, and if one or more of their neighbors were back in the twos and threes, I'd set those fours in another row by the twos and threes. (Is this getting arduous and confusing yet?)
I'd keeping checking the unsorted fours to see if they had neighbors in the rows of nodes I'd made, and keep making rows until I finally came to the handful of nodes that were the most likely to be the innermost nodes of the web. Of course, as I went along, I'd find that the occasional two or three were among the innermost nodes, but it was just easier to snoop around the fours.
(This is harder to explain than it was to come up with.)
It wasn't a perfect or smooth solution, but when I had everything sorted out, it was mostly a time consuming matter of moving the sorted rows of nodes around to form the outer layers of the web.
Anything I need to clarify? Probably.:-)
OMG.
Chris will be so pleased. :)
Have you seen this one? Old meme, but a good one.
THAT WAS CRUEL
That shit was cold, man.
God damn you.
YMTS "if you ever spent an hour playing with that elastic node applet toy that Sun used as a Java demo".
actually, this game makes me wish for that instead. I just want to shake the damned assembly to settle some of the jumble out. Like I would with a tangled cord in RL.
I can't help but think "There's gotta be a computer program somewhere that would do this for me."
For your Treo, too!
http://web.mit.edu/xiphmont/Public/gPlanarity.html
This is quite a bit prettier.