YouTube Videos

A Simple Neural Network
KotlinConf 2018 - Mathematical Modeling
Creating a Sudoku Solver from Scratch
Traveling Salesman Problem
Text Categorization w/ Naive Bayes
Monty Hall Problem
Solving World's Hardest Sudoku

Saturday, October 6, 2018

Animating the Traveling Salesman Problem with JavaFX

Untitled Document.md

Animation can be a powerful tool. It is one thing to explain a complex topic in words or even in pictures, but visuals in motion have an amazing quality to bring abstract ideas to life. This can be especially helpful in complex areas of computer science like optimization and machine learning.

I recently gave a talk at KotlinConf on optimization and machine learning. Of the several examples, one was the Traveling Salesman Problem (a.k.a. “TSP”). This is such a fun and fascinating problem and it often serves as a benchmark for optimization and even machine learning algorithms. However, explaining some of the algorithms (like k-opt and simulated annealing) is less intuitive without a visual aid. Therefore, I made this an open-source project using JavaFX via TornadoFX.

A lot of folks at the conference and online were surprised by the animated visuals, remarking how “integrated” and slick it looked. The truth is I hacked this application together and JavaFX was instrumental in the heavy lifting. It took care of the animation for me so I could focus on the algorithm itself. This is what I want to blog about in this article.

You can watch the video walkthrough of this application (with a thorough explanation of the TSP) here. I recommend watching this before reading on!

The focus of this blog post will be on the animation and how it was achieved. For an in-depth explanation of the TSP and how it can be solved, please watch the above video.

The Structure

To build this, let’s first lay out the structure of our visual framework. I am going to express this in the Kotlin language, and leverage JavaFX via TornadoFX. Thankfully, TornadoFX does not hide or supresss any of JavaFX’s functionality, but rather augments it with expressive Kotlin DSL’s. So you can do this in Java, Kotlin, Scala, or any JVM language that can use JavaFX.

The first thing I’m going to do in my application is declare a Pane, and place in it an ImageView with a simple map image of Europe. Then from my domain model, I’ll import my City objects and place a red Circle on the x and y screen coordinates relative to the Europe map. Finally, I’ll import the Edge objects from my domain where each one is tied to a City, and bind each one to a Line. Each Edge represents a connection between two cities, and it is initialized with the start point and end point being the same city. Therefore, the Line will initialize by resting inside the Circle as a little dot. The Line will also be bound to the startX, endX, startY, and endY properties of its owning Edge.

pane {
    imageview(Image("europe.png")) {
        fitHeight = 1000.0
        fitWidth = 1000.0

        CitiesAndDistances.cities.forEach { city ->
            circle(city.x,city.y,10.0) {
                fill = Color.RED
            }
        }

        Model.edges.forEach { edge ->
            line {
                startXProperty().bind(edge.edgeStartX)
                startYProperty().bind(edge.edgeStartY)
                endXProperty().bind(edge.edgeEndX)
                endYProperty().bind(edge.edgeEndY)
                strokeWidth = 3.0
                stroke = Color.RED
            }
        }
    }
}

At this point, I should have something that renders like this:

When we animate, we will change each Edge’s startX, endX, startY, and endY properties. When we want to connect two cities, for instance, I can change the endX and endY properties to make that line extend to that other city’s coordinates.

Planning the Animation

With this structure in place, I did have to make a few considerations next. Should I animate the algorithm in live time or queue up the animations and make them replayable? Did I want to animate every single thing the algorithm did or filter out the noise and animate only the key events?

These decisions may seem unimportant at first glance, and I even told myself “why not animate everything?”. Of course, this backfired quickly because the animations already slow down the algorithm… and animating unproductive events in the algorithm only added noise. This also made the animation incredingly long and boring.

So what are unproductive events, you ask? Well, the algorithm works by doing thousands of random Edge swaps as explained in the video. When the swap did not improve the solution (or it failed the coin flip in the Simulated Annealing approach), I would undo the swap and put everything back. I learned it was best to not animate these events because most iterations were failed swaps, and it was better to animate successes to show progress rather than every iteration including failures.

