View Single Post
Old 11-16-2014, 10:09 AM
JoeP's Avatar
JoeP JoeP is offline
[thanks] whisperer
Join Date: Jul 2004
Location: England/Miisaland
Gender: Male
Default Re: Simon Tatham's Puzzle Collection

Originally Posted by ceptimus View Post
Originally Posted by JoeP View Post
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.

Free thought! Please take one!

:unitedkingdom:   :southafrica:   :unitedkingdom::finland:       :eur:       :m&ms::m&ms::twix::twix: (rotated 180°):m&ms::m&ms:
Reply With Quote
Thanks, from:
ceptimus (11-16-2014), Ensign Steve (11-22-2014)
Page generated in 0.31091 seconds with 11 queries