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.
Why is Denmark deleted?
ReplyDeleteIt 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