Another adapatation I ultimtely made is running the algorithm first, and then animating the results. This had the benefit of being able to replay the results without having to run the entire process again. The key utility I needed in the JavaFX library is the SequentialTransition, which allows me to queue up animations and have them played in order (rather than all at once). I can then have my algorithm add animations to the SequentialTransition and it can be played later when it is done.

I stored each algorithm (“GREEDY”, “TWO-OPT”, “SIMULATED_ANNEALING”, etc) as an enumerable so I gave each one its own SequentialTransition. I also created some convenient extension functions so I could use += operators to add animations.

enum class SearchStrategy {

    RANDOM {
        ... 
    },

    GREEDY {
        ... 
    },

    REMOVE_OVERLAPS {
        ... 
    },
    TWO_OPT {
        ... 
    },

    SIMULATED_ANNEALING {
        ... 
    }
    
    val animationQueue = SequentialTransition()

    abstract fun execute()
}


// extension functions for SequentialTransition
operator fun SequentialTransition.plusAssign(timeline: Timeline) { children += timeline }
fun SequentialTransition.clear() = children.clear()
operator fun SequentialTransition.plusAssign(other: SequentialTransition) { children.addAll(other) }

And of course, I set a speed as a constant that defines how long each animation frame takes.

// animation parameters
var speed = 200.millis

Executing a Path Traversal

On the domain model side, I have Edgeitems that initially belong to one City. However, the startCity and endCity can be mutated and on each mutation, the Edge has an animateChange() function returning a deferred Timeline that will play that change.

But here is the interesting design decision I ended up doing. I created the edgeStartX, edgeStartY, edgeEndX, and edgeEndY to not be synchronized to their respective startCity and endCity. Rather, these are used purely for animation execution. When I decide to animate a change in the startCity or endCity, I call animateChange() to create a Timeline that animates the coordinate changes. It will take the current value in each JavaFX property holding the coordinate values, and animate it by gradually increasing/decreasing to the specified value in that amount of time (which is the speed of the KeyFrame).

Note though this Timeline does not execute, that is up to the function caller on how to use that animation.

class Edge(city: City) {

    val startCityProperty = SimpleObjectProperty(city)
    var startCity by startCityProperty

    val endCityProperty = SimpleObjectProperty(city)
    var endCity by endCityProperty

    val distance get() = CitiesAndDistances.distances[CityPair(startCity.id, endCity.id)]?:0.0

    // animated properties
    val edgeStartX = SimpleDoubleProperty(startCity.x)
    val edgeStartY = SimpleDoubleProperty(startCity.y)
    val edgeEndX = SimpleDoubleProperty(startCity.x)
    val edgeEndY = SimpleDoubleProperty(startCity.y)

    fun animateChange() = timeline(play = false) {
            keyframe(speed) {
                keyvalue(edgeStartX, startCity?.x ?: 0.0)
                keyvalue(edgeStartY, startCity?.y ?: 0.0)
                keyvalue(edgeEndX, endCity?.x ?: 0.0)
                keyvalue(edgeEndY, endCity?.y ?: 0.0)
                keyvalue(Model.distanceProperty, Model.totalDistance)
            }
        }
}

This particular function is used to expand an Edge for the first time to another city, which happens in the GREEDY and RANDOM algorithms. Stiching these together in a sequence results in a path traversing slickly to create a round-trip. Here is how the animateChange() function is leveraged in the RANDOM algorithm. Note how when I traverse to each random City, I connect each consecutive Edge pairs by their startcity and endCity respectively. Then I call animateChange() to return a Timeline and add it to the animationQueue.

