{"id":222,"date":"2013-03-10T15:54:05","date_gmt":"2013-03-10T14:54:05","guid":{"rendered":"http:\/\/blog.johannes-beck.name\/?p=222"},"modified":"2020-06-19T21:07:21","modified_gmt":"2020-06-19T19:07:21","slug":"travelling-salesman-problem-in-javascript-canvas","status":"publish","type":"post","link":"https:\/\/blog.johannes-beck.name\/?p=222","title":{"rendered":"Travelling Salesman Problem in JavaScript Canvas"},"content":{"rendered":"<p>A long a time ago &#8211; when I was student at university &#8211; I wrote a small, but somewhat impressing program. It is a heuristic (and thus suboptimal) solver for the travelling salesman problem, using an algorithm from the field of neuronal network which is called a <em>self organizing feature map<\/em><\/p>\n<p>You can read details on the neuronal network and the algorithm in my university paper <a href=\"https:\/\/johannes-beck.name\/university\/neuro\/tsp.pdf\">self organising maps based on a Kohonen neuronal network<\/a> (in german) or follow the literature references given.<\/p>\n<p>Now I took the chance of a rainy winter evening to convert the original code to JavaScript and render the output with the <a href=\"http:\/\/www.w3.org\/html\/wg\/drafts\/2dcontext\/html5_canvas\/\">HTML5 Canvas 2D API<\/a> &#8211; for me the chance to learn and keep up with the different HTML5 specs which have now step by step have become reality. So first have a look on the application:<\/p>\n<div><script type=\"text\/javascript\" src=\"https:\/\/johannes-beck.name\/js\/salesman.js\"><\/script><script type=\"text\/javascript\" src=\"https:\/\/johannes-beck.name\/js\/jquery-1.9.1.min.js\"><\/script><\/p>\n<section id=\"content\" style=\"width: 1000px; padding-top: 20px;\"><canvas id=\"canvas\" width=\"540\" height=\"480\" style=\"float:left; border: 1px solid silver; background: url(http:\/\/johannes-beck.name\/images\/grid-20-20.png) top left; display: block; margin-left: 20px;\"><\/canvas><br clear=\"all\"><\/p>\n<form id=\"parameters\" style=\"float:left; margin-left: 2em; margin-right: 1em; margin-top: 0; margin-bottom: 0; width: 450px;\">\n<fieldset>\n<h3 style=\"padding-top: 0px; font-size: x-large\">Parameters<\/h3>\n<p><label for=\"cities\">No. of cities<\/label><input id=\"cities\" type=\"number\" name=\"cities\" size=\"4\" maxlength=\"4\" style=\"margin-left: 10px;\"><br \/>\n<label for=\"maxCycles\">Max. No. of cycles<\/label><input id=\"maxCycles\" type=\"number\" name=\"maxCycles\" size=\"4\" maxlength=\"4\" style=\"margin-left: 10px;\"><br \/>\n<label for=\"gain\">Gain<\/label><input id=\"gain\" type=\"number\" name=\"gain\" size=\"3\" maxlength=\"3\" style=\"margin-left: 10px;\"><br \/>\n<label for=\"alpha\">\u03b1<\/label><input id=\"alpha\" type=\"number\" min=\"0\" step=\"any\" name=\"alpha\" size=\"6\" maxlength=\"6\" style=\"margin-left: 10px;\"><br \/>\n<input id=\"run\" type=\"button\" value=\"Run\" style=\"margin-right: 10px;\"><input id=\"stop\" type=\"button\" value=\"Stop\" disabled=\"disabled\"><\/fieldset>\n<fieldset>\n<h3 style=\"padding-top: 0px; font-size: x-large;\">Simulation status<\/h3>\n<p><label for=\"cycle\">Cycle<\/label><input id=\"cycle\" type=\"text\" name=\"cycle\" disabled=\"disabled\" size=\"4\" style=\"margin-left: 10px;\"><br \/>\n<label for=\"length\">Length of tour<\/label><input id=\"length\" type=\"text\" name=\"length\" disabled=\"disabled\" size=\"16\" style=\"margin-left: 10px;\"><br \/>\n<label for=\"done\">Finished?<\/label><input id=\"done\" type=\"checkbox\" name=\"done\" disabled=\"disabled\" style=\"margin-left: 10px;\" <=\"\" fieldset=\"\"><\/fieldset>\n<\/form>\n<\/section>\n<p><script type=\"text\/javascript\">$(document).ready(function() {var tsp = new TravelingSalesman(); tsp.setupForm();});<\/script><\/p>\n<\/div>\n<p>If you look at the JavaScript code, the part which takes care of the painting is remarkable simple, consisting of 3 sections.<br \/>\nCreating the drawing context on the canvas element:<br \/>\n<code><br \/>\nelem = document.getElementById('#canvas');<br \/>\nctx = elem.getContext('2d');<br \/>\nheight = elem.height;<br \/>\nwidth= elem.width;<br \/>\n<\/code><br \/>\nDrawing the cities as filled circles:<br \/>\n<code><br \/>\nvar centerX = city.x * width + 0.5;<br \/>\nvar centerY = height - city.y * height + 0.5;<br \/>\nctx.fillStyle = \"#C06060\";<br \/>\nctx.beginPath();<br \/>\nctx.arc(centerX, centerY, 3, 0, Math.PI*2, true);<br \/>\nctx.closePath();<br \/>\nctx.fill();<br \/>\n<\/code><br \/>\nand drawing the candidates and connecting them to a tour:<br \/>\n<code><br \/>\nctx.strokeStyle = \"#80D080\";<br \/>\nctx.beginPath();<br \/>\n\/\/ move to first node<br \/>\nn = neurons.start;<br \/>\nctx.moveTo(n.x * width + 0.5, height - n.y * height + 0.5);<\/code><\/p>\n<p><code>for each node n<br \/>\n\/\/ each node as a small dot<br \/>\nvar centerX = n.x * width + 0.5;<br \/>\nvar centerY = height - n.y * height + 0.5;<br \/>\nctx.fillStyle = \"#208020\";<br \/>\nctx.fillRect(centerX, centerY, 1, 1);<br \/>\n\/\/ draw a line to the next node<br \/>\nctx.lineTo(n.right.x * width + 0.5, height - n.right.y * height + 0.5);<\/p>\n<p><\/code><code>\/\/ draw all lines<br \/>\nctx.lineWidth = 1;<br \/>\nctx.stroke();<br \/>\nctx.closePath();<br \/>\n<\/code><\/p>\n<p>You can checkout the source code here: https:\/\/github.com\/kifj\/tsp-js<\/p>\n","protected":false},"excerpt":{"rendered":"<p>A long a time ago &#8211; when I was student at university &#8211; I wrote a small, but somewhat impressing program. It is a heuristic (and thus suboptimal) solver for the travelling salesman problem, using an algorithm from the field of neuronal network which is called a self organizing feature map You can read details [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23,3],"tags":[37,64,40,38,39],"class_list":["post-222","post","type-post","status-publish","format-standard","hentry","category-javascript","category-software-development","tag-html5-canvas","tag-javascript","tag-kohonen-network","tag-neuronal-network","tag-traveling-salesman-problem"],"_links":{"self":[{"href":"https:\/\/blog.johannes-beck.name\/index.php?rest_route=\/wp\/v2\/posts\/222","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.johannes-beck.name\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.johannes-beck.name\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.johannes-beck.name\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.johannes-beck.name\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=222"}],"version-history":[{"count":45,"href":"https:\/\/blog.johannes-beck.name\/index.php?rest_route=\/wp\/v2\/posts\/222\/revisions"}],"predecessor-version":[{"id":1407,"href":"https:\/\/blog.johannes-beck.name\/index.php?rest_route=\/wp\/v2\/posts\/222\/revisions\/1407"}],"wp:attachment":[{"href":"https:\/\/blog.johannes-beck.name\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=222"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.johannes-beck.name\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=222"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.johannes-beck.name\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=222"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}