Quote:
Originally Posted by ceptimus
Quote:
Originally Posted by JoeP
How's your untangle algorithm going, cep?
|
So I've written some code that models (and animates) Untangle as a physical system. The lines connecting the dots represent elastic bands trying to pull the dots closer to each other and I gave all the dots a positive charge so that they repel each other, especially when they get close, and that prevents all the dots from collapsing together into a black hole due to the elastic attractive forces.
Oh and I added some viscosity too, so the points don't just twang into position but move fairly smoothly - as though they are being dragged through treacle.
I started out with Hooke's law for the spring forces (force proportional to length) but I experimented and found it works best when the force is proportional to length cubed. I've kept the repulsion force using the standard Coulomb's law (inverse-square).
It works pretty great and smoothly at Untangling up to a few hundred points, but gets a bit slow and stuttery after that. It's very interesting to watch it working - although I am of course biased, being the proud author!
It sometimes solves the puzzle completely just using the model described above, but more often it gets stuck with just a few crossing lines around the outside edge. I found that at that stage (when the initial movements cease) the program can automatically freeze some of the outer points (that form a loop) in position and then remove all the repulsion forces - and the last few crossing points are then eliminated as the tension takes over.
|
This post is useless without a flash animation.