RANDOM {
    override fun execute() {
        animationQueue.clear()

        val capturedCities = mutableSetOf<Int>()

        val startingEdge = Model.edges.sample()
        var edge = startingEdge

        while(capturedCities.size < CitiesAndDistances.cities.size) {
            capturedCities += edge.startCity.id

            val nextRandom = Model.edges.asSequence()
                    .filter { it.startCity.id !in capturedCities }
                    .sampleOrNull()?:startingEdge

            edge.endCity = nextRandom.startCity
            animationQueue += edge.animateChange()
            edge = nextRandom
        }
        
        Model.bestDistanceProperty.set(Model.totalDistance)
    }
}

My UI can then call animationQueue.play() to execute that change when the green play button is pressed.

Executing a Swap

Swaps are a bit more tricky than animating a path traversal. When TWO_OPT or SIMULATED_ANNEALING algorithms select random edges and try to swap their cities (vertices) somehow, sometimes it will fail and sometimes it will succeed. A failure can happen if a swap breaks the tour, and the reverse() function will be called. If it is successful, an animate() function can be called and return a Timeline that waits to be queued or executed.


class TwoSwap(val city1: City,
          val city2: City,
          val edge1: Edge,
          val edge2: Edge
) {

fun execute() {
    edge1.let { sequenceOf(it.startCityProperty, it.endCityProperty) }.first { it.get() == city1 }.set(city2)
    edge2.let { sequenceOf(it.startCityProperty, it.endCityProperty) }.first { it.get() == city2 }.set(city1)
}
fun reverse() {
    edge1.let { sequenceOf(it.startCityProperty, it.endCityProperty) }.first { it.get() == city2 }.set(city1)
    edge2.let { sequenceOf(it.startCityProperty, it.endCityProperty) }.first { it.get() == city1 }.set(city2)
}


fun animate() = timeline(play = false) {
        keyframe(speed) {
            sequenceOf(edge1,edge2).forEach {
                keyvalue(it.edgeStartX, it.startCity?.x ?: 0.0)
                keyvalue(it.edgeStartY, it.startCity?.y ?: 0.0)
                keyvalue(it.edgeEndX, it.endCity?.x ?: 0.0)
                keyvalue(it.edgeEndY, it.endCity?.y ?: 0.0)
            }
        }
        keyframe(1.millis) {
            sequenceOf(edge1,edge2).forEach {
                keyvalue(Model.distanceProperty, Model.totalDistance)
            }
        }
    }

}

fun attemptTwoSwap(otherEdge: Edge): TwoSwap? {

    val e1 = this
    val e2 = otherEdge

    val startCity1 = startCity
    val endCity1 = endCity
    val startCity2 = otherEdge.startCity
    val endCity2 = otherEdge.endCity

    return sequenceOf(
        TwoSwap(startCity1, startCity2, e1, e2),
        TwoSwap(endCity1, endCity2, e1, e2),

        TwoSwap(startCity1, endCity2, e1, e2),
        TwoSwap(endCity1, startCity2, e1, e2)

    ).filter {
        it.edge1.startCity !in it.edge2.let { setOf(it.startCity, it.endCity) } &&
            it.edge1.endCity !in it.edge2.let { setOf(it.startCity, it.endCity) }
    }
    .firstOrNull { swap ->
        swap.execute()
        val result = Model.tourMaintained
        if (!result) {
        swap.reverse()
        }
        result
    }
}

This can then be used for the TWO_OPT and SIMULATED_ANNEALING algorithms. Note that for both these algorithms I start by cleaning the animationQueue, execute the RANDOM algorithm and take all of its animations, and add them to this algorithm’s animations. For the TWO_OPT, I then attempt 2000 random swaps and only add animations that improve the distance of the tour. Otehrwise I call reverse() and do not animate the swap (as if it never happened).

