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

Quote:
Originally Posted by ceptimus View Post
Quote:
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.
__________________

:roadrun:
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.47701 seconds with 11 queries