Drawbot: Added Traveling Salesman Problem and Gcode generation
On the whole I’m feeling very good about today. Here’s a little before and after. Click for a larger version.
The image on the left is the result after 20 minutes of calculating in Java with a “Greedy” TSP solution. Once it finishes generating the lines it saves it all to a gcode file. I wrote this in about two hours with long breaks to think while I pulled weeds and mowed. It’s brutally stupid code that works. It’s not ready for production yet because it doesn’t meet my standards in two important ways:
- Lines cross over each other.
- I need to store information about every single possible pair of points to run my algorithm. This eats a all the memory Java has access to, and forces me to resize images to ~250 pixels2.
Here is evidence of a solution from MakerBlock that doesn’t have either of these problems. I haven’t deciphered the python to figure out what they’re doing….yet. I’d like to be able to convert huge pictures in a few clicks with a nice progress bar.
On a less happy note, my Macbook Pro has finally given up the ghost and I can’t afford to replace it. My next development machine will probably be a Mac and I’ll be working a lot more in Java. I’m really falling in love with it’s many (many) time saving features.
Have you got pseudocode for a better TSP solver? Please share in the comments!