TWO_OPT {
    override fun execute() {
        animationQueue.clear()
        SearchStrategy.RANDOM.execute()
        animationQueue += SearchStrategy.RANDOM.animationQueue

        (1..2000).forEach { iteration ->
        Model.edges.sampleDistinct(2).toList()
                .let { it.first() to it.last() }
                .also { (e1,e2) ->

                    val oldDistance = Model.totalDistance
                    e1.attemptTwoSwap(e2)?.also {
                        when {
                            oldDistance <= Model.totalDistance -> it.reverse()
                            oldDistance > Model.totalDistance -> animationQueue += it.animate()
                        }
                    }
                }
        }
        Model.distanceProperty.set(Model.totalDistance)
        Model.bestDistanceProperty.set(Model.totalDistance)

        println("TWO-OPT BEST DISTANCE: ${Model.totalDistance}")

    }
}

The SIMULATED_ANNEALING, at least on the animation front, is not much different. I essentially add a further condition to animate inferior moves that pass the coin flip. Swaps that do not are again reversed.

// Desmos graph for intuition: https://www.desmos.com/calculator/rpfpfiq7ce
if (weightedCoinFlip(
                exp((-(newDistance - bestDistance)) / temperature)
        )
) {
    animationQueue += swap.animate()

} else {
    swap.reverse()
}

As soon as the algorithm is done, call animationQueue.play() on the desired SearchStrategy enumerable and watch the fireworks.

22 comments:

  1. Replies
    1. It was drawn in later but this isn't reflected in the video or all the images. The image had some geographic inaccuracies I had to correct once I saw them.

      Delete
  2. Looking for best TNPSC study materials to prepare for the examination? Make use of our samacheer kalvi books and other study guide to learn from experts. TNPSC One Time Registration

    ReplyDelete
  3. I am happy with your article,your website is pretty good. Many articles are very useful for everyone. I am sure your website will grow in the future.
    You can take guidance from Quickbooks desktop support to grow your business with the help of add-ons.

    ReplyDelete
  4. Unable to receive SMS verification for Gemini? Do you want to fix this issue immediately? If yes, don’t waste your single minute and directly get connected to the professionals by dialing Gemini customer support number. The professionals know all the Gemini Support Number means and methods that easily vanish the errors. They also provide assistance for better understanding. You can approach them as per your needs and requirements and you will never be disappointed with their services.

    ReplyDelete
  5. Are you dealing up with stolen password issue in your Blockchain account? Is your password got hacked? There could be various reasons for password problems but the main thing is how to recover them. To nullify all the password errors from roots, you should directly call on Blockchain support number as soon as you encounter such issues. You will be connected Blockchain Support NUmber to the experts team and they will provide ultimate solutions and remedies related to the error that can easily fix up the error without any difficulty.

    ReplyDelete
  6. Dealing with the 403 forbidden error in Binance account? Unable to access Binance account due to this error? Such complex errors need proper guidance and support from the specialists as on average person can’t handle such high-level issues. So, you better call on Binance support number and you will get in touch with the professionals immediately. They will fix their issue by delivering high-end assistance to the users. So, enjoy their services at fullest for removing your Binance Support Number errors and doubts. Speak to the experienced team by dialing customer support phone number which is functional throughout the year without any discontinuity.

    ReplyDelete
  7. Are you a Gemini user who is facing issues due to glitches and server errors. One such error is appearance of connectivity issue in Gemini. Issues such these can be tackled very easily. Dial Gemini customer support number to find solutions to your problems. Get in touch with a representative via phone call and find the remedies that you are looking for. The experts at Gemini are knowledgeable and skilled. They are always available to help you out. You need to dial Gemini number and get ultimate solutions and ways from the team to end the errors.

    ReplyDelete
  8. ATT is one of the greatest remote specialist organizations in the United States. These clients utilize the administrations at the fullest and might confront issues while utilizing the administrations. in the event that you have any sorts of issue identified with ATT remote, at that point you can contact ATT Customer Service Number. We have experts technician remove your anytype issues.
    ATT Customer Service Number
    ATT Email Support Number
    Gmail Customer Service Number
    Gmail support number

    ReplyDelete
  9. QuickBooks Customer Service is available round the clock to resolve accounting problems. Reach experts at QuickBooks support phone Number and get instant help.

    ReplyDelete
  10. We are one of the third party which provide best in class support for all kind of Roku tv setup , installation, updation and much more related issues over phone call and chat across the USA 24*7. We have a dedicated team of professionals who are well certified and experience to handle all kind of Roku tv box issues. We ensure each and every customer to get full satisfaction for his concern. You just need to dial up our roku customer support service number 1-800-382-3046.
    Roku Customer Service Number
    Roku Support Phone Number
    Roku Toll Free Number
    Roku Customer Care Number
    Roku Helpline Number

    ReplyDelete
  11. if you are facing problem related to virus in your PC and computer.Sign in to enter your product key, access your account, manage your subscription, and extend your Norton protection to PC, Mac, Android, and iOS devices then contact us.

    www.norton.com/setup
    www.norton.com/setup
    www.norton.com/setup

    ReplyDelete
  12. http://0rz.tw/D9J4q
    http://shrtlnk.net/4082030
    https://bit.ly/33sDmFx
    https://hostimize.com/7h+
    https://vae.me/cwoV

    ReplyDelete
  13. Get a clear idea on 123.hp.com/setup before you proceed. Slide all the necessary cables; try establishing a good speed network connection (use wireless option). Now find the compatible software visiting our webpage and try installing it right away. Try to answer all the wireless setup wizard instructions to complete the setup. For more assistance ring the customer support number
    To get rid of 123.hp.com/setup errors try checking and verifying the wireless setup steps or else you can try executing the tips and tricks right away @ +1-844-876-5110

    ReplyDelete
  14. Do you require HP printer setup for your mac operating system? Is your printer driver not suitable for macOS? Then visit the 123.hp.com to get the software and driver for better functioning of your printer. You can also call our expert HP support team for services.

    ReplyDelete
  15. Crackle, the most entertaining channel is now on Roku to entertain you. If you are new to this channel, use the page crackle.com/activate. Once if you activate the channel, the most interesting program collections are on its way. The categories include full-length movies, TV shows, and documentaries and much more.

    ReplyDelete
  16. Are you facing error in log in to Binance account? Binance log in process is easy to execute but there are a few users who get in trouble while executing the process. If you’re one of them and need solutions to handle all such issues, you can always call on Binance customer care number which is all the time active. Talking to the team of skilled professionals is the Binance Support Number right decision as it helps in saving your time. Whenever you are in a fix, the team is going to eliminate all your errors in no time.

    ReplyDelete
  17. Account hacking error is the most common and many users of Blockchain have been victim of this. If you don’t know how to solve such issue, you can always take help from the team of elite professionals who are there to assist you. Call on Blockchain support number which is always functional and users can avail quality solution from the team of elite professionals. Feel free to Blockchain Support Number take help from the team anytime and get solutions that are easy to execute. Ask for helping hand from them and they will give you the best results.

    ReplyDelete
  18. Account hacking error is the most common and many users of Gemini have been victim of this. If you don’t know how to solve such issue, you can always take help from the team of elite professionals who are there to assist you. Call on Gemini support number which is always functional and users can avail quality solution from the team of elite professionals. Feel free to take Gemini Support Number help from the team anytime and get solutions that are easy to execute. Ask for helping hand from them and they will give you the best results.

    ReplyDelete
  19. Are you having trouble in dealing with Binance two-factor expansion error? If you need assistance and looking for ways to deal with such issues, you can always call on Binance support number which is always functional and users can always talk to the experts for quality solutions. Whenever you are in trouble, Binance Support Number reaching the team is a right decision as this step would help in fixing errors completely from the roots. Talk to them for availing solutions.

    ReplyDelete
  20. It’s always my passion to write creative articles. Have worked on a lot of innovative and interesting topics. Read it and it’s informative. Recommend you to provide your feedback & suggestions to work on more titles. Contact me or reach me if you would like to know more about my profile.
    Blog: cbs.com/roku

    ReplyDelete